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.

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

Author

Darío Clavijo, Dec 04 2023

Keywords

• nonn

Comments

n < a(n) < A367690(n) for n > 1.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A049826, A107435, A367690.

Programs

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 *)

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)])

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