A051010 Triangle T(m,n) giving of number of steps in the Euclidean algorithm for gcd(m,n) with 0<=m<n.

0, 0, 1, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 3, 2, 0, 1, 1, 1, 2, 2, 0, 1, 2, 2, 3, 3, 2, 0, 1, 1, 3, 1, 4, 2, 2, 0, 1, 2, 1, 2, 3, 2, 3, 2, 0, 1, 1, 2, 2, 1, 3, 3, 2, 2, 0, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2, 0, 1, 1, 1, 1, 3, 1, 4, 2, 2, 2, 2, 0, 1, 2, 2, 2, 4, 2, 3, 5, 3, 3, 3, 2, 0, 1, 1, 3, 2, 3, 2, 1, 3, 4, 3

Offset

1,6

Links

T. D. Noe, Rows n=1..100 of triangle, flattened

Eric Weisstein's World of Mathematics, Euclidean Algorithm.

Example

0,
0, 1,
0, 1, 2,
0, 1, 1, 2,
0, 1, 2, 3, 2,
0, 1, 1, 1, 2, 2,
0, 1, 2, 2, 3, 3, 2,
0, 1, 1, 3, 1, 4, 2, 2,
0, 1, 2, 1, 2, 3, 2, 3, 2,
0, 1, 1, 2, 2, 1, 3, 3, 2, 2,
0, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2,
0, 1, 1, 1, 1, 3, 1, 4, 2, 2, 2, 2,
0, 1, 2, 2, 2, 4, 2, 3, 5, 3, 3, 3, 2,
0, 1, 1, 3, 2, 3, 2, 1, 3, 4, 3, 4, 2, 2

Mathematica

t[m_, n_] := For[r[-1]=m; r[0]=n; k=1, True, k++, r[k] = Mod[r[k-2], r[k-1]]; If[r[k] == 0, Return[k-1]]]; Table[ t[m, n] , {n, 1, 14}, {m, 0, n-1}] // Flatten (* Jean-François Alcover, Oct 25 2012 *)

Prog

(Haskell)
a051010 n k = snd $ until ((== 0) . snd . fst)
                    (\((x, y), i) -> ((y, mod x y), i + 1)) ((n, k), 0)
a051010_row n = map (a051010 n) [0..n-1]
a051010_tabl = map a051010_row [1..]
-- Reinhard Zumkeller, Jun 27 2013

Crossrefs

Cf. A034883, A051011, A051012.

Cf. A049826.

Cf. A130130 (central terms).

Sequence in context: A048823 A173655 A025871 * A328342 A214269 A394018

Adjacent sequences: A051007 A051008 A051009 * A051011 A051012 A051013

Keyword

nonn,nice,tabl,changed

Author

Eric W. Weisstein

Status

approved