A049834 -id:A049834 - cp's OEIS frontend

A049835 a(n) = Sum_{k=1..n} T(n,k), array T as in A049834.

1, 3, 7, 11, 19, 21, 35, 37, 49, 53, 75, 65, 99, 93, 105, 115, 151, 127, 179, 153, 181, 193, 239, 191, 257, 249, 271, 261, 339, 263, 375, 329, 361, 373, 401, 351, 487, 441, 461, 427, 563, 443, 603, 517, 535, 585, 683, 533, 697, 619, 685, 661, 811, 657, 781, 711

Offset: 1

Clark Kimberling

nonn

Also the sum of all the partial quotients in the continued fraction for all rational k/n, for 1 <= k <= n. - Jeffrey Shallit, Jan 31 2023

C. Aistleitner, B. Borda, and M. Hauke, On the distribution of partial quotients of reduced fractions with fixed denominator, ArXiv preprint arXiv:2210.14095 [math.NT], October 25 2022.
M. Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Mag., 54 (1981), 60-63.
A. C. Yao and D. E. Knuth, Analysis of the subtractive algorithm for greatest common divisors, Proc. Nat. Acad. Sci. USA 72 (1975), 4720-4722.

Cf. A049834, A360264.

a:= n-> add(add(i, i=convert(k/n, confrac)), k=1..n):
seq(a(n), n=1..60);  # Alois P. Heinz, Jan 31 2023

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]];
a[n_] := Sum[T[n, k], {k, 1, n}];
Table[a[n], {n, 1, 56}] (* Jean-François Alcover, Jan 07 2025 *)

Yao and Knuth proved that a(n) is asymptotically (6/Pi)^2*n*(log n)^2. - Jeffrey Shallit, Jan 31 2023

A049836 a(n) = Sum_{m=1..n, k=1..m} T(m,k), array T as in A049834.

Original entry on oeis.org

1, 4, 11, 22, 41, 62, 97, 134, 183, 236, 311, 376, 475, 568, 673, 788, 939, 1066, 1245, 1398, 1579, 1772, 2011, 2202, 2459, 2708, 2979, 3240, 3579, 3842, 4217, 4546, 4907, 5280, 5681, 6032, 6519, 6960, 7421, 7848, 8411

Offset: 1

Clark Kimberling

nonn

Partial sums of A049835.

Cf. A049834.

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 2, 4, 1, 5, 4, 4, 5, 1, 6, 3, 2, 3, 5, 1, 7, 5, 5, 5, 5, 5, 1, 8, 4, 5, 2, 5, 4, 7, 1, 9, 6, 3, 6, 6, 3, 6, 7, 1, 10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1

Offset: 1

David Radcliffe, Nov 12 2012

Triangular array read by rows. m=1,2,...,n; n=1,2,3,...

			T(6,5) = 5 because a 6 X 5 rectangle can be subdivided into two 3 X 3 squares and three 2 X 2 squares.
Triangle begins:
   1;
   2, 1;
   3, 3, 1;
   4, 2, 4, 1;
   5, 4, 4, 5, 1;
   6, 3, 2, 3, 5, 1;
   7, 5, 5, 5, 5, 5, 1;
   8, 4, 5, 2, 5, 4, 7, 1;
   9, 6, 3, 6, 6, 3, 6, 7, 1;
  10, 5, 6, 4, 2, 4, 6, 5, 6, 1;
  11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1;
  12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1;
  13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1;
  14, 7, 7, 5, 7, 5, 2, 5, 7, 5, 7, 5, 7, 1;
  15, 9, 5, 7, 3, 4, 8, 8, 4, 3, 7, 5, 8, 7, 1;

Massimo Ortolano, Table of n, a(n) for n = 1..75466, rows 1..388 of triangle, flattened. Corrected version provided by Qizheng He.
Gary Antonick, Matt Enlow's Rectangle Division Puzzle, The New York Times, June 15, 2015.
Bertram Felgenhauer, Filling rectangles with integer-sided squares
Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.
M. Ortolano, M. Abrate, and L. Callegaro, On the synthesis of Quantum Hall Array Resistance Standards, arXiv preprint arXiv:1311.0756 [physics.ins-det], 2013.
Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921.

First 19 terms agree with A049834.
Columns m=1..10 give A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.
Cf. A113881, A338861.

A072030 Array read by antidiagonals: T(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) where n >= 1, k >= 1.

Original entry on oeis.org

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

Offset: 1

Michael Somos, Jun 07 2002

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  of positive integers with a>=b, let  = . 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

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

T. D. Noe, Antidiagonals 1..49, flattened
James C. Alexander, The Entropy of the Fibonacci Code (1989).

Antidiagonal sums are A072031.
Cf. A049834 (the lower left triangle), A003989, A050873.
See also A267177, A267178, A267181.

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

T[n_, k_] := T[n, k] = Which[n<1 || k<1, 0, n==k, 1, nJean-François Alcover, Nov 21 2016, adapted from PARI *)

T(n, k) = if( n<1 || k<1, 0, if( n==k, 1, if( n

Definition and Comments revised by N. J. A. Sloane, Jan 14 2016

A285721 Square array read by antidiagonals: A(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k, read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Original entry on oeis.org

0, 1, 1, 2, 0, 2, 3, 2, 2, 3, 4, 1, 0, 1, 4, 5, 3, 3, 3, 3, 5, 6, 2, 3, 0, 3, 2, 6, 7, 4, 1, 4, 4, 1, 4, 7, 8, 3, 4, 2, 0, 2, 4, 3, 8, 9, 5, 4, 4, 5, 5, 4, 4, 5, 9, 10, 4, 2, 1, 4, 0, 4, 1, 2, 4, 10, 11, 6, 5, 5, 4, 6, 6, 4, 5, 5, 6, 11, 12, 5, 5, 3, 5, 3, 0, 3, 5, 3, 5, 5, 12, 13, 7, 3, 5, 1, 2, 7, 7, 2, 1, 5, 3, 7, 13, 14, 6, 6, 2, 6, 3, 5, 0, 5, 3, 6, 2, 6, 6, 14

Offset: 1

Antti Karttunen, May 03 2017

			The top left 18 X 18 corner of the array:
   0, 1, 2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 12, 13, 14, 15, 16, 17
   1, 0, 2, 1, 3, 2, 4, 3, 5,  4,  6,  5,  7,  6,  8,  7,  9,  8
   2, 2, 0, 3, 3, 1, 4, 4, 2,  5,  5,  3,  6,  6,  4,  7,  7,  5
   3, 1, 3, 0, 4, 2, 4, 1, 5,  3,  5,  2,  6,  4,  6,  3,  7,  5
   4, 3, 3, 4, 0, 5, 4, 4, 5,  1,  6,  5,  5,  6,  2,  7,  6,  6
   5, 2, 1, 2, 5, 0, 6, 3, 2,  3,  6,  1,  7,  4,  3,  4,  7,  2
   6, 4, 4, 4, 4, 6, 0, 7, 5,  5,  5,  5,  7,  1,  8,  6,  6,  6
   7, 3, 4, 1, 4, 3, 7, 0, 8,  4,  5,  2,  5,  4,  8,  1,  9,  5
   8, 5, 2, 5, 5, 2, 5, 8, 0,  9,  6,  3,  6,  6,  3,  6,  9,  1
   9, 4, 5, 3, 1, 3, 5, 4, 9,  0, 10,  5,  6,  4,  2,  4,  6,  5
  10, 6, 5, 5, 6, 6, 5, 5, 6, 10,  0, 11,  7,  6,  6,  7,  7,  6
  11, 5, 3, 2, 5, 1, 5, 2, 3,  5, 11,  0, 12,  6,  4,  3,  6,  2
  12, 7, 6, 6, 5, 7, 7, 5, 6,  6,  7, 12,  0, 13,  8,  7,  7,  6
  13, 6, 6, 4, 6, 4, 1, 4, 6,  4,  6,  6, 13,  0, 14,  7,  7,  5
  14, 8, 4, 6, 2, 3, 8, 8, 3,  2,  6,  4,  8, 14,  0, 15,  9,  5
  15, 7, 7, 3, 7, 4, 6, 1, 6,  4,  7,  3,  7,  7, 15,  0, 16,  8
  16, 9, 7, 7, 6, 7, 6, 9, 9,  6,  7,  6,  7,  7,  9, 16,  0, 17
  17, 8, 5, 5, 6, 2, 6, 5, 1,  5,  6,  2,  6,  5,  5,  8, 17,  0

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 antidiagonals of the array

One less than A072030.
Row 2 & column 2: A028242 (but with starting offset 1).
Row 3 & column 3 (from zero onward) seems to be A226576.
Cf. A003989, A285722, A285732.
Compare also to arrays A049834, A113881, A219158.

def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
for n in range(1, 21): print([A(n - k + 1, k) for k in range(1, n + 1)]) # Indranil Ghosh, May 03 2017

(define (A285721 n) (A285721bi (A002260 n) (A004736 n)))
(define (A285721bi row col) (cond ((= row col) 0) ((> row col) (+ 1 (A285721bi (- row col) col))) (else (+ 1 (A285721bi row (- col row))))))
;; Alternatively:
(define (A285721bi row col) (if (= row col) 0 (+ 1 (A285721bi (abs (- row col)) (min col row)))))
;; Another implementation, as an one-dimensional sequence:
(definec (A285721 n) (if (zero? (A285722 n)) 0 (+ 1 (A285721 (A285722 n)))))

If n = k, then A(n,k) = 0, if n > k, then A(n,k) = 1 + A(n-k,k), otherwise [when n < k], A(n,k) = 1 + A(n,k-n).
Or alternatively, when n <> k, A(n,k) = 1 + A(abs(n-k),min(n,k)).
A(n,k) = A072030(n,k)-1.
As an one-dimensional sequence:
a(n) = 0 if A285722(n) = 0, otherwise a(n) = 1 + a(A285722(n)). [Here A285722 is also used as an one-dimensional sequence.]

A267177 Irregular triangle read by rows: successive bottom and right-hand borders of the infinite square array in A072030 (which gives number of subtraction steps needed to compute GCD).

Original entry on oeis.org

1, 2, 1, 2, 3, 3, 1, 3, 3, 4, 2, 4, 1, 4, 2, 4, 5, 4, 4, 5, 1, 5, 4, 4, 5, 6, 3, 2, 3, 6, 1, 6, 3, 2, 3, 6, 7, 5, 5, 5, 5, 7, 1, 7, 5, 5, 5, 5, 7, 8, 4, 5, 2, 5, 4, 8, 1, 8, 4, 5, 2, 5, 4, 8, 9, 6, 3, 6, 6, 3, 6, 9, 1, 9, 6, 3, 6, 6, 3, 6, 9, 10, 5, 6, 4, 2, 4, 6, 5, 10, 1, 10, 5, 6, 4, 2, 4, 6, 5

Offset: 1

N. J. A. Sloane, Jan 14 2016

Officially the borders are read starting at the bottom left, reading horizontally until the main diagonal is reached, and then reading vertically upwards until the top row is reached.

However, in this case both borders are symmetric about their midpoints, and the bottom border is the same as the right-hand border, so the direction in which the borders are read is less critical.

			The array in A072030 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 successive bottom and right-hand borders are:
  1,
  2, 1, 2,
  3, 3, 1, 3, 3,
  4, 2, 4, 1, 4, 2, 4,
  5, 4, 4, 5, 1, 5, 4, 4, 5,
  6, 3, 2, 3, 6, 1, 6, 3, 2, 3, 6,
  7, 5, 5, 5, 5, 7, 1, 7, 5, 5, 5, 5, 7,
  ...

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

Cf. A072030, A049834, A267178 (parity).

A267177 := proc(n,k)
    if k <= n then
        A072030(n,k) ;
    else
        A072030(2*n-k,n) ;
    end if;
end proc:
seq(seq(A267177(n,k),k=1..2*n-1),n=1..10) ; # R. J. Mathar, May 07 2016

A072030[n_, k_] := A072030[n, k] = Which[n < 1 || k < 1, 0, n == k, 1, n < k, A072030[k, n], True, 1+A072030[k, n-k]];
A267177[n_, k_] := If[k <= n, A072030[n, k], A072030[2n-k, n]];
Table[A267177[n, k], {n, 1, 10}, {k, 1, 2n-1}] // Flatten (* Jean-François Alcover, Apr 23 2023, after R. J. Mathar *)

\\ Based on Michel Marcus's program for A049834.
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, ", "); );
for (k=1, n-1, a = n; b = n-k; r = 1; s = 0; while (r, q = a\b; r = a - b*q; s += q; a = b; b = r); print1(s, ", "); );
print(); ); }
tabl(12)

cp's OEIS Frontend

A049835 a(n) = Sum_{k=1..n} T(n,k), array T as in A049834.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A049836 a(n) = Sum_{m=1..n, k=1..m} T(m,k), array T as in A049834.

Views

Author

Keywords

Crossrefs

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A072030 Array read by antidiagonals: T(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) where n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A285721 Square array read by antidiagonals: A(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k, read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Scheme

Formula

A267177 Irregular triangle read by rows: successive bottom and right-hand borders of the infinite square array in A072030 (which gives number of subtraction steps needed to compute GCD).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI