12
$\begingroup$

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 enter image description here

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

$\endgroup$
  • $\begingroup$ No such $\alpha$ exists for any base, unless that base is a rational power of the base of numeration $($in which case we are dealing with a cycle. And if that cycle has length $1$, we can write $\ge$ or $=)$. $\endgroup$ – Lucian Jan 13 '15 at 17:08
  • $\begingroup$ Can you show it or link a reference? $\endgroup$ – Alessandro Codenotti Jan 13 '15 at 17:19
  • 3
    $\begingroup$ The simplest heuristic is to assume that everything about $k^n$ is random except for its length, which is about $l_n=n\log_{10}k$. Then the sum of its digits should generally look like a linear term, $(9/2)l_n$, plus white noise with standard deviation $c\sqrt{l_n}$. Once the standard deviation of the noise exceeds the linear slope, the sum of the digits will be non-monotonic. $\endgroup$ – mjqxxxx Jan 14 '15 at 20:28
  • 3
    $\begingroup$ The specific question for $2^n$ is answered (in the negative) here: math.stackexchange.com/questions/560624/…. So indeed it is true that $S(2^n)$ keeps oscillating. However, the method is fairly ad hoc and probably wouldn't succeed for many bases. $\endgroup$ – Erick Wong Jan 15 '15 at 20:08
  • $\begingroup$ @ErickWong: thanks for the link, I didn't find it when searching for similar questions! $\endgroup$ – Alessandro Codenotti Jan 15 '15 at 20:28
5
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ If one looks at a fixed digit at place $k$, with increasing $n$ it develops like a PRNG. $\endgroup$ – mvw Jan 16 '15 at 12:46
  • $\begingroup$ Yes. The evolution of a digit at a fixed place branches according to whether there will be a carry or not. But I couldn't make any real use of that. $\endgroup$ – Jyrki Lahtonen Jan 16 '15 at 13:04
  • $\begingroup$ And at each place it is a PRNG with different parameters, e.g. the cycles seem to get longer (times $5$) with increasing place. I need to dive deeper into Knuth Vol. 2 to understand how to analyse this. $\endgroup$ – mvw Jan 16 '15 at 13:12
  • 1
    $\begingroup$ @mvw the 5-fold increase in cycle length is an immediate consequence of the structure of the group of coprime residue classes modulo $5^n$. It is cyclic of order $4\cdot5^{n-1}$. IIRC $2$ is a generator. $\endgroup$ – Jyrki Lahtonen Jan 16 '15 at 13:20
  • $\begingroup$ Thanks for that pointer. Never thought radix conversion would be so much fun. $\endgroup$ – mvw Jan 16 '15 at 13:24
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If the digits were distributed uniformly one would expect $S(2^n)$ to roughly be the string length times the average digit $4.5$. That is what I roughly see in a computer output. I am looking into the cylcles of the different digit places right now, e.g. how the 2nd last digit evolves and it is interestingly complicated. No idea why I see a cycle of length $100$ there. I wish I would know more about the analysis of PRNGs, this looks similar. $\endgroup$ – mvw Jan 15 '15 at 13:23
  • $\begingroup$ I assume that by 'evenly' you mean 'randomly with a uniform distribution'. In this case, we would expect to see fluctuations of the order of $\sqrt{S(2^n)}$ superposed on the average value. $\endgroup$ – TonyK Jan 15 '15 at 13:26
  • $\begingroup$ Note: I edited 'evenly' to 'uniformly'. $\endgroup$ – mvw Jan 15 '15 at 13:29
  • 1
    $\begingroup$ @TonyK: your house is safe, see the comment from Erick on my original post. Are you willing to bet that there isn't such an $\alpha$ for any base $k$? $\endgroup$ – Alessandro Codenotti Jan 15 '15 at 20:31
  • 3
    $\begingroup$ @Alessandro: Phew! I am willing to be astonished if there is any counterexample apart from the trivial ones described in Lucian's comment. But I'm not going to bet my house twice in one day :-) $\endgroup$ – TonyK Jan 15 '15 at 21:36
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'll add some graphs as soon as I'm home because I think the question wasn't too clear. Judging from the graphs $S(2^n)$ (and any other base apart from the trivially constant ones) appears to be growing, but I'm asking wether they eventually become monotonically increasing (I'm not sure you can say that this term can be applied to functions $\mathbb{N}\to\mathbb{N}$ though) $\endgroup$ – Alessandro Codenotti Jan 13 '15 at 14:15
  • 3
    $\begingroup$ What I mean is that from the graph there doesn't seem to be an upper bound on the value of $S(2^n)$, but what I'm interested in is if there's a point after which every value is bigger than the one before it $\endgroup$ – Alessandro Codenotti Jan 13 '15 at 14:28
  • $\begingroup$ I got that, but I found no way to proof it yet. :-) I am pretty sure it is not possible to increase forever, this is because with increasing $n$ the digits $d_k^{(n)}$ are either constant or cycling, which means they might increase for some time but then have to decrease, otherwise there would be no cycle. All this happens with different starts and cycles but in sum this should have the same effect, oscillation of the sum and a growth of the sum due to more digits getting active. $\endgroup$ – mvw Jan 16 '15 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.