A348133 Minimal number of horizontal and vertical lines needed to partition a square into rectangles which can be reassembled into n distinct squares.

3, 4, 5, 5, 6, 7, 7

Offset: 2

Author

Zhao Hui Du, Oct 01 2021

Keywords

• nonn
• hard
• more

Comments

For n > 2 the values may only be upper bounds.

Examples

			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.
		

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

Extensions

Thanks to Jinyuan Wang for additional comments.