|
%I #17 Feb 06 2021 14:13:58
%S 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,
%T 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,
%U 13,20,17,21
%N Minimum number of base-2 rectangles needed to tile an n X n square.
%C A base-2 rectangle is a rectangle whose dimensions are a power of 2.
%H ali, <a href="https://math.stackexchange.com/questions/3173523/tiling-a-square-with-rectangles">Tiling a square with rectangles</a>, Mathematics StackExchange, 2019.
%H Dmitry Kamenetsky, <a href="https://puzzling.stackexchange.com/questions/107116/covering-a-15x15-grid-with-rectangles">Covering a 15x15 grid with rectangles</a>, Puzzling StackExchange, 2021.
%F a(n) <= f(n)^2, where f(n) is the number of 1's in the binary representation of n (A000120).
%F a(n * 2^k) = a(n) for k >= 0.
%e 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:
%e 1 1 1 1 2
%e 1 1 1 1 2
%e 1 1 1 1 2
%e 1 1 1 1 2
%e 3 3 3 3 4
%e 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:
%e A A A A B B C 1 1 1 1 1 1 1 1
%e A A A A B B C 1 1 1 1 1 1 1 1
%e A A A A B B C 1 1 1 1 1 1 1 1
%e A A A A B B C 1 1 1 1 1 1 1 1
%e A A A A B B C 2 2 2 2 2 2 2 2
%e A A A A B B C 2 2 2 2 2 2 2 2
%e A A A A B B C 3 3 3 3 3 3 3 3
%e A A A A B B C 0 X Y Y Z Z Z Z
%e 7 7 7 7 7 7 7 7 X Y Y Z Z Z Z
%e 8 8 8 8 8 8 8 8 X Y Y Z Z Z Z
%e 8 8 8 8 8 8 8 8 X Y Y Z Z Z Z
%e 9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
%e 9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
%e 9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
%e 9 9 9 9 9 9 9 9 X Y Y Z Z Z Z
%Y Cf. A000120.
%K nonn
%O 1,3
%A _Dmitry Kamenetsky_, Feb 05 2021
|
