🧠 Project Euler

Solutions to problems from Project Euler.

Project Euler problems combine mathematics, algorithms, and programming, making them a great way to sharpen problem-solving skills. This repo acts as a small learning log where I share my approaches, methods, and things I learn while solving them.

---

📊 Recent Work

Problem 25 — 1000-digit Fibonacci Number

• The goal is to determine the index of the first Fibonacci number that contains 1000 digits. 📄 Problem Statement. 💻 Solution
• My solution iteratively generates Fibonacci numbers using a while loop. The number of digits of each new Fibonacci number is calculated by converting the integer to a string and checking its length. The loop continues until a Fibonacci number with 1000 digits is reached.
• An alternative idea explored was to store the Fibonacci values as floating point numbers. However, this approach fails because Python floats have a maximum size (around $1.8 \times 10^{308}$), after which values overflow to infinity.

Problem 31 — Coin Sums

• The task is to determine how many different ways £2 can be made using UK coins (1p, 2p, 5p, 10p, 20p, 50p, £1, £2). 📄 Problem Statement. 💻 Solution
• The approach taken uses a recursive search over coin denominations. At each step, the recursive function effectively "fixes" how many coins of the current denomination are used, and recursively solves the remaining value using the other coin types.
• An initial idea was to generate all possible combinations of coin counts using a cartesian product. However, the number of candidate combinations grows extremely large, making this approach impractical.

Problem 23 — Non-Abundant Sums

• The task is to find the sum of all positive integers which cannot be written as the sum of two abundant numbers. 📄 Problem Statement. 💻 Solution
• My approach consisted of three main steps:
  1. Identify abundant numbers: Compute all abundant numbers up to the known upper bound given in the problem ($28{,}123$). Above this limit, it is known that every integer can be written as the sum of two abundant numbers.
  2. Generate abundant sums: Using the list of abundant numbers, compute all pairwise sums that do not exceed the upper bound.
  3. Take the complement: Determine which integers up to the bound do not appear in the set of abundant sums; these are exactly the numbers that cannot be expressed as the sum of two abundant numbers.
• Before settling on this approach, the On-Line Encyclopedia of Integer Sequences entry for odd abundant numbers was reviewed to see whether a method using arithmetic sequence could generate all abundant numbers directly. However, no sequence was found that captured all cases. As a result, the approach above turned out to be both straightforward and efficient, especially given the known upper bound in the problem.

Problem 11 — Largest Product in a Grid

• The challenge is to find the largest product of four adjacent numbers in a $20 \times 20$ grid (horizontal, vertical, diagonal, or anti-diagonal). 📄 Problem Statement. 💻 Solution
• My approach was two simple steps:
  1. Extract all candidate 1D arrays (rows, columns, diagonals, anti-diagonals).
  2. Scan each array using a length-4 sliding window, compute each subarray product, and track the maximum.
• The solution runs in $\mathcal{O}(n^2)$ time. There are about $\mathcal{O}(n)$ candidate 1D arrays, and for each array we check $\mathcal{O}(n)$ length-4 subarrays, giving a total of $\mathcal{O}(n) \times \mathcal{O}(n) = \mathcal{O}(n^2)$.
• The approach was loosely inspired by the maximum subarray problem (often solved with Kadane's algorithm). While this problem focuses on products rather than sums, the idea of scanning arrays and evaluating subarrays is conceptually similar.

---