cp's OEIS Frontend

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).

%I A175039 #16 Dec 30 2022 06:35:33
%S A175039 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,
%T A175039 29,28
%N 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).
%C A175039 a(n) >= n, since the rightmost squares in each row must be covered by distinct tiles.
%C A175039 a(n) = n iff n = 2^k - 1.
%C A175039 a(n) = n+1 iff n = 2^k - 2^m - 1.
%C A175039 a(2*k) <= 2*a(k) + 1, a(2*k+1) <= 2*a(k) + 1 for k >= 1. - _Jinyuan Wang_, Jul 17 2019
%C A175039 a(n) <= A003817(n). - _Austin Shapiro_, Dec 29 2022
%H A175039 Canadian Mathematical Society, <a href="http://www.smc.math.ca/Competitions/CMO/exam/cmo2010.pdf">2010 Canadian Mathematical Olympiad, Problem 1</a>
%H A175039 C. Zhang, <a href="http://cyrilzhang.com/wp-content/uploads/2010/04/tilings.txt">Diagrams of tilings</a> [BROKEN LINK]
%e A175039 See link for diagrams of tilings.
%Y A175039 Solutions for a(n) = n: A000225. Solutions for a(n) = n+1: A030130, excluding 0.
%K A175039 nonn,more
%O A175039 1,2
%A A175039 _Cyril Zhang_, Apr 04 2010