login
The OEIS is supported by the many generous donors to the OEIS 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. 15
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 (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
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
# 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, 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
Antidiagonal sums are A072031.
Cf. A049834 (the lower left triangle), A003989, A050873.
See also A267177, A267178, A267181.
Sequence in context: A368053 A338573 A113881 * A217029 A331886 A205456
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 09:59 EDT 2024. Contains 371268 sequences. (Running on oeis4.)