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

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]

Links

R. J. Mathar, Table of n, a(n) for n = 1..5050

N. J. A. Sloane, Rows 1 through 100

Example

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

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

Prog

(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

Crossrefs

Cf. A049828.

Row sums give A049835.

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

Sequence in context: A210216 A195915 A219158 * A134625 A325477 A277227

Adjacent sequences: A049831 A049832 A049833 * A049835 A049836 A049837

Keyword

nonn,tabl

Author

Clark Kimberling

Status

approved