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

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

Offset: 1

Author

Dmitry Kamenetsky, Feb 05 2021

Keywords

• nonn

Comments

A base-2 rectangle is a rectangle whose dimensions are a power of 2.

Examples

			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
		

Links

• ali, Tiling a square with rectangles, Mathematics StackExchange, 2019.
• Dmitry Kamenetsky, Covering a 15x15 grid with rectangles, Puzzling StackExchange, 2021.

Crossrefs

Cf. A000120.

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.