Squary Numbers

A number is said to be Squary if it can be partitioned in a way such that each partition is a perfect square. For example, the numbers 164 and 4036729 are Squary numbers because they can be partitioned into (1,64) or (16,4) and (4,0,36,729) respectively. However, the number 139 is not Squary. Let us see all the possible ways or partitioning 139 -

All possible ways of partitioning 139 -

(139)
(1,39)
(13,9)
(1,3,9)

Hence, 139 is not a Squary number.

As we can see in the above example, no case exits in which all the partitions are perfect squares.

Given a number N, can you efficiently find out if it is Squary or not? If it is Squary, can you give any one valid partitioning for this number?

View Solution: Solution to "Squary Numbers"