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.

%I A107435 #68 May 06 2022 03:04:49
%S A107435 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 A107435 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 A107435 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 A107435 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = length of Euclidean algorithm starting with n and k.
%C A107435 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 A107435 From _Bernard Schott_, May 01 2022: (Start)
%C A107435 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 A107435 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 A107435 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 A107435 Wacław Sierpiński, Elementary Theory of Numbers, Theorem 12 (Lamé) p. 21, Warsaw, 1964.
%H A107435 Peter Kagey, <a href="/A107435/b107435.txt">Table of n, a(n) for n = 1..10000</a>
%H A107435 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 A107435 Wikipedia, <a href="https://en.wikipedia.org/wiki/Euclidean_algorithm">Euclidean algorithm</a>.
%H A107435 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gabriel_Lamé">Gabriel Lamé</a>.
%F A107435 T(n, k) = A049816(n, k) + 1.
%F A107435 From _Robert Israel_, Feb 16 2016: (Start)
%F A107435 T(n, k) = 1 if n == 0 (mod k), otherwise T(n, k) = 1 + T(k, (n mod k)).
%F A107435 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 A107435 From _Bernard Schott_, Apr 29 2022: (Start)
%F A107435 T(F(m+2), F(m+1)) = m where F(n) = A000045(n) (first comment).
%F A107435 T(n, k) <= 5 * length(k) where length(k) = A055642(k).
%F A107435 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 A107435 13 = 5*2 + 3, 5 = 3*1 + 2, 3 = 2*1 + 1, 2 = 2*1 + 0 = so that T(13,5) = 4.
%e A107435 Triangle begins:
%e A107435   1
%e A107435   1 1
%e A107435   1 2 1
%e A107435   1 1 2 1
%e A107435   1 2 3 2 1
%e A107435   1 1 1 2 2 1
%e A107435   1 2 2 3 3 2 1
%e A107435   1 1 3 1 4 2 2 1
%e A107435   1 2 1 2 3 2 3 2 1
%e A107435   1 1 2 2 1 3 3 2 2 1
%e A107435   1 2 3 3 2 3 4 4 3 2 1
%e A107435   1 1 1 1 3 1 4 2 2 2 2 1
%e A107435   1 2 2 2 4 2 3 5 3 3 3 2 1
%e A107435   1 1 3 2 3 2 1 3 4 3 4 2 2 1
%e A107435   1 2 1 3 1 2 2 3 3 2 4 2 3 2 1
%e A107435   1 1 2 1 2 3 3 1 4 4 3 2 3 2 2 1
%e A107435   1 2 3 2 3 3 3 2 3 4 4 4 3 4 3 2 1
%e A107435   ..............................
%e A107435 Smallest examples with T(n, k) = 5 * length(k) (Theorem of Gabriel Lamé):
%e A107435 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 A107435 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 A107435 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 A107435 F:= proc(n,k) option remember;
%p A107435    if n mod k = 0 then 1
%p A107435    else 1 + procname(k, n mod k)
%p A107435    fi
%p A107435 end proc:
%p A107435 seq(seq(F(n,k),k=1..n), n=1..15); # _Robert Israel_, Feb 16 2016
%t A107435 T[n_, k_] := T[n, k] = If[Divisible[n, k], 1, 1 + T[k, Mod[n, k]]];
%t A107435 Table[T[n, k], {n, 1, 15}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Apr 12 2019, after _Robert Israel_ *)
%o A107435 (PARI) T(n, k) = if ((n % k) == 0, 1, 1 + T(k, n % k)); \\ _Michel Marcus_, May 02 2022
%Y A107435 Cf. A000045, A001622, A002390, A034883, A049816, A051010, A055642.
%K A107435 nonn,tabl
%O A107435 1,5
%A A107435 _Philippe Deléham_, Jun 09 2005