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!)
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 <a,b> of positive integers with a>=b, let <a^(1),b^(1)> = <max(a-b,b),min(a-b,b)>. 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<k, T[k, n], True, 1 + T[k, n-k]]; Table[T[n-k, k], {n, 2, 15}, {k, 1, n-1}] // Flatten (* Jean-Fran├žois Alcover, Nov 21 2016, adapted from PARI *)

PROG

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

CROSSREFS

Row sums are A072031. Cf. A049834 (the lower left triangle), A003989, A050873.

See also A267177, A267178, A267181.

Sequence in context: A237447 A338573 A113881 * A217029 A331886 A205456

Adjacent sequences:  A072027 A072028 A072029 * A072031 A072032 A072033

KEYWORD

nonn,tabl,easy,nice

AUTHOR

Michael Somos, Jun 07 2002

EXTENSIONS

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

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 April 12 21:47 EDT 2021. Contains 342933 sequences. (Running on oeis4.)