|
|
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).
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
|
|
|
FORMULA
|
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)
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:
|
|
MATHEMATICA
|
T[n_, k_] := T[n, k] = If[Divisible[n, k], 1, 1 + T[k, Mod[n, k]]];
|
|
PROG
|
(PARI) T(n, k) = if ((n % k) == 0, 1, 1 + T(k, n % k)); \\ Michel Marcus, May 02 2022
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|