# Digit sum equality $S(a^n + n) = 1 + S(n)$ implies that $a$ is a power of ten

Let $$a$$ be a positive integer such that for the digit sum $$S(\cdot)$$ the equality $$S(a^n + n) = 1 + S(n)$$ holds for every sufficiently large $$n$$. Then $$a$$ is a power of ten.

So I know that $$S(a+b)=S(a)+S(b)-9c(a,b),$$ where $$c(a,b)$$ is the number of carryovers when adding $$a$$ and $$b$$. Using this gives $$S(a^n) +S(n)-9c(a^n,n) = 1 + S(n)$$ and hence $$S(a^n)=1+9c(a^n,n).$$ Now if we set e.g. $$a=10$$, we get $$S(10^n)=1+9c(10^n,n)$$ and $$9c(10^n,n)=0$$ for large $$n$$, so the formula makes sense. But the thing that we have to prove is that our condition definitely gives $$a=10^z$$. So maybe this way of proving it is wrong, maybe one has to assume that $$a\neq 10$$ in the beginning. Any help would be great, this is a problem for olympiad training.

• I assume that $Q(n)$ is the sum of the digits in $n$? Of course, this should be stated in the post. Note that any power of $10$ works, you don't need $a=10$.
– lulu
Jan 13 at 22:07
• Working $\pmod 9$ we get $a^n+n\equiv 1 +n \pmod 9$ so $a^n \equiv 1 \pmod 9$ for large $n$. Thus, at least you know that $a\equiv 1 \pmod 9$.
– lulu
Jan 13 at 22:08
• @lulu: I don't think you have to assume that $Q(n)$ is the sum of the digits of $n$. It turns out to be, but I don't think you need that to show that $a$ is a power of $10$. Jan 13 at 22:21
• @BrianTung The question has been edited repeatedly...
– lulu
Jan 13 at 22:22
• @lulu: Ahh I see. Jan 13 at 22:31

We require

$$S(a^n + n) = 1 + S(n) \tag{1}\label{eq1A}$$

to be true for all sufficiently large $$n$$. Note that $$a = 1$$ doesn't work, e.g., take $$n = 10^k - 1$$ for any $$k \ge 1$$, so this means $$a \gt 1$$. However, $$a = 10^k$$ for any integer $$k \ge 1$$ does work, since $$a^n \gt n$$ which means $$a^n + n$$ has a leading digit of $$1$$, followed by some zeros and then the digits of $$n$$. This shows that \eqref{eq1A} holds in those cases.

Next, consider $$n = 10^k$$ for all integers $$k \ge k_0$$ for some sufficiently large $$k_0$$, so $$1 + S(n) = 2$$. If $$a$$ is a multiple of $$10$$, then $$a^n$$ would have at least $$n$$ zeros at the end, which is more than the digits of $$n$$, so \eqref{eq1A} would only hold if $$a^n$$ has a leading digit of $$1$$ and then remaining digits all being $$0$$. However, this only happens if $$a$$ is a positive integral power of $$10$$.

If $$a$$ is not a multiple of $$10$$, then the last digit of $$a^n$$ is not $$0$$. Thus, $$S(a^n + n) = 2$$ requires the right-most digit of $$a^n$$ to be $$1$$ then, going to the left from there, there would be $$k - 1$$ zeros, and then some $$m \ge 1$$ group of the digits $$9$$. This means $$a^n + n$$ would be a power of $$10$$ plus $$1$$ to get $$S(a^n + n) = 2$$. Thus, we have

$$a^n = 10^{m+k} - 10^k + 1 = 10^{k}(10^m - 1) + 1 \tag{2}\label{eq2A}$$

Next, consider $$n_1 = 10^{k+1}$$, so $$a^{n_1} = (a^{n})^{10}$$. From \eqref{eq2A}, we get

$$a^{n_1} = 1 + 10(10^k(10^m - 1)) + 45(10^k(10^m - 1))^2 + \ldots + (10^k(10^m - 1))^{10} \tag{3}\label{eq3A}$$

The second term of $$(10^m - 1)10^{k+1}$$ has, from the right, $$k + 1$$ zeros and then $$m$$ nines. This added to $$n_1$$ results in a $$1$$ followed by $$k + m + 1$$ zeros. The third term, i.e., $$(45(10^m - 1)^2)10^{2k}$$, has $$2k$$ zeros on the right, then an odd multiple of $$5$$, i.e., $$45(10^m - 1)^2$$, so its last digit is $$5$$. If $$2k = k + m + 1 \;\to\; k = m + 1$$, then this last digit will overlap with a $$1$$ digit mentioned before, resulting in a digit of $$6$$, else it will remain as $$5$$. Since all of the remaining terms have at least $$3k$$ right-end zeros, none of them will affect this digit in the summation. Thus, we get $$S(a^n + n) \gt 2$$, so \eqref{eq1A} is not true.

This shows that $$a$$ can only be a positive integral power of $$10$$.

• Why is $$a^{n_1} \equiv 1 \pmod{10^{10k}}.$$ For $k=2$ and $m=3$, I get $$a^{n_1}=(a^n)^{10} = (10^{2}(10^3 - 1) + 1)^{10} \equiv 14236364309981449001 \pmod{10^{20}}.$$ using pari.math.u-bordeaux.fr/gp.html Jan 14 at 15:24
• @calculatormathematical Thank you for pointing out my mistake. It's not quite as simple as I originally thought. Nonetheless, I've now made a correction which still leads to the same conclusion. Please let me know if there are any other issues. Jan 14 at 16:36

This solution is the same in heart as the one posted by John Omielan, only with simplified final steps.

If $$a$$ is a multiple of $$10$$, then $$S(a^n+n) = S(a^n)+S(n)$$, thus $$S(a^n)=1$$ for sufficiently large $$n$$, which means $$a$$ is a power of $$10$$.

Otherwise, let $$n = 10^k$$ for some sufficiently large $$k$$. Then $$\begin{cases} S(a^{10^k}+10^k) &= 1+S(10^k) &= 2\\ S(a^{10^{k+1}}+10^{k+1}) &= 1+S(10^{k+1}) &= 2 \end{cases} \implies \begin{cases} a^{10^k}+10^k &= 10^p+1\\ a^{10^{k+1}}+10^{k+1} &= 10^q+1 \end{cases}$$ where $$p$$ and $$q$$ are the amount of digits of $$a^{10^k}+10^k$$ and $$a^{10^{k+1}}+10^{k+1}$$, respectively (of course $$p).

Now, this means $$10^q+1-10^{k+1} = a^{10^{k+1}} = (a^{10^k})^{10} = (10^p+1-10^k)^{10}$$, therefore $$1-10^{k+1}\equiv (1-10^k)^{10}\pmod{10^p}$$ thus $$10^p$$ divides $$(10^k-1)^{10}+10^{k+1}-1$$. This is ridiculous (I mean, a contradiction) because $$0<(10^k-1)^{10}+10^{k+1}-1\approx 10^{10k}\ll a^{10^k}\approx 10^p$$