# Integer Sequence “sums of digits of squares”.

1. For all $n \in \mathbb{N}$ we define the function $\delta(n)=p$, where $p$ is sums of digits of $n^2$. For example if $n=17, \ n^2=289$, then $\delta(17)=2+8+9=19$.

2. Let $a_k$ is a monotonically increasing sequence of all positive integer numbers for which exist at least one $n(a_k) \in \mathbb{N}$ such that $\delta(n)=a_k$. And we define that $a_0=0$.

3. Find $a_{20122012}-?$.

This is a problem from my school math competition, and during this competition I found answer in the following way: simple calculations give us that $a_1=1, \ a_2=4, \ a_3=7, \ a_4=9, \ a_5=10, \ a_6=13, \ a_7=16, \ a_8=18, ...$. Then I notice that $a_4=a_0+9, a_5=a_1+9, a_6=a_2+9 ...$ so I guessed that for this sequence $a_{k+4}=a_{k}+9$. And this give us a very simple solution: if $k=4m+r$, where $r:\{0,1,2,3\}$ then $a_k=9m+a_r$. But I wasn't able to prove the main formula $a_{k+4}=a_{k}+9$ and lost some points because they said that it is not hard. But I still can't find the way how to prove it. So my

Question is: Is there exist a simple and nice way to prove that for this sequence $a_{k+4}=a_{k}+9$ - ? I guess that it is a well known problem. But is there some elementary solution?

-
This sequence is shown in oeis.org/A056991, where it states the series is as you say. These are the numbers of digital root $1,4,7,$ or $9$, which are the only digital roots that squares can have. No proof is given that all these numbers appear. – Ross Millikan Aug 16 '12 at 20:13
Do I understand correctly Your comment "there is no proof for this recursive formula in the general case" ? – Mike Aug 16 '12 at 20:21
As I understand You and what I read from your link: You say, that no proof is given, that for all numbers from this sequence exist at least one $n(a_k) \in \mathbb{N}$ such that $\delta(n)=a_k$. So this means, that this problem doesn't have solution in general case? That is, I was tricked :/. – Mike Aug 16 '12 at 20:41
Only that no proof is given in the OEIS. I am sure there is one, but don't see how to prove it right now. – Ross Millikan Aug 16 '12 at 20:44
Ok, hope you are right. Thank you! – Mike Aug 16 '12 at 20:47

$\delta(9)=9$, $\delta(99)=18$, $\delta(999)=27$, etc., shows you get every number with digital root 0.
$\delta(49)=7$, $\delta(499)=16$, $\delta(4999)=25$, etc, shows you get every number with digital root 7.
$\delta(8)=10$, $\delta(98)=19$, $\delta(998)=28$, etc., shows you get every number with digital root 1.
$\delta(7)=13$, $\delta(97)=22$, $\delta(997)=31$, etc., finishes the problem off.