## Steps in Euclid's algorithm

### Problem 433

Published on Saturday, 22nd June 2013, 04:00 pm; Solved by 284; Difficulty rating: 65%
Let E(`x`_{0}, `y`_{0}) be the number of steps it takes to determine the greatest common divisor of `x`_{0} and `y`_{0} with **Euclid's algorithm**. More formally:`x`_{1} = `y`_{0}, `y`_{1} = `x`_{0} mod `y`_{0}`x _{n}` =

`y`

_{n-1},

`y`

_{n}=

`x`

_{n-1}mod

`y`

_{n-1}

E(

`x`

_{0},

`y`

_{0}) 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^{6}).