login
A348133
Minimal number of horizontal and vertical lines needed to partition a square into rectangles which can be reassembled into n distinct squares.
1
3, 4, 5, 5, 6, 7, 7
OFFSET
2,1
COMMENTS
For n > 2 the values may only be upper bounds.
LINKS
Anonymous, Divide a square into several small squares. [A Chinese web site where the problem originated]
FORMULA
a(n) <= a(n-2) + 2.
a(k + m - 1) <= a(k) + a(m).
EXAMPLE
For example, we could use one horizontal line to cut one side of the square in the ratio 2:3 and then two vertical lines to cut another side in the ratio 1:1:3 to form 6 rectangles 1*3, 1*3, 3*3, 1*2, 1*2, 3*2. Then we can reassemble the rectangles into a 3*3 square and a 4*4 square. So a(2) = 3.
CROSSREFS
Sequence in context: A339362 A240676 A037038 * A278375 A106501 A374261
KEYWORD
nonn,hard,more
AUTHOR
Zhao Hui Du, Oct 01 2021
EXTENSIONS
Thanks to Jinyuan Wang for additional comments.
STATUS
approved