7
$\begingroup$

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...

  • 0
    @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...2012-02-24
  • 0
    @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.2012-02-24
  • 0
    @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?2012-02-25
  • 0
    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.2012-02-25

2 Answers 2

4

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. $$
  • 0
    But another approach may lead to a cleaner solution. First I tried to calculate the total carry...2012-02-24
  • 0
    Won't there be an overlap between $10^9 S_n^2$ and the middle term?2012-02-24
  • 0
    @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.2012-02-24
  • 0
    I see. Nice :-) (you have my +1 already, in case you are wondering :-))2012-02-24
  • 0
    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.2012-02-25
  • 0
    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) :-)2012-02-25
  • 0
    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 :-)2012-02-25
  • 0
    Well, done @xan ! I missed most of today in a bridge tournament, but you seem to have managed just fine :-)2012-02-25
  • 0
    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 :-)2012-02-25
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$