login
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.
1
0, 1, 1, 3, 2, 4, 3, 3, 4
OFFSET
1,4
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.
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.
EXAMPLE
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
CROSSREFS
KEYWORD
nonn,more
AUTHOR
EXTENSIONS
Edited by Peter Munn, Oct 04 2023
STATUS
approved