login
A367892
Total number of steps of Euclid's GCD algorithm to calculate gcd(x,y) for all pairs x,y in the range 1 <= y <= x <= n.
2
1, 3, 7, 12, 21, 29, 43, 58, 75, 93, 121, 142, 175, 207, 239, 274, 321, 363, 419, 464, 515, 571, 645, 700, 769, 843, 919, 992, 1089, 1161, 1263, 1354, 1451, 1557, 1659, 1752, 1877, 1997, 2121, 2232, 2379, 2493, 2649, 2782, 2915, 3067, 3245, 3384, 3549
OFFSET
1,2
COMMENTS
n < a(n) < A367690(n) for n > 1.
LINKS
FORMULA
a(n) = Sum_{x=1..n} Sum_{y=1..x} A107435(x,y).
a(n) = a(n-1) + 1 + A049826(n) with a(0) = 0. - Alois P. Heinz, Dec 04 2023
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(n, j), j=1..n))
end:
seq(a(n), n=1..100); # Alois P. Heinz, Dec 04 2023
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[n, j], { j, 1, n}]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Mar 08 2024, after Alois P. Heinz *)
PROG
(Python)
A107435 = lambda x, y: 0 if y == 0 else 1 + A107435(y, x % y)
a = lambda n: n+sum(A107435(x, y) for x in range(1, n+1) for y in range(1, x))
print([a(n) for n in range(1, 50)])
CROSSREFS
KEYWORD
nonn
AUTHOR
Darío Clavijo, Dec 04 2023
STATUS
approved