Project Euler/700

Problem Statement

Leonhard Euler was born on 15 April 1707.

Consider the sequence:

$ a_n = 1504170715041707 \, n \bmod 4503599627370517 $

An element of this sequence is defined to be an Eulercoin if it is strictly smaller than all previously found Eulercoins. For example:

• The first term is $ 1504170715041707 $, which is the first Eulercoin.
• The second term is $ 3008341430083414 $, which is greater than the first, so it is not an Eulercoin.
• The third term is $ 8912517754604 $, which is smaller than the first, making it the second Eulercoin.

The sum of the first two Eulercoins is therefore $ 1513083232796311 $.

Find the sum of all Eulercoins.

Approach

Key Insight

The sequence $ a(n) = k n \bmod M $ achieves new record minima exactly at the convergents of the continued fraction of $ k/M $. By the three-distance theorem, these record lows correspond precisely to the odd-indexed remainders in the Euclidean algorithm applied to $ (M, k) $:

$ r_1 = k, \; r_2 = M \bmod k, \; r_3, \; r_4, \; r_5, \dots $

Only the odd-indexed steps ($ r_1, r_3, r_5, \dots $) generate Eulercoins.

Euclidean Algorithm Walk

At each odd step $ i $ with quotient $ q_i = \lfloor r_i / r_{i+1} \rfloor $, there are exactly $ q_i $ Eulercoins. These Eulercoins form a descending arithmetic progression:

$ r_i - j \cdot r_{i+1}, \quad \text{for } j = 1, 2, \dots, q_i $

The sum contributed by this step is:

$ \sum_{j=1}^{q_i} \left( r_i - j \cdot r_{i+1} \right) = q_i \cdot r_i - r_{i+1} \cdot \frac{q_i (q_i + 1)}{2} $

Algorithm

1. Initialize $ \text{sum} = k $ (the first Eulercoin, $ r_1 $).
2. Run the Euclidean algorithm on $ (M, k) $, maintaining $ (a, b) = (r_i, r_{i+1}) $ starting with $ a = k $, $ b = M \bmod k $.
3. For each step $ i = 1, 2, 3, \dots $:
   • Compute quotient $ q = \lfloor a / b \rfloor $ and remainder $ \text{next} = a \bmod b $.
   • If $ i $ is odd: add $ q \cdot a - b \cdot q (q + 1) / 2 $ to the sum.
   • Set $ a = b $, $ b = \text{next} $, and increment $ i $.
4. Stop when $ b = 0 $. Return the accumulated sum.

Complexity

The Euclidean algorithm terminates in $ O(\log M) $ steps — approximately 34 iterations for this problem. All intermediate products fit within a Java long, so no overflow handling is needed. The solution runs in about 40 ms.

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem700.java