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

%I #56 Jan 31 2023 08:00:50

%S 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,

%T 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,

%U 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

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

%C 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.]

%C For example <11,3> -> <8,3> -> <5,3> -> <3,2> -> <2,1> -> <1,1> -> <1,0> takes 6 steps.

%C 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.

%C 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.

%C 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

%H T. D. Noe, <a href="/A072030/b072030.txt">Antidiagonals 1..49, flattened</a>

%H James C. Alexander, <a href="http://web.archive.org/web/20030625141534/http://www.cwru.edu/artsci/math/alexander/pdf/fib.pdf">The Entropy of the Fibonacci Code</a> (1989).

%e The array begins:

%e 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

%e 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, ...

%e 3, 3, 1, 4, 4, 2, 5, 5, 3, 6, ...

%e 4, 2, 4, 1, 5, 3, 5, 2, 6, 4, ...

%e 5, 4, 4, 5, 1, 6, 5, 5, 6, 2, ...

%e 6, 3, 2, 3, 6, 1, 7, 4, 3, 4, ...

%e 7, 5, 5, 5, 5, 7, 1, 8, 6, 6, ...

%e 8, 4, 5, 2, 5, 4, 8, 1, 9, 5, ...

%e 9, 6, 3, 6, 6, 3, 6, 9, 1, 10, ...

%e 10, 5, 6, 4, 2, 4, 6, 5, 10, 1, ...

%e ...

%e The first few antidiagonals are:

%e 1;

%e 2, 2;

%e 3, 1, 3;

%e 4, 3, 3, 4;

%e 5, 2, 1, 2, 5;

%e 6, 4, 4, 4, 4, 6;

%e 7, 3, 4, 1, 4, 3, 7;

%e 8, 5, 2, 5, 5, 2, 5, 8;

%e 9, 4, 5, 3, 1, 3, 5, 4, 9;

%e 10, 6, 5, 5, 6, 6, 5, 5, 6, 10;

%e ...

%p A072030 := proc(n,k)

%p option remember;

%p if n < 1 or k < 1 then

%p 0;

%p elif n = k then

%p 1 ;

%p elif n < k then

%p procname(k,n) ;

%p else

%p 1+procname(k,n-k) ;

%p end if;

%p end proc:

%p seq(seq(A072030(d-k,k),k=1..d-1),d=2..12) ; # _R. J. Mathar_, May 07 2016

%p # second Maple program:

%p A:= (n, k)-> add(i, i=convert(k/n, confrac)):

%p seq(seq(A(n, 1+d-n), n=1..d), d=1..14); # _Alois P. Heinz_, Jan 31 2023

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

%o (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))))

%Y Antidiagonal sums are A072031.

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

%Y See also A267177, A267178, A267181.

%K nonn,tabl,easy,nice

%O 1,2

%A _Michael Somos_, Jun 07 2002

%E Definition and Comments revised by _N. J. A. Sloane_, Jan 14 2016