%I #68 May 06 2022 03:04:49

%S 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,

%T 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,

%U 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

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

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

%C From _Bernard Schott_, May 01 2022: (Start)

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

%C 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)

%D 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.

%D Wacław Sierpiński, Elementary Theory of Numbers, Theorem 12 (Lamé) p. 21, Warsaw, 1964.

%H Peter Kagey, <a href="/A107435/b107435.txt">Table of n, a(n) for n = 1..10000</a>

%H Gabriel Lamé, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k2978z/f867.item">Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers</a>, Comptes rendus de l'Académie des sciences XIX, 1844, pages 867-870.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Euclidean_algorithm">Euclidean algorithm</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Gabriel_Lamé">Gabriel Lamé</a>.

%F T(n, k) = A049816(n, k) + 1.

%F From _Robert Israel_, Feb 16 2016: (Start)

%F T(n, k) = 1 if n == 0 (mod k), otherwise T(n, k) = 1 + T(k, (n mod k)).

%F 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)

%F From _Bernard Schott_, Apr 29 2022: (Start)

%F T(F(m+2), F(m+1)) = m where F(n) = A000045(n) (first comment).

%F T(n, k) <= 5 * length(k) where length(k) = A055642(k).

%F 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)

%e 13 = 5*2 + 3, 5 = 3*1 + 2, 3 = 2*1 + 1, 2 = 2*1 + 0 = so that T(13,5) = 4.

%e Triangle begins:

%e 1

%e 1 1

%e 1 2 1

%e 1 1 2 1

%e 1 2 3 2 1

%e 1 1 1 2 2 1

%e 1 2 2 3 3 2 1

%e 1 1 3 1 4 2 2 1

%e 1 2 1 2 3 2 3 2 1

%e 1 1 2 2 1 3 3 2 2 1

%e 1 2 3 3 2 3 4 4 3 2 1

%e 1 1 1 1 3 1 4 2 2 2 2 1

%e 1 2 2 2 4 2 3 5 3 3 3 2 1

%e 1 1 3 2 3 2 1 3 4 3 4 2 2 1

%e 1 2 1 3 1 2 2 3 3 2 4 2 3 2 1

%e 1 1 2 1 2 3 3 1 4 4 3 2 3 2 2 1

%e 1 2 3 2 3 3 3 2 3 4 4 4 3 4 3 2 1

%e ..............................

%e Smallest examples with T(n, k) = 5 * length(k) (Theorem of Gabriel Lamé):

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

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

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

%p F:= proc(n,k) option remember;

%p if n mod k = 0 then 1

%p else 1 + procname(k, n mod k)

%p fi

%p end proc:

%p seq(seq(F(n,k),k=1..n), n=1..15); # _Robert Israel_, Feb 16 2016

%t T[n_, k_] := T[n, k] = If[Divisible[n, k], 1, 1 + T[k, Mod[n, k]]];

%t Table[T[n, k], {n, 1, 15}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Apr 12 2019, after _Robert Israel_ *)

%o (PARI) T(n, k) = if ((n % k) == 0, 1, 1 + T(k, n % k)); \\ _Michel Marcus_, May 02 2022

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

%K nonn,tabl

%O 1,5

%A _Philippe Deléham_, Jun 09 2005