OFFSET
1,3
COMMENTS
A base-2 rectangle is a rectangle whose dimensions are a power of 2.
LINKS
ali, Tiling a square with rectangles, Mathematics StackExchange, 2019.
Dmitry Kamenetsky, Covering a 15x15 grid with rectangles, Puzzling StackExchange, 2021.
FORMULA
a(n) <= f(n)^2, where f(n) is the number of 1's in the binary representation of n (A000120).
a(n * 2^k) = a(n) for k >= 0.
EXAMPLE
A 5 X 5 square can be covered with 4 such rectangles and this is the minimum, so a(5) = 4. Here is a possible covering:
1 1 1 1 2
1 1 1 1 2
1 1 1 1 2
1 1 1 1 2
3 3 3 3 4
n=15 is the smallest n where a(n) < f(n)^2, since a(15) = 13. Here is a possible covering found by Bubbler on Puzzling StackExchange:
A A A A B B C 1 1 1 1 1 1 1 1
A A A A B B C 1 1 1 1 1 1 1 1
A A A A B B C 1 1 1 1 1 1 1 1
A A A A B B C 1 1 1 1 1 1 1 1
A A A A B B C 2 2 2 2 2 2 2 2
A A A A B B C 2 2 2 2 2 2 2 2
A A A A B B C 3 3 3 3 3 3 3 3
A A A A B B C 0 X Y Y Z Z Z Z
7 7 7 7 7 7 7 7 X Y Y Z Z Z Z
8 8 8 8 8 8 8 8 X Y Y Z Z Z Z
8 8 8 8 8 8 8 8 X Y Y Z Z Z Z
9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
CROSSREFS
KEYWORD
nonn
AUTHOR
Dmitry Kamenetsky, Feb 05 2021
STATUS
approved