login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 5
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

Theorem of Gabriel Lamé (1845) : 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).

LINKS

Peter Kagey, Table of n, a(n) for n = 1..10000

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)

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

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 *)

CROSSREFS

Cf. A034883, A049816, A051010.

Sequence in context: A335234 A217467 A268057 * A196056 A161095 A276162

Adjacent sequences:  A107432 A107433 A107434 * A107436 A107437 A107438

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 27 07:50 EDT 2021. Contains 346304 sequences. (Running on oeis4.)