Selection of M square numbers to make a square

Question

I came across a question during an exam of computational mathematics to which I could think of no solution other than a brute force approach.

Given the squares of first 9 natural numbers, i.e $1,4,9,16,25,36,49,64,81$ select exactly $m$ squares such that the sum of the squares is a square number as well, if such a selection is possible. The selected squares should be minimum possible values and a square can be selected any number of times from 0 to m.

For example, if $m = 2$, the selected squares can be $9$ and $16$ as well as $36$ and $64$, but the answer will be $9$ and $16$ as it is the smallest possible selection. Similarly, if $m = 3$, a possible selection is $1,4,4$ where $4$ is selected twice.

Could someone please suggest the correct method of attempting such question mathematically, since m can be as large as $10^6$?

Answer 1

When m=2 you select 9 and 16. Otherwise You start answering this question by asking “what happens if I just select ones?” The sum you get is m. If m is a square, you just select ones and you’re done. Next you want to ask, “can I get to the next square converting ones to fours?” Each time you convert a one to a four, you raise the sum by three, and you normally have enough ones to get past the next square, and you so if the next square is a multiple of three away from m, then you convert ones to fours till you get the next square for your sum and you select those ones and four. If you’re next square isn’t a multiple of three away from n, you have to start considering nines. Converting a one to a nine increases your total by 8, since 8 doesn’t divide 3, you can use this to get your total to something that is a multiple of three less than the next square after it, and you can convert ones to fours to close the remaining gap. For m>64, the gaps between squares are quite large so there is enough room that nines can be used for either the next square or the one after it, so this method works optimally. For smaller m, it provides a decent bound which cuts down on the brute force work.

Answer 2

Brute force actually seems like a reasonable approach for this problem. Here are solutions up to $m=7$.

$$m=1:$$

Since you only need 1 square, any square will do, so choose 1 to keep it minimal.

$$m=2:$$

You are looking for Pythagorean Triples. The smallest is well-known to be $3^2+4^2=5^2$

$$m=3:$$

Try: $$\begin{align*}1+1+1 & = 3 \\ 1+1+4 & = 6 \\ 1+4+4 & =9=3^2\end{align*}$$ and in three tries, you find a solution.

$$m=4:$$

Try $1+1+1+1=4=2^2$ and in one try, you find a solution.

$$m=5:$$

Try $$\begin{align*}1+1+1+1+1 & = 5 \\ 1+1+1+1+4 & = 8 \\ 1+1+1+4+4 & = 11 \\ 1+1+4+4+4 & = 14 \\ 1+4+4+4+4 & = 17 \\ 4+4+4+4+4 & = 20 \\ 1+1+1+1+9 & = 13 \\ 1+1+1+4+9 & =16 = 4^2\end{align*}$$

That's only 8 tries.

$$m=6:$$

Try $$\begin{align*}1+1+1+1+1+1 & = 6 \\ 1+1+1+1+1+4 & = 9 = 3^2\end{align*}$$

Two tries.

$$m=7:$$

Try $$\begin{align*}1+1+1+1+1+1+1 & = 7 \\ 1+1+1+1+1+1+4 & = 10 \\ 1+1+1+1+1+4+4 & = 13 \\ 1+1+1+1+4+4+4 & = 16 = 4^2\end{align*}$$

4 tries.

Honestly, brute force seems like a pretty reasonable approach. You can find solutions relatively quickly every time.