Which positive integers under 2007 are the digit-sum of a perfect square?

166 Views Asked by At

A positive integer $n$ is said to be good if there exists a perfect square whose sum of digits in base $10$ is equal to $n$. For instance, $13$ is good because $7^2=49$ and $4+9=13$. How many good numbers are among the list $\{1, 2, 3, \dotsc, 2007\}$?

I input all the numbers from $1$ to $2007$ into an Excel spreadsheet, squared all the numbers, split the squares into individual digits, added the digits and checked-off on the numbers which are repeating in the original list of numbers from $1$ to $2007$, and the sum of digits of the squares.

But this method takes too long. Is there a smarter way to answer this question?

1

There are 1 best solutions below

6
On

Remember the trick about casting out nines. Summing the digits of a number maintains the remainder on division by $9$. If we work $\bmod 9$ the only squares are $0,1,4,7$, so any number that is not equivalent to one of these will not have a square with that digit sum.

The next part is to show that any number of this form has a square with that digit sum. The sum of digits function is like a logarithm. It is at most $9$ times the number of digits of the original number. To get a digit sum of $2017$ you need a number with hundreds of digits, so I am sure you didn’t get close.

You can find patterns of numbers to handle whole classes of desired sums. If you square $10^k-1$, which is a number with $k\ 9's$ you get $10^{2k}-2\cdot 10^k+1,$ which has $k-1\ 9's,$ an $8,\ k-1 0$'s and a $1$ for a sum of $9k$. That covers all the multiples of $9$.