cp's OEIS Frontend

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.

%I A049834 #37 Jan 31 2023 07:56:11
%S A049834 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 A049834 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 A049834 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 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.
%C A049834 First quotient=[ n/k ]=Q1; 2nd=[ k/(n-k*Q1) ]; ...
%C A049834 Number of squares in a greedy tiling of an n-by-k rectangle by squares. [_David Radcliffe_, Nov 14 2012]
%H A049834 R. J. Mathar, <a href="/A049834/b049834.txt">Table of n, a(n) for n = 1..5050</a>
%H A049834 N. J. A. Sloane, <a href="/A049834/a049834.txt">Rows 1 through 100</a>
%e A049834 Rows:
%e A049834 1;
%e A049834 2,1;
%e A049834 3,3,1;
%e A049834 4,2,4,1;
%e A049834 5,4,4,5,1;
%e A049834 6,3,2,3,6,1;
%e A049834 7,5,5,5,5,7,1;
%e A049834 ...
%p A049834 A049834 := proc(n,k)
%p A049834     local a,b,r,s ;
%p A049834     a := n ;
%p A049834     b := k ;
%p A049834     r := 1;
%p A049834     s := 0 ;
%p A049834     while r > 0 do
%p A049834         q := floor(a/b);
%p A049834         r := a-b*q ;
%p A049834         s := s+q ;
%p A049834         a := b;
%p A049834         b := r;
%p A049834     end do:
%p A049834     s ;
%p A049834 end proc: # _R. J. Mathar_, May 06 2016
%p A049834 # second Maple program:
%p A049834 T:= (n, k)-> add(i, i=convert(k/n, confrac)):
%p A049834 seq(seq(T(n, k), k=1..n), n=1..14);  # _Alois P. Heinz_, Jan 31 2023
%t A049834 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]];
%t A049834 Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Mar 29 2020 *)
%o A049834 (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 A049834 Cf. A049828.
%Y A049834 Row sums give A049835.
%Y A049834 This is the lower triangular part of the square array in A072030.
%K A049834 nonn,tabl
%O A049834 1,2
%A A049834 _Clark Kimberling_