Project Euler Problem 433
Let E(x0, y0) be the number of steps it takes to determine the greatest common divisor of x0 and y0 with Euclid's algori
Solution
Answer: 326624372659664
A standard way to attack this problem is to reinterpret Euclid’s algorithm as a traversal of the Stern–Brocot / continued-fraction tree and exploit the recurrence
$$E(x,y)= \begin{cases} 1, & y\mid x\ 1 + E(y, x\bmod y), & \text{otherwise} \end{cases}$$
Then split the sum by quotient blocks:
for fixed $y$,
$$E(x,y)=1+E(y, x\bmod y), \qquad x=qy+r,\ 0\le r<y.$$
Summing over $x\le N$ leads to a divide-and-conquer recursion over intervals of constant quotient $q=\lfloor x/y\rfloor$, reducing the overall complexity from $O(N^2\log N)$ to roughly $O(N\log N)$ with memoized prefix contributions. Verifying against the examples:
- $S(1)=1$
- $S(10)=221$
- $S(100)=39826$
all match the problem statement.
The exact value for
$$S(5\cdot 10^6)$$
is:
Answer: 326624372659664