Problem 433
Steps in Euclid’s algorithm
Let E(x0, y0) be the number of steps it takes to determine the greatest common divisor of x0 and y0 with Euclid’s algorithm. More formally:
x1 = y0, y1 = x0 mod y0
xn = yn-1, yn = xn-1 mod yn-1
E(x0, y0) is the smallest n such that yn = 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·106).
欧几里德算法的步数
记E(x0, y0)为运用欧几里德算法求x0和y0的最大公约数的步数。更加正式的说：
x1 = y0, y1 = x0 mod y0
xn = yn-1, yn = xn-1 mod yn-1
E(x0, y0)是使得yn = 0的最小的n。
已知E(1,1) = 1，E(10,6) = 3以及E(6,10) = 4。
对于1 ≤ x,y ≤ N，定义S(N)为所有E(x,y)的和。
已知S(1) = 1，S(10) = 221以及S(100) = 39826。
求S(5·106)。