¿Cómo encontrar el elemento de la secuencia de suma de dígitos de manera eficiente?

20

Solo por interés, traté de resolver un problema de la categoría "Reciente" del Proyecto Euler ( secuencia de suma de dígitos ). Pero no puedo pensar en una forma de resolver el problema de manera eficiente. El problema es el siguiente (en la secuencia de preguntas original hay dos al principio, pero no cambia la secuencia):

La secuencia de suma de dígitos es 1,2,4,8,16,23,28,38,49 .... donde el término de secuencia es la suma de dígitos que la preceden en la secuencia. Encuentre el término de la secuencia.nth1015th

La solución ingenua no se puede implementar porque lleva mucho tiempo. Traté de reducir el problema a un caso de exponenciación de la matriz (que tomaría una cantidad de tiempo ) pero no pude encontrar una recurrencia que se ajustara a los criterios lineales, ya que la recurrencia para esta secuencia es bastante peculiar Se puede ver que la secuencia se rige por la recurrencia:O(log(1015))

an=an1+d(an1).....(1)

donde anorte es norteth término de la secuencia re es una función que, cuando se le da un número natural como entrada, devuelve la suma de dígitos del número (p. ej. re(786)=21 ). Mi segundo enfoque fue tratar de encontrar algún patrón en la secuencia. Se puede ver que los primeros términos de la secuencia se pueden escribir como

   a_1 = 1  
   a_2 = 1 + d( 1 )
   a_3 = 1 + d( 1 ) + d( 1 + d( 1 ) )
   a_4 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) )
   a_5 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) + d( 1 +  d(  
   1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) )

A partir del patrón anterior, se convierte en que el término norteth de la secuencia se puede generar mediante el siguiente método:

  1. Escriba 12norte-1 1 's con el símbolo de suma entre ellos.
  2. Dejando el primer 1 , luego aplique la función re en los próximos 20 0 términos, luego en los siguientes 21 términos, luego en los siguientes 22 términos y así sucesivamente.
  3. Luego aplique el método anterior de forma recursiva en los argumentos de cada función re aplicada.

por ejemplo si n = 3 realizamos las siguientes manipulaciones:

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    1 + d( 1 ) + d( 1 + 1 ) + d( 1 + 1 + 1 + 1 )
    1 + d( 1 ) + d( 1 + d(1) ) + d( 1 + d( 1 ) + d( 1 +d( 1 ) ) )

Mediante la programación dinámica puedo generar el término usando el método anterior en el tiempo , que de nuevo no es mejor que la solución ingenua.nortethO(losol(21015))

EDITAR 1
Otra cosa que se puede observar es que . Por ejemplo . Pero no puedo hacer uso de este punto. Intenté nuevamente encontrar una relación de recurrencia lineal (para la exponenciación de la matriz), pero no puedo encontrarla.re(unanorte)=re(2norte-1)re(una6 6)=re(23)=re(32)=5 5

EDITAR 2

A continuación se muestra el gráfico cuando se traza la secuencia para un rango menor (se trazan los primeros términos de la secuencia). 106 6ingrese la descripción de la imagen aquí

PD: Sé que no es aconsejable pedir soluciones al Proyecto Euler. Pero solo quiero una nueva dirección o una pista, ya que me he estado moviendo en círculos durante los últimos días. Si eso también es inaceptable, puedo eliminar la pregunta si se sugiere.

Sashas
fuente
1
Siento que You are given a106 = 31054319.en el problema original de Euler es una pista.
Filip Haglund
@FilipHaglund que no es una pista. Solo por la fuerza bruta puedo calcular ese valor fácilmente. Es solo para verificar su enfoque.
sashas
3
También en OEIS: oeis.org/A004207 .
Yuval Filmus
@EvilJS podría, sí, tracé el gráfico en una extensión que aumenta gradualmente en forma de zig zag. ¿Podría elaborar su último punto "" patrones de almacenamiento en caché ... ".
sashas
Dado que aparecen patrones interesantes en el mod 9, ¿sucede algo interesante si miramos la secuencia mod 11 o mod 99? El valor mod 11 puede derivarse de la suma de los dígitos indexados impares y la suma de los dígitos indexados pares. El valor mod 99 puede derivarse de la suma de pares de dígitos adyacentes.
DW

Respuestas:

4

Su secuencia se describe en oeis.org/A004207 como suma de dígitos. Hay algunos puntos buenos como que la secuencia mod 9 tiene un patrón repetitivo , comparte raíces digitales con oeis.org/A065075 y oeis.org/A001370 . Si esas propiedades son útiles es un problema abierto (porque no hay una ecuación de forma cerrada para número).(1,2,4 4,8,7 7,5 5)norte-th

Hay algunas propiedades de esta secuencia que vale la pena mencionar:
cuando calcula número, solo necesita almacenar el contador (para saber qué número era) y el número en sí. Para reiniciar no hay nada más necesario, ya que el siguiente número es el número actual + suma de sus dígitos.norte-th

Al tomar algunos pasos para garantizar la velocidad al principio, es bueno poner los números en la matriz, evitando cálculos ingenuos de mod y div, que son caros. Esto da aceleración por constante, pero mirando a veces sí importa.

Desde el punto de partida puede calcular el siguiente, y el siguiente, y funciona hasta cierto punto, este mismo punto es el cambio de número de dígitos.
Lo que es más importante, los patrones están cambiando con el aumento de los números.
Las sumas de dígitos son pequeñas en comparación con los números en sí, por lo que solo la parte del número cambiará en la mayoría de las operaciones.
Entonces, ¿qué podemos realmente almacenar en caché?

Sabemos que con dos números con la misma suma de dígitos, la suma para obtener el siguiente número será la misma. ¿Qué hay del próximo?

Sasha

Alerta de spoiler, a continuación se muestra un patrón de caché bastante explícito

Depende de condiciones adicionales, como los números que no cambian en la ejecución , lo llamaré turno , cantidad inicial como inicio .

Tomando una carrera arbitraria , como , y comenzando de 0 a 9 , podemos almacenar en caché cada patrón desde el punto de partida hasta 100 , contar el número de elementos (para saber cómo lidiar con el contador, que es necesario para dar algo de n - t h número), y memorizarlo. 1000 09 9100norte-th

Okay. Hasta ahora, cualquier inicio está cubierto, ¿qué cambia más allá de ? Desafortunadamente, estos patrones dejan de funcionar, porque si intenta desde 100 haciendo que el inicio sea igual a 1 , el siguiente número se calcula perfectamente, pero el segundo se rompe. 100
1001

Aquí tenemos que cubrir shift set en y empezar a 0 . También significa calcular tablas para diferentes turnos . 10 0

¿Realmente necesitamos calcularlos todos ? No, realmente no.
Parte de las tablas es solo otro elemento inicial más.
Por ejemplo, a partir de da la misma secuencia desplazada. Entonces, ¿necesitamos calcular un caché más largo? No, lo calculamos para cambiar el cambio y recoger otra ejecución , por lo que ahorrará mucha memoria. 1,2,4 4,8

Ahora, cuando la tabla está cubierta, comenzamos desde la configuración inicial, seleccionamos la suma de la tabla, agregamos el contador y vemos que: desde llegamos a 101 , actualizamos las variables y saltamos a 218 , repitiendo los pasos 305 -> 406 -> 517 -> 607 -> 719 -> 805 -> 904 -> 1003 . Okay. ¿Ahora que? 11012183054065176077198059041003

Podemos continuar hasta que el turno sea ​​más alto de lo calculado.
Yendo más allá, podríamos construir más carreras sobre la marcha, calcular previamente carreras más grandes u observar otros patrones (como si pudiéramos reutilizar parcialmente las tablas ya calculadas).
Eche un vistazo a diferentes turnos como todos dan la misma ejecución siendo el mismo entorno para sumas de dígitos, por lo tanto, podemos usar las mismas tablas. Hacer tablas más grandes que 100 elementos acelera aún más el proceso, haciendo saltos más grandes a la vez.100,1000,10000,100000,1000000 ...
100

Mal
fuente
4

Dado que solicitó "una nueva dirección o una pista" y no sé la respuesta, lo dejaré aquí, espero que sea útil. algunas ideas:

Tiene sentido que haya un patrón mod 9, ya que

k>1,kZ10k1modificación9 9

Lo que puedes probar por inducción.

Esto significa que todos los números son congruentes con la suma de sus dígitos mod 9.

unanorte=re(unanorte)modificación9 9

unanorte=unanorte-1+re(unanorte-1)=2re(unanorte-1)modificación9 9

Si seguimos expandiendo esta recurrencia obtenemos

unanorte=2nortemodificación9 9

Lo que explica el patrón mod 9.

unanorte=9 9k+2norte

Aquí hay un código menos que general:

import matplotlib.pyplot as plt
import numpy as np

#sum digits of n
def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

#get the sequence to n digits
def calculate(n):
    retval = [1]
    for i in range(n):
        retval.append(retval[-1] + sum_digits(retval[-1]))
    return retval;

#empirically confirm that a_n = 2^n mod 9
def confirmPow2(a):
    count = 0
    for i in a[:10000]:
        if((i%9) != (2**count % 9)):
            print "false"
        count = count + 1

#find gaps divisible by 9 in a subset of a
def find9Gaps(a):
    count = 0
    S = []
    for i in a[:10000]:
         S.append(((2**count ) - i)/9)
         count = count + 1
    return S

#repeatedly sum the digits until they're less than 9...
#gives some interesting patterns
def repeatedDigitSum():
    for i in range(1000, 1100):
         print "=========for ",i
         while i > 9:
                 i = sum_digits(i)
                 print i 


a = calculate(10**6)
b = find9Gaps(a)
plt.plot(range(len(b[:100])), b[:100])
plt.show()

La trama (para los primeros 100) parece exponencial, pero no creo que sea perfecta.

trama para huecos

Aquí está la salida de

>>> plt.plot(range(len(b[5:60])), np.log2(np.array(b[5:60])))
>>> plt.show()

diagrama logarítmico de las brechas

Lo último que tengo es que parece que si sumas los dígitos de un número, y luego sumas los dígitos del número resultante, y repites esto, eventualmente obtienes ese número mod 9.

Tiene sentido dado el hecho anterior sobre las potencias de 10 mod 9.

nortere(norte)re(re(norte))modificación9 9

Sin embargo, da una secuencia interesante de números.

Editar: Aparentemente esto se llama una "raíz digital".

quietContest
fuente
1
Fue un poco comentado al menos tres veces. Además, cuando traza una gráfica que le parece exponencial, ¿tal vez debería usar un logaritmo e informar sobre ello en el eje de escala? Si trazara 10 ^ 16 términos legibles, estaría realmente impresionado.
Mal
¿Qué fue comentado 3 veces? La gente decía que había un "patrón de mod 9", pero sentí que no estaba claro qué era. Acabo de explorar y comentar lo que tenía, ya que no creo que pueda seguir trabajando en esto. Una vez más, no tengo una solución, pero la pregunta no pidió una.
quietContest
Se agregó una trama de registro por sugerencia de EvilJS, no se puede trazar más grande porque se rompe el numpy y realmente no tengo tiempo para continuar persiguiendo este problema
quietContest