A049816 -id:A049816 - cp's OEIS frontend

A107435 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = length of Euclidean algorithm starting with n and k.

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, 3, 1, 4, 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, 3, 2, 3, 4, 4, 3, 2, 1, 1, 1, 1, 1, 3, 1, 4, 2, 2, 2, 2, 1, 1, 2, 2, 2, 4, 2, 3, 5, 3, 3, 3, 2, 1, 1, 1, 3, 2, 3, 2, 1, 3, 4, 3, 4, 2, 2, 1

Offset: 1

Philippe Deléham, Jun 09 2005

Consequence of theorem of Gabriel Lamé (1844): the first value of m in this triangle is T(F(m+2), F(m+1)) where F(n) = A000045(n); example: the first 5 is T(F(7), F(6)) = T(13, 8).
From Bernard Schott, May 01 2022: (Start)
Theorem of Gabriel Lamé (1844): The number of divisions necessary to find the greatest common divisor of two natural numbers n > k by means of the Euclidean algorithm is never greater than five times the number of digits of the smaller number k (see link).
This upper bound 5*length(k) is the best possible; the smallest pairs (n, k) for which T(n, k) = 5 * length(k) when length(k) = 1, 2 or 3 are respectively  (F(7), F(6)), (F(12), F(11)) and (F(17), F(16)) where F(n) = A000045(n). This upper bound is not attained when length(k) >= 4. (End)

			13 = 5*2 + 3, 5 = 3*1 + 2, 3 = 2*1 + 1, 2 = 2*1 + 0 = so that T(13,5) = 4.
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 3 1 4 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 3 2 3 4 4 3 2 1
  1 1 1 1 3 1 4 2 2 2 2 1
  1 2 2 2 4 2 3 5 3 3 3 2 1
  1 1 3 2 3 2 1 3 4 3 4 2 2 1
  1 2 1 3 1 2 2 3 3 2 4 2 3 2 1
  1 1 2 1 2 3 3 1 4 4 3 2 3 2 2 1
  1 2 3 2 3 3 3 2 3 4 4 4 3 4 3 2 1
  ..............................
Smallest examples with T(n, k) = 5 * length(k) (Theorem of Gabriel Lamé):
13 = 8*1 + 5, 8 = 5*1 + 3, 5 = 3*1 + 2, 3 = 2*1 + 1, 2 = 2*1 + 0 = so that T(13,8) = 5 = 5 * length(8).
144 = 89*1 + 55, 89 = 55*1 + 34, 55 = 34*1 + 21, 34 = 21*1 + 13, 21 = 13*1 + 8, then 5 steps already seen in the previous example, so that T(144,89) = 10 = 5 * length(89).
1597 = 987*1 + 610, 987 = 610*1 + 377, 610 = 377*1 + 233, 377 = 233*1 + 144, 233 = 144*1 + 89, then 10 steps already seen in the previous examples, so that T(1597,987) = 15 = 5 * length(987).

Ross Honsberger, Mathematical Gems II, Dolciani Mathematical Expositions No. 2, Mathematical Association of America, 1976, Chapter 7, A Theorem of Gabriel Lamé, pp. 54-57.
Wacław Sierpiński, Elementary Theory of Numbers, Theorem 12 (Lamé) p. 21, Warsaw, 1964.

Peter Kagey, Table of n, a(n) for n = 1..10000
Gabriel Lamé, Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers, Comptes rendus de l'Académie des sciences XIX, 1844, pages 867-870.
Wikipedia, Euclidean algorithm.
Wikipedia, Gabriel Lamé.

Cf. A000045, A001622, A002390, A034883, A049816, A051010, A055642.

F:= proc(n,k) option remember;
   if n mod k = 0 then 1
   else 1 + procname(k, n mod k)
   fi
end proc:
seq(seq(F(n,k),k=1..n), n=1..15); # Robert Israel, Feb 16 2016

T[n_, k_] := T[n, k] = If[Divisible[n, k], 1, 1 + T[k, Mod[n, k]]];
Table[T[n, k], {n, 1, 15}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 12 2019, after Robert Israel *)

T(n, k) = if ((n % k) == 0, 1, 1 + T(k, n % k)); \\ Michel Marcus, May 02 2022

T(n, k) = A049816(n, k) + 1.
From Robert Israel, Feb 16 2016: (Start)
T(n, k) = 1 if n == 0 (mod k), otherwise T(n, k) = 1 + T(k, (n mod k)).
G.f. G(x,y) of triangle satisfies G(x,y) = x*y/((1-x)*(1-x*y)) - Sum_{k>=1} (x^2*y)^k/(1-x^k) + Sum_{k>=1} G(x^k*y,x). (End)
From Bernard Schott, Apr 29 2022: (Start)
T(F(m+2), F(m+1)) = m where F(n) = A000045(n) (first comment).
T(n, k) <= 5 * length(k) where length(k) = A055642(k).
T(n, k) <= 1 + floor(log(k)/log(phi)) where log(phi) = A002390; the least numbers for which equality stands are when k and n are consecutive Fibonacci numbers. (End)

A049822 a(n) = 1 - tau(n) + Sum_{d|n} tau(d-1).

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 3, 2, 4, 4, 3, 4, 5, 4, 6, 5, 4, 6, 5, 6, 9, 6, 3, 6, 9, 7, 7, 8, 5, 10, 7, 6, 9, 7, 8, 11, 8, 6, 9, 10, 7, 12, 7, 8, 14, 8, 3, 10, 12, 13, 10, 11, 5, 10, 12, 12, 13, 8, 3, 14, 11, 8, 15, 11, 13, 16, 7, 9, 9, 14, 7, 14, 11, 9, 16, 12, 11, 15, 7, 14, 16, 11, 3, 18, 17, 10, 9, 12

Offset: 1

Clark Kimberling

Number of partitions of n into 3 summands 0 < a <= b <= c with b/a and c/b integers.

a(n) is the number of 1's in the n-th row of array T given by A049816. E.g., there are 5 numbers k from 1 to 13 for which the Euclidean algorithm on (13, k) has exactly 1 nonzero remainder; hence a(13) = 5.

			a(6) = 2 because of the 3 partitions of 6 into 3 parts, [4,1,1] and [2,2,2] meet the definition; [3,2,1] fails because 2 does not divide 3.
a(100) = 20 because there are 20 partitions of 100 in 3 summands 0 < a <= b <= c with integer b/a and c/b: {a, b, c} = {1, 1, 98}, {1, 3, 96}, {1, 9, 90}, {1, 11, 88}, {1, 33, 66}, {2, 2, 96}, {2, 14, 84}, {4, 4, 92}, {4, 8, 88}, {4, 12, 84}, {4, 16, 80}, {4, 24, 72}, {4, 32, 64}, {4, 48, 48}, {5, 5, 90}, {10, 10, 80}, {10, 30, 60}, {20, 20, 60}, {20, 40, 40}, {25, 25, 50}.

G. C. Greubel, Table of n, a(n) for n = 1..5000

Column 3 of A122934.
Cf. A000005, A003238, A057427.
Cf. A069905 (number of partitions of n into 3 positive parts).

a[n_] := 1 - DivisorSigma[0, n] + DivisorSum[n, If[# == 1, 0, DivisorSigma[ 0, # - 1]]& ]; Array[a, 90] (* Jean-François Alcover, Dec 02 2015 *)

a(n) = 1 - numdiv(n) + sumdiv(n, d, if (d==1, 0, numdiv(d-1))); \\ Michel Marcus, Oct 01 2013

Additional comments from Vladeta Jovovic, Aug 23 2003, Zak Seidov, Aug 31 2006 and Franklin T. Adams-Watters, Sep 20 2006

Edited by N. J. A. Sloane, Sep 21 2006

A049843 Triangular array T read by rows: T(n,k)=number of nonzero remainders when Euclidean algorithm acts on primes prime(n) and prime(k), k=1,2,...,n-1; n=2,3,4,...

Original entry on oeis.org

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

Offset: 2

Clark Kimberling

			Triangle begins:
  {1};
  {1,2};
  {1,1,2};
  ...
T(4,3)=2 since remainders for 7=prime(4) and 5=prime(3) are 2,1,0; to wit, 7=1*5+2, 5=2*2+1, 2=2*1+0.

Cf. A049816.

A060991 a(n) is the smallest positive integer c such that the equation A049820(x) = c has exactly n solutions.

Original entry on oeis.org

7, 2, 1, 6, 22, 838, 17638, 192520, 3240114, 219476872, 2146772872, 24443168392

Offset: 0

Labos Elemer, May 11 2001

Essentially same as A236565, except here for n=2 we have a(2) = 1 instead of A236565(2) = 0, because this sequence requires its terms to be strictly positive. - Antti Karttunen, Oct 09 2015

			The solution sets of smallest values of x-d(x) deviations with 1, 2, 3, 4, 5, 6 terms are as follows: {6}, {3, 4}, {9, 10, 12}, {25, 26, 28, 30}, {841, 842, 844, 848, 850}, {17642, 17648, 17650, 17654, 17658, 17670}. Thus difference x-d(x) for x={25, 26, 28, 30} with d(x)={3, 4, 6, 8} divisors is equally 22, so a(4)=22.

Cf. A000005, A049820, A045765, A049816, A236565.

s = Array[# - DivisorSigma[0, #] &, {20000}]; t = Length@ Position[s, #] & /@ Range@ Max@ s; Table[FirstPosition[t, n], {n, 0, 6}] // Flatten (* Michael De Vlieger, Oct 09 2015 *)

a(9)-a(11) from Donovan Johnson, Jan 08 2009

A375117 Irregular triangle of positive integers, read by rows, the elements of the n-th row being the nonzero remainders, in increasing order, when the Euclidean algorithm is applied to 2^n-1 and n.

Original entry on oeis.org

1, 1, 1, 3, 1, 3, 1, 1, 7, 1, 2, 7, 1, 3, 1, 3, 1, 1, 2, 3, 1, 7, 1, 15, 1, 9, 1, 5, 15, 7, 1, 3, 1, 3, 6, 9, 15, 1, 6, 1, 2, 3, 1, 2, 25, 1, 2, 13, 15, 1, 3, 1, 1, 31, 1, 2, 5, 7, 1, 3, 1, 17, 9, 27, 1, 1, 2, 3, 1, 3, 4, 7, 5, 10, 15, 1, 21, 1, 1, 14, 15, 1, 3, 13, 16

Offset: 2

Mike Jones, Jul 30 2024

			The triangle begins:
    1;
    1;
    1, 3;
    1;
    3;
    1;
    1, 7;
    1, 2, 7;
    1, 3;
    1;
    3;
    1;
    3;
    ...
Row(2) is {1}, because 2^2-1 = 4-1 = 3, and 3 divided by 2 leaves a remainder of 1.
Row(4) is {1, 3}, because 2^4-1 = 16-1 = 15, and 15 divided by 4 leaves a remainder of 3, and 4 divided by 3 leaves a remainder of 1.

Cf. A049816, A014491.

row(n) = my(x=2^n-1, y=n, ok=1, list=List()); while (ok, my(z=divrem(x, y)); x = y; y = z[2]; if (y==0, ok=0, listput(list, y));); listsort(list); Vec(list); \\ Michel Marcus, Jul 31 2024

More terms from Michel Marcus, Jul 31 2024

cp's OEIS Frontend

A107435 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = length of Euclidean algorithm starting with n and k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A049822 a(n) = 1 - tau(n) + Sum_{d|n} tau(d-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A049843 Triangular array T read by rows: T(n,k)=number of nonzero remainders when Euclidean algorithm acts on primes prime(n) and prime(k), k=1,2,...,n-1; n=2,3,4,...

Views

Author

Keywords

Examples

Crossrefs

A060991 a(n) is the smallest positive integer c such that the equation A049820(x) = c has exactly n solutions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A375117 Irregular triangle of positive integers, read by rows, the elements of the n-th row being the nonzero remainders, in increasing order, when the Euclidean algorithm is applied to 2^n-1 and n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Extensions