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