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.

0, 2, 7, 14, 26, 38, 57, 78, 102, 128, 165, 196, 240, 284, 329, 378, 440, 498, 571, 634, 704, 780, 875, 952, 1044, 1142, 1243, 1342, 1466, 1566, 1697, 1818, 1946, 2084, 2219, 2346, 2506, 2662, 2823, 2972, 3158, 3312, 3509, 3684, 3860, 4056, 4279, 4464, 4676

Offset: 1

Author

Darío Clavijo, Dec 05 2023

Keywords

• nonn

Comments

A000096(n-1) < a(n) < A367690(n).

Crossrefs

Cf. A000096, A000217, A049826, A107435, A367690, A367892.

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(j, n), j=1..n-1))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Dec 05 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[j, n], { j, 1, n - 1}]];
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: sum(A107435(y,x)+1 for x in range(1, n+1) for y in range(x+1, n+1))
print([a(n) for n in range(1, 50)])

Formula

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

a(n) = A367690(n) - A367892(n).

a(n) = A367892(n) + A000096(n).

a(n) = A000217(n-1) + Sum_{i=1..n} A049826(i).