login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A107435 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = length of Euclidean algorithm starting with n and k. 8
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,5
COMMENTS
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)
REFERENCES
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.
LINKS
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, Gabriel Lamé.
FORMULA
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)
EXAMPLE
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).
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) T(n, k) = if ((n % k) == 0, 1, 1 + T(k, n % k)); \\ Michel Marcus, May 02 2022
CROSSREFS
Sequence in context: A353854 A217467 A268057 * A196056 A161095 A276162
KEYWORD
nonn,tabl
AUTHOR
Philippe Deléham, Jun 09 2005
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:31 EDT 2024. Contains 371240 sequences. (Running on oeis4.)