|
|
A341100
|
|
Minimum number of base-2 rectangles needed to tile an n X n square.
|
|
0
|
|
|
1, 1, 4, 1, 4, 4, 9, 1, 4, 4, 9, 4, 9, 9, 13, 1, 4, 4, 9, 4, 9, 9, 15, 4, 9, 9, 16, 9, 16, 13, 17, 1, 4, 4, 9, 4, 9, 9, 16, 4, 9, 9, 16, 9, 16, 15, 19, 4, 9, 9, 16, 9, 16, 16, 20, 9, 16, 16, 20, 13, 20, 17, 21
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A base-2 rectangle is a rectangle whose dimensions are a power of 2.
|
|
LINKS
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|