login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A049834 Triangular array T given by rows: T(n,k)=sum of quotients when Euclidean algorithm acts on n and k; for k=1,2,...,n; n=1,2,3,...; also number of subtraction steps when computing gcd(n,k) using subtractions rather than divisions. 6

%I

%S 1,2,1,3,3,1,4,2,4,1,5,4,4,5,1,6,3,2,3,6,1,7,5,5,5,5,7,1,8,4,5,2,5,4,

%T 8,1,9,6,3,6,6,3,6,9,1,10,5,6,4,2,4,6,5,10,1,11,7,6,6,7,7,6,6,7,11,1,

%U 12,6,4,3,6,2,6,3,4,6,12,1,13,8,7,7,6,8,8,6,7,7,8,13,1

%N Triangular array T given by rows: T(n,k)=sum of quotients when Euclidean algorithm acts on n and k; for k=1,2,...,n; n=1,2,3,...; also number of subtraction steps when computing gcd(n,k) using subtractions rather than divisions.

%C First quotient=[ n/k ]=Q1; 2nd=[ k/(n-k*Q1) ]; ...

%C Number of squares in a greedy tiling of an n-by-k rectangle by squares. [_David Radcliffe_, Nov 14 2012]

%H R. J. Mathar, <a href="/A049834/b049834.txt">Table of n, a(n) for n = 1..5050</a>

%H N. J. A. Sloane, <a href="/A049834/a049834.txt">Rows 1 through 100</a>

%e Rows:

%e 1;

%e 2,1;

%e 3,3,1;

%e 4,2,4,1;

%e 5,4,4,5,1;

%e 6,3,2,3,6,1;

%e 7,5,5,5,5,7,1;

%e ...

%p A049834 := proc(n,k)

%p local a,b,r,s ;

%p a := n ;

%p b := k ;

%p r := 1;

%p s := 0 ;

%p while r > 0 do

%p q := floor(a/b);

%p r := a-b*q ;

%p s := s+q ;

%p a := b;

%p b := r;

%p end do:

%p s ;

%p end proc: # _R. J. Mathar_, May 06 2016

%o (PARI) tabl(nn) = {for (n=1, nn, for (k=1, n, a = n; b = k; r = 1; s = 0; while (r, q = a\b; r = a - b*q; s += q; a = b; b = r); print1(s, ", ");); print(););} \\ _Michel Marcus_, Aug 17 2015

%Y Cf. A049828.

%Y This is the lower triangular part of the square array in A072030.

%K nonn,tabl

%O 1,2

%A _Clark Kimberling_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 20:17 EDT 2016. Contains 276522 sequences.