cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A051010 Triangle T(m,n) giving of number of steps in the Euclidean algorithm for gcd(m,n) with 0<=m

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 3, 2, 0, 1, 1, 1, 2, 2, 0, 1, 2, 2, 3, 3, 2, 0, 1, 1, 3, 1, 4, 2, 2, 0, 1, 2, 1, 2, 3, 2, 3, 2, 0, 1, 1, 2, 2, 1, 3, 3, 2, 2, 0, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2, 0, 1, 1, 1, 1, 3, 1, 4, 2, 2, 2, 2, 0, 1, 2, 2, 2, 4, 2, 3, 5, 3, 3, 3, 2, 0, 1, 1, 3, 2, 3, 2, 1, 3, 4, 3
Offset: 1

Views

Author

Eric W. Weisstein

Keywords

Links

Crossrefs

Cf. A034883, A051011, A051012.
Cf. A049826.
Cf. A130130 (central terms).

Programs

  • Haskell
    a051010 n k = snd $ until ((== 0) . snd . fst)
                    (\((x, y), i) -> ((y, mod x y), i + 1)) ((n, k), 0)
a051010_row n = map (a051010 n) [0..n-1]
a051010_tabl = map a051010_row [1..]
-- Reinhard Zumkeller, Jun 27 2013
  • Mathematica
    t[m_, n_] := For[r[-1]=m; r[0]=n; k=1, True, k++, r[k] = Mod[r[k-2], r[k-1]]; If[r[k] == 0, Return[k-1]]]; Table[ t[m, n] , {n, 1, 14}, {m, 0, n-1}] // Flatten (* Jean-François Alcover, Oct 25 2012 *)

A367690 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.

Original entry on oeis.org

1, 5, 14, 26, 47, 67, 100, 136, 177, 221, 286, 338, 415, 491, 568, 652, 761, 861, 990, 1098, 1219, 1351, 1520, 1652, 1813, 1985, 2162, 2334, 2555, 2727, 2960, 3172, 3397, 3641, 3878, 4098, 4383, 4659, 4944, 5204, 5537, 5805, 6158, 6466, 6775, 7123, 7524, 7848
Offset: 1

Views

Author

Darío Clavijo, Nov 26 2023

Keywords

Comments

The number of steps to calculate gcd(x,y) is A107435(x,y) for x<=y, and is the length of the continued fraction expansion of x/y (including 0 for the integer part).
A018806(n) <= a(n) <= A064951(n).

Links

Crossrefs

Cf. A018806, A049826, A064951, A107435.

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)+n+2*add(g(n, j), j=1..n-1))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 27 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] + n + 2*Sum[g[n, j], {j, 1, n-1}]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Apr 19 2025, after Alois P. Heinz *)
  • PARI
    A107435(n, k) = if (k == 0, 0, 1 + A107435(k, n % k));
a(n) = sum(x=1, n, sum(y=1, n, A107435(x,y)));
print(vector(49,n,a(n)));
  • Python
    from functools import cache
A107435 = lambda x,y: 0 if y == 0 else 1 + A107435(y, x % y)
A049826 = lambda n: sum(A107435(n,j) for j in range(1, n))
@cache
def a(n):
  # Code after Alois P. Heinz
  if n == 0: return 0
  return a(n-1) + n + A049826(n) * 2
print([a(n) for n in range(1,49)])

Formula

a(n) = a(n-1) + n + A049826(n) * 2 and a(1) = 1.
a(n) = a(n-1) + n + (Sum_{j=1..n-1} A107435(n,j)) * 2 and a(1) = 1.
a(n) = Sum_{x=1..n} Sum_{y=1..n} A107435(x,y). - Michel Marcus, Nov 28 2023

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.

Original entry on oeis.org

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

Views

Author

Darío Clavijo, Dec 04 2023

Keywords

Comments

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

Links

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

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.

Original entry on oeis.org

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

Views

Author

Darío Clavijo, Dec 05 2023

Keywords

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).
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.