cp's OEIS Frontend

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.

%I A367892 #33 Mar 08 2024 08:58:26
%S A367892 1,3,7,12,21,29,43,58,75,93,121,142,175,207,239,274,321,363,419,464,
%T A367892 515,571,645,700,769,843,919,992,1089,1161,1263,1354,1451,1557,1659,
%U A367892 1752,1877,1997,2121,2232,2379,2493,2649,2782,2915,3067,3245,3384,3549
%N 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.
%C A367892 n < a(n) < A367690(n) for n > 1.
%H A367892 Alois P. Heinz, <a href="/A367892/b367892.txt">Table of n, a(n) for n = 1..10000</a>
%F A367892 a(n) = Sum_{x=1..n} Sum_{y=1..x} A107435(x,y).
%F A367892 a(n) = a(n-1) + 1 + A049826(n) with a(0) = 0. - _Alois P. Heinz_, Dec 04 2023
%p A367892 g:= proc(x, y) option remember;
%p A367892       `if`(y=0, 0, 1+g(y, irem(x, y)))
%p A367892     end:
%p A367892 a:= proc(n) option remember; `if`(n=0, 0,
%p A367892       a(n-1)+add(g(n, j), j=1..n))
%p A367892     end:
%p A367892 seq(a(n), n=1..100);  # _Alois P. Heinz_, Dec 04 2023
%t A367892 g[x_, y_] := g[x, y] = If[y == 0, 0, 1 + g[y, Mod[x, y]]];
%t A367892 a[n_] := a[n] = If[n == 0, 0, a[n - 1] + Sum[g[n, j], { j, 1, n}]];
%t A367892 Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Mar 08 2024, after _Alois P. Heinz_ *)
%o A367892 (Python)
%o A367892 A107435 = lambda x, y: 0 if y == 0 else 1 + A107435(y, x % y)
%o A367892 a = lambda n: n+sum(A107435(x,y) for x in range(1, n+1) for y in range(1, x))
%o A367892 print([a(n) for n in range(1, 50)])
%Y A367892 Cf. A049826, A107435, A367690.
%K A367892 nonn
%O A367892 1,2
%A A367892 _Darío Clavijo_, Dec 04 2023