|
|
A367690
|
|
Total number of steps of Euclid's GCD algorithm to calculate gcd(x,y) for all pairs x,y in the range 1 <= x,y <= n.
|
|
2
|
|
|
1, 5, 14, 26, 47, 67, 100, 136, 177, 221, 286, 338, 415, 491, 568, 652, 761, 861, 990, 1098, 1219, 1351, 1520, 1652, 1813, 1985, 2162, 2334, 2555, 2727, 2960, 3172, 3397, 3641, 3878, 4098, 4383, 4659, 4944, 5204, 5537, 5805, 6158, 6466, 6775, 7123, 7524, 7848
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The number of steps to calculate gcd(x,y) is A107435(x,y) for x<=y, and is the length of the continued fraction expansion of x/y (including 0 for the integer part).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = a(n-1) + n + A049826(n) * 2 and a(1) = 1.
a(n) = a(n-1) + n + (Sum_{j=1..n-1} A107435(n,j)) * 2 and a(1) = 1.
|
|
MAPLE
|
g:= proc(x, y) option remember;
`if`(y=0, 0, 1+g(y, irem(x, y)))
end:
a:= proc(n) option remember; `if`(n=0, 0,
a(n-1)+n+2*add(g(n, j), j=1..n-1))
end:
|
|
PROG
|
(Python)
from functools import cache
@cache
def a(n):
if n == 0: return 0
print([a(n) for n in range(1, 49)])
(PARI)
a(n) = sum(x=1, n, sum(y=1, n, A107435(x, y)));
print(vector(49, n, a(n)));
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|