Sum of digits

Almost a month ago I participated in the Ibero-American College Olympiad thats was held in Quito  as team leader of the Guatemalan team. It had been almost 4 years now since I last participated in any olympiad-related event and sure enough, I was out of shape.  It is well known that mathematics is like any other activity, it requires constant practice and training, even more to make it in a competing level. 

I had a really good time remembering my Olympic times, but it also reminded my how out of shape I was. I must be that the type of mathematics used to do research is a bit different as the kind of skills that are used in competitions, as their goals are a bit different. None the less, this feeling made me start a personal goal: do at least one olympiad-type problem each day. With that in mind, I start this blog, were I post a problem everyday (first in my twitter and then I post the solution of the problem in the blog). Last week, when looking at one of the problems of the day, I noticed a very interesting pattern in the sum of the digits of the powers of 16.

I found the curious relation that the sum of the digits of $16^n$ is $6n+1$. This was something that I had never noticed before and I found it quite charming. After a bit, I started wondering if this sort of property was satisfied with some other powers, but found nothing like the powers of 16. It intrigued me then what was so special about 16 that made it have this beautiful property. 

Talking about this with my friend Esteban, I decided to seek for an easy proof of this fact that could unravel the mystery behind the 16, as no direct explanation seemed to appear.. What would the equivalent power be in a different base $b$ rather than 10?

Surprisingly enough, the core of this pretty property is hidden in the number 9. If you have a number $m$  which does not end in 1, $m$ and $m+9$ will have the same sum of digits. And what is the relation with 9 and 16? Well, $16^n$ always ends with 6, and when you multiply it by 16 we have that

 $16^{n+1}=16^n\cdot 10+16^n\cdot 6$. 

The first summand will have the same sum as $16^n$. Now the magic happens with the second summand. As it ends with 6, when performing the multiplications as we all learned in elementary school, the first operator that we make is $6\times 6=36=3\times 10+6$, thus the 30 adds up with the tenths of the first summand and voilà, there appears the 9. Then to compute the new number $(16^{n+1})$, we only have to keep performing this algorithm as in elementary school, and we end up having that the new number is going to have the same sum of digits as the one before, except by the digit of the units, which is 6. Therefore by induction we have that the sum is to have the desired form. 

By looking at this, we can easily find other numbers that work, for example the powers of $10^k+6$ will do the job. Here we can notice then that the special duty is made by the number 6, as $6^2=36$ whose sum of digits equals 9 and ends also in 6. So hence, when looking at different bases other than 10, we can find something similar happening. We need to have then a base $b$ and a digit $d$ such that:

• $d^2$ ends in $d$
• the sum of the digits of $d^2$ is equal to $b-1$.

In other words, we need to find pairs $(b,d)$ such that

$d^2=(b-1-d)b+d$

i.e.

$d^2+d(b-1)-b(b-1)=0$

which will have integer solutions iff 

$(b-1)^2+4b(b-1)=5b^2-6b+1=(5b-1)(b-1)$

is a perfect square. This is a diophantine equation of order two, which have integer solutions. For instance another solutions are $(65,40), (442, 273), (3026, 1870)$. One way of analyzing this equation can be by the method I described earlier.

Thus, similar properties are satisfied by $65^k+40$, $442^k+273$ and $3026^k+1870$ in base $65, 442$ and $3026$ respectively and $k>0$. It is a neat property and special also because it happens to be the case that we use a base that satisfy this diophantine equation.