Steps in Euclid's algorithm

Let E(x₀, y₀) be the number of steps it takes to determine the greatest common divisor of x₀ and y₀ with Euclid's algorithm. More formally:x₁ = y₀, y₁ = x₀ mod y₀x_n = y_n-1, y_n = x_n-1 mod y_n-1 E(x₀, y₀) is the smallest n such that y_n = 0.

We have E(1,1) = 1, E(10,6) = 3 and E(6,10) = 4.

Define S(N) as the sum of E(x,y) for 1 ≤ x,y ≤ N. We have S(1) = 1, S(10) = 221 and S(100) = 39826.

Find S(5·10⁶).

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter