

A175039


Minimum number of integersided squares needed to tile an nrow staircase (a figure with n unit squares in the nth row, and the leftmost squares of each row vertically aligned).


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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


LINKS

Table of n, a(n) for n=1..27.
Canadian Mathematical Society, 2010 Canadian Mathematical Olympiad, Problem 1
C. Zhang, Diagrams of tilings [BROKEN LINK]


EXAMPLE

See link for diagrams of tilings.


CROSSREFS

Solutions for a(n) = n: A000225. Solutions for a(n) = n+1: A030130, excluding 0.
Sequence in context: A200690 A045773 A256700 * A222405 A146970 A078708
Adjacent sequences: A175036 A175037 A175038 * A175040 A175041 A175042


KEYWORD

nonn,more


AUTHOR

Cyril Zhang, Apr 04 2010


STATUS

approved



