cp's OEIS Frontend

A341100 Minimum number of base-2 rectangles needed to tile an n X n square.

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