SquareNumber Difficult

Problem - 2816
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 $1, 2, 3, \cdots , 2007$?

Answer     992

If a positive integer is a multiple of $3$, then its square is a multiple of $9$, and so is the sum of the digits of its square.

If a positive integer is not a multiple of $3$, then its square is $1$ more than a multiple of $3$, and so is the sum of the digits of its square.

Therefore, we only need to study two categories of candidates.

The square of $\underbrace{9 \cdots 9}_{m}$ is $\underbrace{9\cdots 9}_{m-1}8\underbrace{0\cdots 0}_{m-1}1$. Its digit sum is $9m$. Therefore, all multiples of $9$ are good. There are $2007\div {9} = 223$ of them not exceeding $2007$.

The square of $\underbrace{3 \cdots 3}_{m}5$ is $\underbrace{1\cdots 1}_{m}\underbrace{2\cdots 2}_{m+1}5$ Its digit sum is $3m+7$. Since $1$ and $4$ are also good, all numbers $1$ more than a multiple of $3$ are good, and there are ${2007}\div{3} = 669$ of them.

Hence there are altogether $223 + 669 = \boxed{992}$ good numbers not exceeding $2007$.

report an error