Detailed mathematical approach

Problem Summary

Define the sequence

$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$

with residues interpreted in \(\{0,1,\dots,M-1\}\). An Eulercoin is a term that is smaller than every earlier term:

$r_k<\min_{1\le j<k} r_j.$

The goal is to sum all Eulercoins. A naive scan through all possible indices would be far too large, so the solution uses a two-phase argument: first collect the large record lows in index order, then recover the remaining small record lows from value order by using a modular inverse.

Mathematical Approach

The key fact is that multiplication by \(A\) permutes the nonzero residues modulo \(M\). That allows us to look at the same sequence from two complementary directions: by increasing index \(k\), and by increasing value \(v\).

Step 1: The sequence is a permutation of the nonzero residues

Because \(\gcd(A,M)=1\), the congruence

$kA\equiv \ell A \pmod M$

implies \(k\equiv \ell \pmod M\). Therefore the map \(k\mapsto (kA)\bmod M\) is injective modulo \(M\), and for \(k=1,2,\dots,M-1\) it visits every nonzero residue exactly once.

So each integer \(v\in\{1,2,\dots,M-1\}\) appears at one unique position in the sequence. This uniqueness is what makes the reverse phase possible.

Step 2: Recover the unique index of a value

Since \(\gcd(A,M)=1\), there exists a modular inverse \(A^{-1}\pmod M\). For any nonzero value \(v\), the position where \(v\) occurs is the unique solution of

$kA\equiv v \pmod M,$

namely

$k(v)\equiv A^{-1}v \pmod M.$

This means we do not have to wait for a small value to appear in a long forward simulation. We can compute directly where that value occurs.

Step 3: Characterize Eulercoins in value order

A value \(v\) is an Eulercoin if and only if it appears before every smaller positive value. If \(\mathcal{E}\) denotes the set of Eulercoins, then

$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$

The forward implication is immediate: if some smaller value \(u<v\) appeared earlier, then \(v\) could not be a new record low. The converse is just as important: if every smaller value appears later, then all earlier sequence terms are larger than \(v\), so \(v\) really is a new minimum.

Thus the Eulercoins are exactly the record minima of the index sequence \(k(1),k(2),k(3),\dots\) when values are scanned upward.

Step 4: Use a forward scan for the large Eulercoins

The implementations begin in index order. Starting from \(r_1=A\), they update the sequence by one modular addition at a time:

$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$

Whenever the new term is smaller than the current record low, it is an Eulercoin and is added to the sum. This efficiently captures the early Eulercoins, which still have large values.

The forward phase stops when the current Eulercoin drops below \(20{,}000{,}000\). Let that last forward Eulercoin be \(B\). Any later Eulercoin must be smaller than \(B\), so from that point on only the values \(1,2,\dots,B-1\) remain to be checked.

Step 5: Finish with a reverse scan on the remaining values

Now scan the values \(v=1,2,\dots,B-1\). For each \(v\), compute the unique position \(k(v)\equiv A^{-1}v\pmod M\). Maintain the smallest index seen so far among all scanned values.

If the new index is smaller than that running minimum, then \(v\) is an Eulercoin by the criterion from Step 3, so it must be added to the total. Otherwise some smaller value already appears earlier, and \(v\) is not an Eulercoin.

This split is exact, not heuristic. The forward phase already found every Eulercoin with value at least \(B\), and the reverse phase checks every positive value below \(B\). The two sets are disjoint and together contain all Eulercoins.

Worked Example

With the actual constants, the first term is

$r_1=A=1504170715041707.$

The second term is

$r_2=2A\bmod M=3008341430083414,$

which is larger than \(r_1\), so it is not an Eulercoin.

For \(k=3\),

$3A=4512512145125121=M+8912517754604,$

hence

$r_3=8912517754604.$

Since

$8912517754604<1504170715041707,$

the third term is the second Eulercoin. The reverse viewpoint describes the same event differently: that value has a smaller index than every positive value below it, so it becomes a new record low exactly once.

How the Code Works

The C++, Python, and Java implementations all follow the same two-phase strategy. They begin with the modular sequence at \(A\), keep track of the smallest value seen so far, and add each strict decrease to the running sum. That loop ends once the current Eulercoin falls below \(20{,}000{,}000\).

Next they compute the modular inverse of \(A\) modulo \(M\) with the extended Euclidean algorithm. After that, they scan the remaining candidate values \(1\le v<B\), convert each value into its unique sequence index with one modular multiplication, and add \(v\) whenever that recovered index is a new minimum among all indices seen in the reverse scan.

The arithmetic details differ slightly by language, but the mathematics is identical. The C++ implementation uses a 128-bit intermediate product before reducing modulo \(M\), Python relies on arbitrary-precision integers, and the Java implementation uses big-integer arithmetic for the modular product.

Complexity Analysis

Let \(K_f\) be the number of forward iterations before the forward phase stops, and let \(B\) be the last Eulercoin found there. The first phase costs \(O(K_f)\), the second phase costs \(O(B)\), and both phases use only constant extra memory. Therefore the total complexity is

$O(K_f+B)$

time with \(O(1)\) additional space. For this problem that is vastly smaller than scanning the sequence all the way to \(k=M-1\).

Footnotes and References

1. Problem page: Project Euler 700
2. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse
3. Extended Euclidean algorithm: Wikipedia - Extended Euclidean algorithm
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Complete residue system: Wikipedia - Complete residue system