The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A072030 Array read by antidiagonals: T(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) where n >= 1, k >= 1. 14
 1, 2, 2, 3, 1, 3, 4, 3, 3, 4, 5, 2, 1, 2, 5, 6, 4, 4, 4, 4, 6, 7, 3, 4, 1, 4, 3, 7, 8, 5, 2, 5, 5, 2, 5, 8, 9, 4, 5, 3, 1, 3, 5, 4, 9, 10, 6, 5, 5, 6, 6, 5, 5, 6, 10, 11, 5, 3, 2, 5, 1, 5, 2, 3, 5, 11, 12, 7, 6, 6, 5, 7, 7, 5, 6, 6, 7, 12, 13, 6, 6, 4, 6, 4, 1, 4, 6, 4, 6, 6, 13, 14, 8, 4, 6, 2, 3, 8 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS The old definition was: Triangle T(a,b) read by rows giving number of steps in simple Euclidean algorithm for gcd(a,b) (a > b >= 1). [For this, see A049834.] For example <11,3> -> <8,3> -> <5,3> -> <3,2> -> <2,1> -> <1,1> -> <1,0> takes 6 steps. The number of steps function can be defined inductively by T(a,b) = T(b,a), T(a,0) = 0, and T(a+b,b) = T(a,b)+1. The simple Euclidean algorithm is the Euclidean algorithm without divisions. Given a pair of positive integers with a>=b, let = . This is iterated until a^(m)=0. Then T(a,b) is the number of steps m. Note that row n starts at k = 1; the number of steps to compute gcd(n,0) or gcd(0,n) is not shown. - T. D. Noe, Oct 29 2007 LINKS T. D. Noe, Antidiagonals 1..49, flattened James C. Alexander, The Entropy of the Fibonacci Code (1989). EXAMPLE The array begins:    1,  2,  3,  4,  5,  6,  7,  8,  9, 10, ...    2,  1,  3,  2,  4,  3,  5,  4,  6,  5, ...    3,  3,  1,  4,  4,  2,  5,  5,  3,  6, ...    4,  2,  4,  1,  5,  3,  5,  2,  6,  4, ...    5,  4,  4,  5,  1,  6,  5,  5,  6,  2, ...    6,  3,  2,  3,  6,  1,  7,  4,  3,  4, ...    7,  5,  5,  5,  5,  7,  1,  8,  6,  6, ...    8,  4,  5,  2,  5,  4,  8,  1,  9,  5, ...    9,  6,  3,  6,  6,  3,  6,  9,  1, 10, ...   10,  5,  6,  4,  2,  4,  6,  5, 10,  1, ...   ... The first few antidiagonals are:    1;    2,  2;    3,  1,  3;    4,  3,  3,  4;    5,  2,  1,  2,  5;    6,  4,  4,  4,  4,  6;    7,  3,  4,  1,  4,  3,  7;    8,  5,  2,  5,  5,  2,  5,  8;    9,  4,  5,  3,  1,  3,  5,  4,  9;   10,  6,  5,  5,  6,  6,  5,  5,  6, 10;   ... MAPLE A072030 := proc(n, k)     option remember;     if n < 1 or k < 1 then         0;     elif n = k then         1 ;     elif n < k then         procname(k, n) ;     else         1+procname(k, n-k) ;     end if; end proc: seq(seq(A072030(d-k, k), k=1..d-1), d=2..12) ; # R. J. Mathar, May 07 2016 MATHEMATICA T[n_, k_] := T[n, k] = Which[n<1 || k<1, 0, n==k, 1, n

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.

Last modified April 12 21:47 EDT 2021. Contains 342933 sequences. (Running on oeis4.)