En la suma de dígitos de $n^k$

Question

Leyendo otra pregunta sobre la suma de los dígitos de $2^n$ empecé a preguntarme si existe una $\alpha\in\mathbb{N}$ tal que para cada $n>\alpha$ tenemos $S(2^{n+1})>S(2^n)$ , donde $S(n)$ es la suma de los dígitos de $n$ .

A través de un programa informático he trazado la gráfica de $S(2^n)$ para $n$ hasta $10000$ y claramente no hay un punto en este intervalo después del cual $S(2^n)$ se vuelve creciente.

Con el mismo programa informático he trazado los gráficos de $S(k^n)$ para varios pequeños $k$ y $n$ hasta $10000$ con los mismos resultados (excluyendo $k=0,1$ o $10$ para el que la suma de los dígitos es obviamente constante).

editar:
Este es un gráfico de $S(2^n)$ para $1\le n\le 1000$ como se puede ver los valores parecen crecer (y esta observación se puede hacer también en el gráfico con valores más altos de $n$ ), pero de forma muy oscilante

Entonces, mi pregunta es, ¿hay una $k\in\mathbb{N}$ tal que $S(k^n), n\in\mathbb{N}$ ¿con el tiempo se convierte en algo creciente?

Edición posterior:
En este La pregunta MO es una referencia para el hecho de que para cualquier $n,s\in\Bbb{N}$ sólo existe un número finito de valores de $k\in\Bbb{N}$ tal que $S(n^k)<s$ por lo que sabemos que $S(n^k)$ puede ser arbitrariamente grande para cualquier $n$ (por supuesto $n$ no debe ser un poder de $10$ ).

Incluso la edición posterior:
Al parecer, el caso concreto de $S(2^n)$ ya se había pedido y respondido negativamente (gracias a Erick Wong por señalarlo, de alguna manera se me pasó la pregunta cuando busqué para ver si la mía era un duplicado).
Todavía estoy interesado en saber si hay algún $k$ tal que $S(k^n)$ finalmente se convierte en creciente

una edición de unos meses más antigua:
La pregunta fue reenviada a MO

Answer 1

No es una respuesta. Sólo una trama relacionada que produje y me apetece compartir.

Esto parece apoyar en gran medida el modelo que en $2^n$ hay $n\log_{10}2$ dígitos aleatorios. En la figura siguiente, la nube azul de puntos da la diferencia $S(n)-P(n)$ , donde $S(n)$ es la suma real de los dígitos de base diez de $2^n$ y $P(n)=\frac92n\log_{10}2$ es la suma de dígitos prevista. Las curvas naranja y roja son las curvas +1SD y +2SD respectivamente. El cuadrado de la diferencia de un dígito aleatorio de $9/2$ tiene un valor esperado $33/4$ , por lo que estas curvas son $k\sqrt{33 n \log_{10}2}/2$ con $k=1$ y $k=2$ .

El rango cubierto en la parcela es $1\le n\le 10000$ .

Answer 2

Yo diría que no existe tal $\alpha$ . De hecho, apostaría mi casa por ello. Sería sorprendente si (digamos) $S(2^n)$ se encontraron con que eventualmente son monotónicas crecientes. Pero no creo que nadie tenga una prueba de que no lo sea.

En la otra dirección: ¿Tiene $S(2^n)$ incluso tienden al infinito como $n \to \infty$ ? De nuevo, sería sorprendente que no fuera así. Pero no creo que nadie tenga una prueba de que así sea.

Answer 3

Estimación

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

$(2^n)_2$ tiene $n+1$ dígitos, $(2^n)_{10}$ tiene alrededor de $n/3$ dígitos. $10$ nuevos dígitos en la base $2$ ( $2^{10} = 1024$ ) dan alrededor de $3$ nuevos dígitos en base 10.

Mi intuición es que con más y más dígitos, más y más dígitos tienen la oportunidad de ser distintos de cero, lo que llevará a un crecimiento de $S((2^n)_{10})$ a largo plazo.

Nota: Un ejemplo contrario a esta idea es $S((2^n)_2) = 1 = \mbox{const.}$ donde la división es perfecta.

Cálculo de los dígitos de base 10

Para el $m$ dígitos $d_k$ de $(2^n)_{10}$ tenemos $$ 2^n = \sum_{k=0}^{m-1} d_k \, 10^k $$

Comenzamos con $n = 0$ : $$ m^{(0)} = 1 \quad d_0^{(0)} = 1 $$

Como $n$ aumenta tenemos $$ (2^{n+1})_{10} = (2^{n} + 2^{n})_{10} $$ para que los dígitos puedan ser calculados por adición con acarreo, para el $k$ -dígito tenemos $$ 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 $$ donde $c_k$ es el valor de arrastre, en este caso $c_k \in \mathbb{B} = \{0,1\}$ . Establecemos $c_{-1} = 0$ y observe que un bit de acarreo establecido $c_{m}^{(n+1)}$ provocará la creación de un nuevo dígito $d_{m}^{(n+1)} = 1$ y aumentar $m$ : $m^{(n+1)} = m^{(n)} + 1$ .

Ecuación $(*)$ es bastante similar a un generador congruente lineal $$ X_{n+1} = (a X_{n} + c) \bmod m $$ que se utiliza para generar números pseudoaleatorios. La diferencia es una variable $c$ en la ecuación $(*)$ frente a la constante $c$ en el LCG. También $a=2$ y $m=10$ pueden no ser las mejores opciones para un buen PRNG.

Esto podría justificar la suposición de dígitos aleatorios, si se profundiza en las propiedades de la LCG.

Desarrollo de los dígitos $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} $$

Las reglas de cálculo son sencillas pero dan lugar a un comportamiento complejo.

Para el último dígito $d_0$ obtenemos un ciclo de longitud $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 

Para la siguiente cifra $d_1$ obtenemos un ciclo de longitud $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

Para $d_2$ se consigue este desarrollo:

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

Presenta un ciclo de longitud $100$ .

Así, un dígito recién introducido comienza como $1$ y parece entrar (después de algunas iteraciones) en un ciclo. En esto influye la secuencia de bits de arrastre del dígito anterior.

Desarrollo de la suma de dígitos

La suma de dígitos $$ S((2^{(n)})_{10}) = \sum_{i=1}^9 f_i^{(n)} \, i $$ depende de los recuentos $f_i^{(n)}$ de los dígitos no nulos.

Una estimación aproximada es que será la longitud de la representación de la cadena multiplicada por el dígito medio $4.5$ incluyendo que esto aumentará, porque la longitud de la cadena tiene que crecer con el aumento de $n$ .

Sin embargo, no tengo ninguna justificación para esto, excepto algunos valores calculados.