Project Euler Problem 700

Solution

Answer: 1517926517777556

Let

$$a = 1504170715041707,\qquad m = 4503599627370517.$$

We study the sequence

$$E_n = an \pmod m.$$

An Eulercoin is a term that is strictly smaller than every previous term.

We must compute the sum of all Eulercoins.

---

1. Mathematical analysis

The sequence is

$$E_n = an - m\left\lfloor \frac{an}{m}\right\rfloor.$$

Because $\gcd(a,m)=1$, the sequence is a permutation of the integers $1,\dots,m-1$.

The key observation is that Eulercoins are exactly the successive minima of this modular sequence.

The first few terms are:

$$\begin{aligned} E_1 &= 1504170715041707,\ E_2 &= 3008341430083414,\ E_3 &= 8912517754604. \end{aligned}$$

Since

$$8912517754604 < 1504170715041707,$$

the third term is the second Eulercoin.

---

Core number theoretic insight

A direct simulation is impossible because $m \approx 4.5\times10^{15}$.

The breakthrough comes from modular inverses.

Since $\gcd(a,m)=1$, there exists $a^{-1}$ such that

$$aa^{-1}\equiv 1\pmod m.$$

Using the extended Euclidean algorithm:

$$a^{-1} \equiv 3451657199285664 \pmod m.$$

This means:

$$n \equiv a^{-1}E_n \pmod m.$$

---

Two complementary searches

The Eulercoins split naturally into two phases.

Phase 1: Large Eulercoins

Generate the sequence forward:

$$E_n = (E_{n-1}+a)\bmod m,$$

keeping only new minima.

These minima decrease rapidly.

After relatively few iterations, the Eulercoins become small.

---

Phase 2: Small Eulercoins

Suppose $x$ is an Eulercoin.

Then its index is

$$n_x \equiv a^{-1}x \pmod m.$$

A number $x$ is an Eulercoin iff its corresponding index $n_x$ is smaller than the indices of all smaller positive integers already checked.

So for small $x$, we can test:

$$n_x = (a^{-1}x)\bmod m.$$

If this index is the smallest seen so far, then $x$ is an Eulercoin.

This second method finds the tiny Eulercoins extremely quickly.

---

Why this works

Suppose $x<y$.

If

$$n_x < n_y,$$

then $x$ appears earlier in the sequence than $y$, so $y$ cannot be the first occurrence of a minimum below $x$.

Thus Eulercoins correspond precisely to values whose modular-inverse index is a new minimum.

This converts the difficult forward modular scan into a very cheap search over small integers.

---

2. Python implementation

from math import gcd

A = 1504170715041707
M = 4503599627370517

# ------------------------------------------------------------
# Extended Euclidean algorithm
# ------------------------------------------------------------

def egcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

# modular inverse of A mod M
g, x, y = egcd(A, M)
A_INV = x % M

# ------------------------------------------------------------
# Phase 1: generate large Eulercoins directly
# ------------------------------------------------------------

coins = []

current = A
minimum = A

coins.append(A)

while current > 10_000_000:
    current = (current + A) % M

    if current < minimum:
        minimum = current
        coins.append(current)

# ------------------------------------------------------------
# Phase 2: generate small Eulercoins using inverse mapping
# ------------------------------------------------------------

best_index = M

for x in range(1, minimum):
    idx = (A_INV * x) % M

    if idx < best_index:
        best_index = idx
        coins.append(x)

# ------------------------------------------------------------
# Final answer
# ------------------------------------------------------------

answer = sum(coins)

print(answer)

---

3. Code walkthrough

Step 1: Compute the modular inverse

g, x, y = egcd(A, M)
A_INV = x % M

This finds $A^{-1}$ satisfying

$$AA^{-1}\equiv1\pmod M.$$

---

Step 2: Forward search for large Eulercoins

current = (current + A) % M

This generates successive sequence terms.

Whenever:

if current < minimum:

we have discovered a new Eulercoin.

The sequence of minima begins:

$$1504170715041707,; 8912517754604,; 2044785486369,; 1311409677241,\dots$$

---

Step 3: Reverse search for small Eulercoins

For every small integer $x$, compute where it appears:

idx = (A_INV * x) % M

If this index is the smallest seen so far, then $x$ must appear before all smaller candidates and is therefore an Eulercoin.

This efficiently discovers all remaining tiny Eulercoins down to $1$.

---

4. Verification

The first two Eulercoins are:

$$1504170715041707$$

and

$$8912517754604.$$

Their sum is:

$$1513083232796311,$$

matching the problem statement.

The algorithm is mathematically exact:

• no floating point,
• no probabilistic steps,
• all arithmetic is integer modular arithmetic.

The final computed total is:

$$1517926517777556.$$

---

Answer: 1517926517777556