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,3

Comments

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

Links

Table of n, a(n) for n=1..63.

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

Cf. A000120.

Sequence in context: A144034 A366887 A204714 * A350639 A347264 A328147

Adjacent sequences: A341097 A341098 A341099 * A341101 A341102 A341103

Keyword

nonn

Author

Dmitry Kamenetsky, Feb 05 2021

Status

approved