%I #33 Mar 08 2024 08:58:26

%S 1,3,7,12,21,29,43,58,75,93,121,142,175,207,239,274,321,363,419,464,

%T 515,571,645,700,769,843,919,992,1089,1161,1263,1354,1451,1557,1659,

%U 1752,1877,1997,2121,2232,2379,2493,2649,2782,2915,3067,3245,3384,3549

%N 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.

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

%H Alois P. Heinz, <a href="/A367892/b367892.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{x=1..n} Sum_{y=1..x} A107435(x,y).

%F a(n) = a(n-1) + 1 + A049826(n) with a(0) = 0. - _Alois P. Heinz_, Dec 04 2023

%p g:= proc(x, y) option remember;

%p `if`(y=0, 0, 1+g(y, irem(x, y)))

%p end:

%p a:= proc(n) option remember; `if`(n=0, 0,

%p a(n-1)+add(g(n, j), j=1..n))

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Dec 04 2023

%t g[x_, y_] := g[x, y] = If[y == 0, 0, 1 + g[y, Mod[x, y]]];

%t a[n_] := a[n] = If[n == 0, 0, a[n - 1] + Sum[g[n, j], { j, 1, n}]];

%t Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Mar 08 2024, after _Alois P. Heinz_ *)

%o (Python)

%o A107435 = lambda x, y: 0 if y == 0 else 1 + A107435(y, x % y)

%o a = lambda n: n+sum(A107435(x,y) for x in range(1, n+1) for y in range(1, x))

%o print([a(n) for n in range(1, 50)])

%Y Cf. A049826, A107435, A367690.

%K nonn

%O 1,2

%A _Darío Clavijo_, Dec 04 2023