A107435 -id:A107435 - cp's OEIS frontend

A269267 Indices k such that A107435(k) != A268057(k).

31, 33, 59, 62, 71, 73, 83, 86, 94, 102, 109, 116, 126, 127, 129, 130, 142, 143, 146, 147, 158, 160, 164, 166, 176, 178, 179, 182, 183, 185, 193, 199, 201, 207, 218, 223, 236, 239, 245, 248, 257, 259, 261, 262, 263, 266, 267, 268, 270, 272, 281, 283, 285, 286

Offset: 1

Peter Kagey, Feb 24 2016

nonn

Peter Kagey, Table of n, a(n) for n = 1..10000

Complement of A269331.

Cf. A107435, A268057.

A269331 Indices k such that A107435(k) = A268057(k).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 60, 61, 63, 64, 65, 66, 67, 68, 69, 70, 72

Offset: 1

Peter Kagey, Feb 23 2016

nonn

Peter Kagey, Table of n, a(n) for n = 1..10000

Complement of A269267.

Cf. A107435, A268057.

A049816 Triangular array T read by rows: T(n,k) = number of nonzero remainders when Euclidean algorithm acts on n and k, for k=1..n, n>=1.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 1, 0, 0, 0, 2, 0, 3, 1, 1, 0, 0, 1, 0, 1, 2, 1, 2, 1, 0, 0, 0, 1, 1, 0, 2, 2, 1, 1, 0, 0, 1, 2, 2, 1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0, 2, 0, 3, 1, 1, 1, 1, 0, 0, 1, 1, 1, 3, 1, 2, 4, 2, 2, 2, 1, 0

Offset: 1

Clark Kimberling

			Triangle begins:
0,
0, 0,
0, 1, 0,
0, 0, 1, 0,
0, 1, 2, 1, 0,
0, 0, 0, 1, 1, 0,
0, 1, 1, 2, 2, 1, 0,
0, 0, 2, 0, 3, 1, 1, 0,
0, 1, 0, 1, 2, 1, 2, 1, 0,
0, 0, 1, 1, 0, 2, 2, 1, 1, 0,
0, 1, 2, 2, 1, 2, 3, 3, 2, 1, 0,
0, 0, 0, 0, 2, 0, 3, 1, 1, 1, 1, 0,
0, 1, 1, 1, 3, 1, 2, 4, 2, 2, 2, 1, 0,
...

Alois P. Heinz, Rows n = 1..200, flattened

Row sums give A049817.

T:= proc(x, y) option remember;
      `if`(y=0, -1, 1+T(y, irem(x, y)))
    end:
seq(seq(T(n, k), k=1..n), n=1..15);  # Alois P. Heinz, Nov 29 2023

R[n_, k_] := R[n, k] = With[{r = Mod[n, k]}, If[r == 0, 1, R[k, r] + 1]];
T[n_, k_] := R[n, k] - 1;
Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 12 2019, after Robert Israel in A107435 *)

A268057 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = number of iterations of A048158(n, A048158(n, ... A048158(n, k)...)) to reach 0.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 2, 1, 1, 1, 2, 1, 3, 2, 2, 1, 1, 2, 1, 2, 3, 2, 3, 2, 1, 1, 1, 2, 2, 1, 3, 3, 2, 2, 1, 1, 2, 3, 4, 2, 3, 5, 4, 3, 2, 1, 1, 1, 1, 1, 2, 1, 3, 2, 2, 2, 2, 1, 1, 2, 2, 2, 3, 2, 3, 4, 3

Offset: 1

Peter Kagey, Jan 25 2016

Each column is periodic: T(n+A003418(k),k) = T(n,k). - Robert Israel, Feb 02 2016

			T(5, 3) = 3 because the algorithm requires three steps to reach 0.
  5 % 3 = 2
  5 % 2 = 1
  5 % 1 = 0
Triangle begins:
  1
  1 1
  1 2 1
  1 1 2 1
  1 2 3 2 1
  1 1 1 2 2 1
  1 2 2 3 3 2 1
  1 1 2 1 3 2 2 1
  1 2 1 2 3 2 3 2 1
  1 1 2 2 1 3 3 2 2 1
  1 2 3 4 2 3 5 4 3 2 1
  1 1 1 1 2 1 3 2 2 2 2 1

Peter Kagey, Table of n, a(n) for n = 1..10000
"ModernModest", Reddit discussion

Cf. A003418, A048158, A107435, A268058, A268059, A268060.

T:= proc(n,k) option remember; local m;
     if k = 0 then 0 else 1 + procname(n,n mod k) fi
end proc:
seq(seq(T(n,k),k=1..n),n=1..30); # Robert Israel, Feb 02 2016

T[n_, k_] := T[n, k] = If[k == 0, 0, 1 + T[n, Mod[n, k]]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 30}] // Flatten (* Jean-François Alcover, Jan 31 2023, after Robert Israel *)

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

Darío Clavijo, Nov 26 2023

nonn

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

Project Euler, Problem 433: Steps in Euclid's Algorithm

Cf. A018806, A049826, A064951, A107435.

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

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 *)

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)));

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)])

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

Darío Clavijo, Dec 04 2023

nonn

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

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A049826, A107435, A367690.

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

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 *)

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)])

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

Darío Clavijo, Dec 05 2023

nonn

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

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

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

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 *)

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)])

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

cp's OEIS Frontend

A269267 Indices k such that A107435(k) != A268057(k).

Views

Author

Keywords

Links

Crossrefs

A269331 Indices k such that A107435(k) = A268057(k).

Views

Author

Keywords

Links

Crossrefs

A049816 Triangular array T read by rows: T(n,k) = number of nonzero remainders when Euclidean algorithm acts on n and k, for k=1..n, n>=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A268057 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = number of iterations of A048158(n, A048158(n, ... A048158(n, k)...)) to reach 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Python

Formula