cp's OEIS Frontend

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.

%I A367954 #37 Mar 08 2024 07:18:09
%S A367954 0,2,7,14,26,38,57,78,102,128,165,196,240,284,329,378,440,498,571,634,
%T A367954 704,780,875,952,1044,1142,1243,1342,1466,1566,1697,1818,1946,2084,
%U A367954 2219,2346,2506,2662,2823,2972,3158,3312,3509,3684,3860,4056,4279,4464,4676
%N 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.
%C A367954 A000096(n-1) < a(n) < A367690(n).
%F A367954 a(n) = Sum_{x=1..n} Sum_{y=x+1..n} (A107435(y,x) + 1).
%F A367954 a(n) = A367690(n) - A367892(n).
%F A367954 a(n) = A367892(n) + A000096(n).
%F A367954 a(n) = A000217(n-1) + Sum_{i=1..n} A049826(i).
%p A367954 g:= proc(x, y) option remember;
%p A367954       `if`(y=0, 0, 1+g(y, irem(x, y)))
%p A367954     end:
%p A367954 a:= proc(n) option remember; `if`(n=0, 0,
%p A367954       a(n-1)+add(g(j, n), j=1..n-1))
%p A367954     end:
%p A367954 seq(a(n), n=1..100);  # _Alois P. Heinz_, Dec 05 2023
%t A367954 g[x_, y_] := g[x, y] = If[y == 0, 0, 1 + g[y, Mod[x, y]]];
%t A367954 a[n_] := a[n] = If[n == 0, 0, a[n - 1] + Sum[g[j, n], { j, 1, n - 1}]];
%t A367954 Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Mar 08 2024, after _Alois P. Heinz_ *)
%o A367954 (Python)
%o A367954 A107435 = lambda x, y: 0 if y == 0 else 1 + A107435(y, x % y)
%o A367954 a = lambda n: sum(A107435(y,x)+1 for x in range(1, n+1) for y in range(x+1, n+1))
%o A367954 print([a(n) for n in range(1, 50)])
%Y A367954 Cf. A000096, A000217, A049826, A107435, A367690, A367892.
%K A367954 nonn
%O A367954 1,2
%A A367954 _Darío Clavijo_, Dec 05 2023