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.

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

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• tabl

Comments

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

Number of squares in a greedy tiling of an n-by-k rectangle by squares. [David Radcliffe, Nov 14 2012]

Examples

			Rows:
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;
...
		

Links

• R. J. Mathar, Table of n, a(n) for n = 1..5050
• N. J. A. Sloane, Rows 1 through 100

Crossrefs

Cf. A049828.

Row sums give A049835.

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

Programs

Maple

A049834 := proc(n,k)
    local a,b,r,s ;
    a := n ;
    b := k ;
    r := 1;
    s := 0 ;
    while r > 0 do
        q := floor(a/b);
        r := a-b*q ;
        s := s+q ;
        a := b;
        b := r;
    end do:
    s ;
end proc: # R. J. Mathar, May 06 2016
# second Maple program:
T:= (n, k)-> add(i, i=convert(k/n, confrac)):
seq(seq(T(n, k), k=1..n), n=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], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 29 2020 *)

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