A072030 Array read by antidiagonals: T(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) where n >= 1, k >= 1.

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, 8, 3, 2, 6, 4, 8, 14

Offset: 1

Author

Michael Somos, Jun 07 2002

Keywords

• nonn
• tabl
• easy
• nice

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

Examples

			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;
  ...
		

Links

• T. D. Noe, Antidiagonals 1..49, flattened
• James C. Alexander, The Entropy of the Fibonacci Code (1989).

Crossrefs

Antidiagonal sums are A072031.

Cf. A049834 (the lower left triangle), A003989, A050873.

See also A267177, A267178, A267181.

Programs

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
# second Maple program:
A:= (n, k)-> add(i, i=convert(k/n, confrac)):
seq(seq(A(n, 1+d-n), n=1..d), d=1..14);  # Alois P. Heinz, Jan 31 2023

Mathematica

T[n_, k_] := T[n, k] = Which[n<1 || k<1, 0, n==k, 1, nJean-François Alcover, Nov 21 2016, adapted from PARI *)

PARI

T(n, k) = if( n<1 || k<1, 0, if( n==k, 1, if( n
				

Extensions

Definition and Comments revised by N. J. A. Sloane, Jan 14 2016