On the sum of digits of $n^k$

Question

Reading another question on the sum of the digits of $2^n$ i started wondering whether there exist a $\alpha\in\mathbb{N}$ such that for every $n>\alpha$ we have $S(2^{n+1})>S(2^n)$, where $S(n)$ is the sum of the digits of $n$.

Via a computer program I plotted the graph of $S(2^n)$ for $n$ up to $10000$ and there clearly isn't a point in this interval after which $S(2^n)$ becomes increasing.

With the same computer program I plotted the graphs of $S(k^n)$ for several small $k$ and $n$ up to $10000$, with the same results (excluding $k=0,1$ or $10$, for which the sum of the digits is obviously constant).

edit:
Here is a graph of $S(2^n)$ for $1\le n\le 1000$, as you can see the values seems to grow (and this observation can be made also on the graph with higher values of $n$), but in a very oscillating manner

So, my question is, is there a $k\in\mathbb{N}$ such that $S(k^n), n\in\mathbb{N}$ eventually becomes increasing?

Later edit:
In this MO question is provided a reference for the fact that for any $n,s\in\Bbb{N}$ there exist only finitely many values of $k\in\Bbb{N}$ such that $S(n^k)<s$ so we know that $S(n^k)$ can be arbitratily big for any $n$ (of course $n$ must not be a power of $10$).

Even later edit:
Apparently the specific case of $S(2^n)$ had already been asked and negatively answered (thanks to Erick Wong for pointing it out, I somehow missed the question when i searched to see if mine was a duplicate).
I'm still interested in whether there is some $k$ such that $S(k^n)$ eventually becomes increasing

a few months older edit:
The question was reposted on MO

Answer 1

Estimation

Looking at $$ 2^n = 10^x \iff x = n \log_{10} 2 = \frac{\ln 2}{\ln 10} n \approx 0.3 \, n $$

$(2^n)_2$ has $n+1$ digits, $(2^n)_{10}$ has about $n/3$ digits. $10$ new digits in base $2$ ($2^{10} = 1024$) give about $3$ new digits in base 10.

My gut feeling is that with more and more digits, more and more digits have the chance to be non-zero, which will lead to a growth of $S((2^n)_{10})$ in the long run.

Note: A counter example to this idea is $S((2^n)_2) = 1 = \mbox{const.}$, where the division is perfect.

Calculation of the base 10 digits

For the $m$ digits $d_k$ of $(2^n)_{10}$ we have $$ 2^n = \sum_{k=0}^{m-1} d_k \, 10^k $$

We start with $n = 0$: $$ m^{(0)} = 1 \quad d_0^{(0)} = 1 $$

As $n$ increases we have $$ (2^{n+1})_{10} = (2^{n} + 2^{n})_{10} $$ so the digits can be calculated by addition with carry, for the $k$-th digit we have $$ d_k^{(n+1)} = \left( 2 \, d_k^{(n)} + c_{k-1}^{(n+1)} \right) \bmod 10 \quad (*) \\ c_k^{(n+1)} = \left\lfloor \left( 2 \, d_k^{(n)} + c_{k-1}^{(n+1)} \right) / 10 \right\rfloor $$ where $c_k$ is the carry value, in this case $c_k \in \mathbb{B} = \{0,1\}$. We set $c_{-1} = 0$ and note that a set carry bit $c_{m}^{(n+1)}$ will trigger the creation of a new digit $d_{m}^{(n+1)} = 1$ and increase $m$: $m^{(n+1)} = m^{(n)} + 1$.

Equation $(*)$ is quite similar to a linear congruential generator $$ X_{n+1} = (a X_{n} + c) \bmod m $$ which is used to generate pseudo random numbers. The difference is a variable $c$ in equation $(*)$ versus the constant $c$ in the LCG. Also $a=2$ and $m=10$ might not be the best choices for a good PRNG.

This might justify the assumption of random digits, if one dives deeper into LCG properties.

Development of the digits $d_k^{(n)}$

$$ \begin{array}{c|cccccccccc} c_{k+1} \, d_k^{(n+1)} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & = d_k^{(n)} \\ \hline c_k = 0 & 0\, 0 & 0\, 2 & 0\, 4 & 0\, 6 & 0\, 8 & 1\, 0 & 1\, 2 & 1\, 4 & 1\, 6 & 1\, 8 \\ \hline c_k = 1 & 0\, 1 & 0\, 3 & 0\, 5 & 0\, 7 & 0\, 9 & 1\, 1 & 1\, 3 & 1\, 5 & 1\, 7 & 1\, 9 \\ \end{array} $$

The computation rules are simple but they gives raise to a complex behaviour.

For the last digit $d_0$ we get a cycle of length $4$: 4,8,6,2

c  0<0>0 0 0<0> ..
d  1<2>4 8 6<2>
d+ 2 4 8 6 2 4 ..
     ----------
c+ 0 0 0 1 1 0 

For the next digit $d_1$ we get a cycle of length $20$:

d_1:
c  0 0 0<1>1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0<1>1 0 0 ..
d  0 0 0<0>1 3 6 2 5 1 2 4 9 9 8 6 3 7 4 8 7 5 0<0>1 3 6
d+ 0 0 0 1 3 6 2 5 1 2 4 9 9 8 6 3 7 4 8 7 5 0 0 1 3 6 2 ..
         --------------------------------------- 
c+ 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1

For $d_2$ one gets this development:

d_2:
c  0 0 0 0 0 0<1>0 1 0..
d  0 0 0 0 0 0<0>1 2 5
d+ 0 0 0 0 0 0 1 2 5 0
               -------.. 
c+ 0 0 0 0 0 0 0 0 0 1..

000000
0125000137501251362487498
6251374987512486363624999
9874999862498748637512501
3748625012487513636375000
0125000..

It features a cycle of length $100$.

So a newly introduced digit starts as a $1$ and seems to go (after some iterations) into a cycle. This is influenced by the carry bit sequence of the digit before.

Development of the digit sum

The digit sum $$ S((2^{(n)})_{10}) = \sum_{i=1}^9 f_i^{(n)} \, i $$ depends on the counts $f_i^{(n)}$ of the non-zero digits.

A rough estimation is that it will be the length of the string representation times the average digit $4.5$, including that this will increase, because the string length has to grow with increasing $n$.

However I have no justification for this, except some calculated values.

Answer 2

I would say that there is no such $\alpha$. In fact I would bet my house on it. It would be astonishing if (say) $S(2^n)$ were found to be eventually monotonic increasing. But I don't think anybody has a proof that it's not.

In the other direction: Does $S(2^n)$ even tend to infinity as $n \to \infty$? Again, it would be astonishing if it didn't. But I don't think anybody has a proof that it does.

Answer 3

Not an answer. Just a related plot I produced and feel like sharing.

This seems to very much support the model that in $2^n$ there are $n\log_{10}2$ random digits. In the figure below the blue cloud of dots gives the difference $S(n)-P(n)$, where $S(n)$ is the actual sum of base ten digits of $2^n$, and $P(n)=\frac92n\log_{10}2$ is the predicted sum of digits. The orange and red curves are the +1SD and +2SD curves respectively. The square of the difference of a random digit from $9/2$ has expected value $33/4$, so these curves are $k\sqrt{33 n \log_{10}2}/2$ with $k=1$ and $k=2$.

The range covered in the plot is $1\le n\le 10000$.