A175039 Minimum number of integer-sided squares needed to tile an n-row staircase (a figure with n unit squares in the n-th row, and the leftmost squares of each row vertically aligned).

1, 3, 3, 7, 6, 7, 7, 11, 12, 13, 12, 15, 14, 15, 15, 20, 20, 23, 22, 23, 24, 25, 24, 29, 28, 29, 28

Offset: 1

Author

Cyril Zhang, Apr 04 2010

Keywords

• nonn
• more

Comments

a(n) >= n, since the rightmost squares in each row must be covered by distinct tiles.

a(n) = n iff n = 2^k - 1.

a(n) = n+1 iff n = 2^k - 2^m - 1.

a(2*k) <= 2*a(k) + 1, a(2*k+1) <= 2*a(k) + 1 for k >= 1. - Jinyuan Wang, Jul 17 2019

a(n) <= A003817(n). - Austin Shapiro, Dec 29 2022

Examples

			See link for diagrams of tilings.
		

Links

• Canadian Mathematical Society, 2010 Canadian Mathematical Olympiad, Problem 1
• C. Zhang, Diagrams of tilings [BROKEN LINK]

Crossrefs

Solutions for a(n) = n: A000225. Solutions for a(n) = n+1: A030130, excluding 0.