A365236 a(n) is the least number of integer-sided squares that can be packed together with the n squares 1 X 1, 2 X 2, ..., n X n to fill out a rectangle.

0, 1, 1, 3, 2, 4, 3, 3, 4

Offset: 1

Author

Tamas Sandor Nagy and Thomas Scheuerle, Sep 25 2023

Keywords

• nonn
• more

Comments

Warning: several terms are provisional as their intended verification effectively assumed the augmenting squares were not larger than n X n. - Peter Munn, Oct 02 2023

The definition does not exclude squares larger than n X n.

Terms for n < 10 were verified by the use of a program.

a(10) <= 5.

Examples

			Compositions of rectangles that satisfy the minimal number of augmenting squares for n. Where more than one minimal composition exists for a given n, the table shows a single example. In the table body, the numbers include both the specific mandatory and augmenting squares. a(n) is the total number of squares in the rectangle minus n.
           | 1^2   2^2   3^2   4^2   5^2   6^2   7^2   8^2   9^2  10^2 | Total
  ----------------------------------------------------------------------------
  a(1) = 0 |  1                                                        |   1
  a(2) = 1 |  2     1                                                  |   3
  a(3) = 1 |  2     1     1                                            |   4
  a(4) = 3 |  2     1     2     2                                      |   7
  a(5) = 2 |  2     1     1     2     1                                |   7
  a(6) = 4 |  2     1     3     2     1     1                          |  10
  a(7) = 3 |  1     1     1     3     1     2     1                    |  10
  a(8) = 3 |  3     2     1     1     1     1     1     1              |  11
  a(9) = 4 |  2     2     2     2     1     1     1     1     1        |  13
		

Links

• Tamas Sandor Nagy, Examples for a(1) - a(4).
• Tamas Sandor Nagy, Example for a(5).
• Tamas Sandor Nagy, Example for a(6).
• Tamas Sandor Nagy, Original upper bound examples for a(7) with 5 augmenting squares and a(8) with 6 augmenting squares.
• Tamas Sandor Nagy, Example of a conjectured solution for a(10) with 5 augmenting squares, found by Peter Munn.
• Thomas Scheuerle, Example for a(6) with smallest possible area.
• Thomas Scheuerle, Example for a(7).
• Thomas Scheuerle, Example for a(8).
• Thomas Scheuerle, Example for a(9).
• Thomas Scheuerle, Original upper bound example for a(10) with 6 augmenting squares.
• Thomas Scheuerle, Example for a(11) = 4 this is at the same time also a conjectured solution for a(10) = 5.

Crossrefs

Cf. A000290, A005670, A005842, A038666, A081287.

Formula

a(n) <= 1 + Sum_{k = 1 .. ceiling((n - 1)/2)} (n + (1 - k)*floor(n/k) - 2). This upper bound corresponds to placing the squares with length n up to n - floor((n - 1)/2) all in one row. The remaining mandatory squares will then fit naturally into the rectangle n X (1/2)*(2*n - ceiling((n - 1)/2))*(ceiling((n - 1)/2) + 1).

a(n) > a(n - 1) - 2.

Extensions

Edited by Peter Munn, Oct 04 2023