Admin: Create Project Euler/700 page with problem statement, Euclidean algorithm approach, and solution link (via create-page on MediaWiki MCP Server)

2026-06-16T23:31:31Z

Create Project Euler/700 page with problem statement, Euclidean algorithm approach, and solution link (via create-page on MediaWiki MCP Server)

New page

==Problem Statement==

Leonhard Euler was born on 15 April 1707.

Consider the sequence:

<math>
a_n = 1504170715041707 \, n \bmod 4503599627370517
</math>

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 <math>1504170715041707</math>, which is the first Eulercoin.
* The second term is <math>3008341430083414</math>, which is greater than the first, so it is not an Eulercoin.
* The third term is <math>8912517754604</math>, which is smaller than the first, making it the second Eulercoin.

The sum of the first two Eulercoins is therefore <math>1513083232796311</math>.

Find the sum of all Eulercoins.

==Approach==

===Key Insight===

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

<math>
r_1 = k, \; r_2 = M \bmod k, \; r_3, \; r_4, \; r_5, \dots
</math>

Only the odd-indexed steps (<math>r_1, r_3, r_5, \dots</math>) generate Eulercoins.

===Euclidean Algorithm Walk===

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

<math>
r_i - j \cdot r_{i+1}, \quad \text{for } j = 1, 2, \dots, q_i
</math>

The sum contributed by this step is:

<math>
\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}
</math>

===Algorithm===

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

===Complexity===

The Euclidean algorithm terminates in <math>O(\log M)</math> steps — approximately 34 iterations for this problem. All intermediate products fit within a Java <code>long</code>, 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

==Flags==

{{ProjectEulerFlag}}

Project Euler/700 - Revision history

Admin: Create Project Euler/700 page with problem statement, Euclidean algorithm approach, and solution link (via create-page on MediaWiki MCP Server)