|
|
A367954
|
|
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.
|
|
0
|
|
|
0, 2, 7, 14, 26, 38, 57, 78, 102, 128, 165, 196, 240, 284, 329, 378, 440, 498, 571, 634, 704, 780, 875, 952, 1044, 1142, 1243, 1342, 1466, 1566, 1697, 1818, 1946, 2084, 2219, 2346, 2506, 2662, 2823, 2972, 3158, 3312, 3509, 3684, 3860, 4056, 4279, 4464, 4676
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{x=1..n} Sum_{y=x+1..n} (A107435(y,x) + 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)+add(g(j, n), j=1..n-1))
end:
|
|
MATHEMATICA
|
g[x_, y_] := g[x, y] = If[y == 0, 0, 1 + g[y, Mod[x, y]]];
a[n_] := a[n] = If[n == 0, 0, a[n - 1] + Sum[g[j, n], { j, 1, n - 1}]];
|
|
PROG
|
(Python)
a = lambda n: sum(A107435(y, x)+1 for x in range(1, n+1) for y in range(x+1, n+1))
print([a(n) for n in range(1, 50)])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|