9

I have a very interesting number theory problem. Let $$ S_n $$ be a number consisting of only $$n$$ ones. For instance, $$S_1=1\\S_2=11 \\ S_4=1111$$ The problem is to prove that the sum of the digits of $$S^2_n$$ can be calculated using the formula $$81\cdot \left( \left\lfloor \frac{n}{9} \right\rfloor + \left( \frac{n}{9} - \left\lfloor \frac{n}{9} \right\rfloor \right)^2 \right)$$

I would be very grateful for help. I don't even know how to start...

awllower
  • 16,536
xan
  • 1,443
  • 1
  • 21
  • 28
  • @xan: My answer may actually contain too many hints - sorry about that. Before you study it, please try the following: compare e.g. the pairs $S_{14}^2$ vs. $S_5^2$, and $S_{16}^2$ vs. $S_7^2$ with the aid of a computer (or Wolfram Alpha). Generate more such pairs, and... – Jyrki Lahtonen Feb 24 '12 at 19:17
  • @Jyrki Lahtonen no problem. I'm not as smart as I'd like to be and it's still very difficult for me. Thank you very much for hints, I'm going to study them hard in the near future but I don't exclude the option, I will have to ask about something. Identities in 2 and 4 are definitely not trivial for me.

    Sorry for my English, I'm still working on it.

     – xan Feb 24 '12 at 22:26
  • @xan: My hint #4 is really a translation of the pattern that you see, when you compare, e.g. $S_6^2$ to $S_{15}^2$ and slide the former 9 positions to the left. I was a little bit surprised that you accepted my answer, because I rather suspect that an easier to follow solution is out there :-) One that comes grade school multiplication or something? – Jyrki Lahtonen Feb 25 '12 at 06:00
  • Firstly I have tried grade school multiplication but it was hard with calculations and I thought that this way will not lead me to solve this problem and will only frustrate me. – xan Feb 25 '12 at 13:51

2 Answers2

7

A nice problem!

Hints:

  1. Let $n=9q+r$ with $0\le r <9$. Show that the claimed formula gives $$ D_n=81q+r^2 $$ for the sum of digits $D_n$ of $S_n^2$.
  2. Therefore it suffices to check the formula for $n=1,2,\ldots,9$, and to show that for all $n$ we have the recurrence relation $$ D_{n+9}=D_n+81. $$
  3. For $n\le9$ verify the formula using the grade school multiplication. Observe that there will be no carry for these small values of $n$.
  4. Verify the identity $$ S_{n+9}^2=10^9S_n^2+\frac{10^{2n+18}-10^{2n+9}}{81}-\frac{10^9-1}{81}. $$ Here the factor $10^9$ has a predictable effect on the sum of digits, and the remaining task is to check that the two additional terms give the desired contribution. There is some work to be done there, but not an awful lot, if you notice that $$ \frac{10^9-1}{81}=12345679. $$
Jyrki Lahtonen
  • 133,153
  • But another approach may lead to a cleaner solution. First I tried to calculate the total carry... – Jyrki Lahtonen Feb 24 '12 at 18:52
  • Won't there be an overlap between $10^9 S_n^2$ and the middle term? – Aryabhata Feb 24 '12 at 19:07
  • @Aryabhata: No. The middle term is divisible by $10^{2n+9}$, and is thus `safely' larger than $10^9S_n^2$. The last term affects the least significant non-zero digit of $10^9S_n^2$, but the effect is easy to analyze. – Jyrki Lahtonen Feb 24 '12 at 19:11
  • I see. Nice :-) (you have my +1 already, in case you are wondering :-)) – Aryabhata Feb 24 '12 at 19:16
  • OK, I finally understand the whole structure of this proof. I am very happy, because now the problem seems to be much more fun :-) I have generated over a dozen of $S^2_n$ and I found the relation between $S^2_n$ and $S^2_{n+9}$. I also prooved this: $S^2_{n+9}=10^9 S_n + \frac{10^9-1}{81}(10^{2n+9}-1)$ but still don't know how extract from this the sum of digits relation. It is obvious that sum of digits of $10^9 S_n$ and $S_n$ is equal but despite I know what $\frac{10^9-1}{81}(10^{2n+9}-1)$ do for this number, I don't know how does this affect the sum of digits. – xan Feb 25 '12 at 13:46
  • I don't know how to formally come to this sum of digits relation (because it is clear when I look at this numbers but I don't know how to formally justify it). You have helped me so much and I am very grateful, but I have to ask for help again (I hope the last time) :-) – xan Feb 25 '12 at 13:54
  • OK. got it :-) After careful analysis of numbers $S^2_{n+9}$ and $S^2_n$ I deduced formula from your #4 hint! Now justification of hint #2 is very simple. Thank you very very much! Your help and way to solve it was awesome :-) – xan Feb 25 '12 at 17:05
  • Well, done @xan ! I missed most of today in a bridge tournament, but you seem to have managed just fine :-) – Jyrki Lahtonen Feb 25 '12 at 17:54
  • It's because of your great hints :-) As I mentioned, I'm not as good as I would like to be and it took me a lot of time, but now I understand very well this problem, everything is clear to me. I can describe solution in a completely precise way.

    I had a lot of fun while solving it, love this feeling :-)

     – xan Feb 25 '12 at 18:25
  • In fact, by the same method, we can generalize to any base $b\ge2$: the sum of digits of the square of $S_n$ (in base $b$) is equal to $$ (b-1)^2\cdot\left(\left\lfloor\frac n{b-1}\right\rfloor+\left{\frac n{b-1}\right}^2 \right).$$ – awllower Aug 07 '19 at 12:52
  • 1
    Indeed! That's a nice observation @awllower. – Jyrki Lahtonen Aug 07 '19 at 16:55
0

It is also possible to do it by proving that the difference between sum of the digits of $S_{n+1}^2$ and $S_n^2$ equals to $2(n \mod 9) + 1$. I see it is, but I can't prove it formally. Maybe someone would like to fill the gap in my solution :-) and then sum the differences from $S_0^2$ to $S_n^2$

Norbert
  • 56,803
msa
  • 1
  • 1