5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$
    – lulu
    Jan 13 at 22:07
  • $\begingroup$ 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$. $\endgroup$
    – lulu
    Jan 13 at 22:08
  • $\begingroup$ @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$. $\endgroup$
    – Brian Tung
    Jan 13 at 22:21
  • 1
    $\begingroup$ @BrianTung The question has been edited repeatedly... $\endgroup$
    – lulu
    Jan 13 at 22:22
  • $\begingroup$ @lulu: Ahh I see. $\endgroup$
    – Brian Tung
    Jan 13 at 22:31

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$ Jan 14 at 15:24
  • $\begingroup$ @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. $\endgroup$ Jan 14 at 16:36
3
$\begingroup$

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<q$).

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .