Reducir el tiempo para calcular secuencias de Collatz

Question

Estoy resolviendo el problema clásico de cálculo, por lo que el número en un intervalo de $[a,b]$ la secuencia de Collatz lleva a la mayoría de los pasos para llegar a $1$. Hay un algoritmo que necesita menos de $\cal O(n)$ del tiempo, para calcular el número de pasos para llegar a $1$ donde $n$ es el número de pasos necesarios?

Además, estoy interesada en saber si es posible conseguir la aceleración por descartar ciertos candidatos de la entrada de intervalo. Yo ya lo hago calcular algunos pasos a la vez mediante la visualización de la entrada de $a \bmod 2^k$ algunos $k$, pero el extra de memoria que se necesita es bastante.

Answer 1

El experto en gran escala de Collatz cálculos es Tomás de Oliveira e Silva, quien tiene un sitio web con mucha información. También vale la pena un vistazo a Eric Roosendaal del sitio web.

Answer 2

Para un intervalo de $1..b$, todos los números congruentes 2, 4, 5 o 8 módulo 9 puede ser ignorado porque de estas producciones mirando con un número menor:

$$6z + 1 \rightarrow 18z + 4 \rightarrow 9z + 2$$ $$6z + 3 \rightarrow 18z + 10 \rightarrow 9z + 5$$ $$6z + 5 \rightarrow 18z + 16 \rightarrow 9z + 8$$

$$8z + 3 \rightarrow 24z + 10 \rightarrow 12z + 5 \rightarrow 36z + 16 \rightarrow 18z + 8 \rightarrow 9z + 4$$

Del mismo modo, todos los números congruentes modulo 5 8 puede ser ignorado , ya que estos dos caminos se unen después de tres pasos:

$$8z + 5 \rightarrow 24z + 16 \rightarrow 12z + 8 \rightarrow 6z + 4$$ $$8z + 4 \rightarrow 4z + 2 \rightarrow 2z + 1 \rightarrow 6z + 4$$

De esta manera podemos reducir el conjunto de los números para ser revisado por un factor de $\frac59\cdot\frac78 = \frac{35}{72}$.

También la mitad inferior del intervalo puede ser omitido (como incluso los números de "caer" en ellos), vuelve a guardar el factor 2. Por lo que una reducción de alrededor de un cuarto puede ser adquirida(*).

Pero la más importante speedup puede ser obtenido haciendo varios pasos a la vez, como se describe en la Wikipedia. Con una pequeña tabla de $2^{17}$ elementos, de 17 pasos a la vez que se puede hacer, que conduce a una velocidad de seguridad tal vez 10 (los pasos son un poco más complicados que los directos de computación). AFAIK este es el más grande de tabla de ajuste en la memoria caché.

Cuando la búsqueda de la maximizer, sin embargo, el número de pasos necesarios para exceder la corriente máxima que puede ser utilizado para una búsqueda en una tabla derivada de este para determinar si el valor actual necesita ser ampliado aún más. Esto le da un factor adicional de 2 para el intervalo de $1..10^{10}$.

Este fantástico enlace da mucho más complicado consejos de optimización que permite omitir la comprobación de la mayoría de los números restantes.

---

(*) Por un intervalo de $a..b$, esto sólo se aplica parcialmente.

Answer 3

No estoy acostumbrado a esta forma de mirar el collatz-problema y parece ser realmente incapaces de abrir mi mente en este momento. Pero, posiblemente, las siguientes observaciones ayuda de todos modos.
Si nos fijamos en la operación inversa, por extraño $\small a_k $ definir $ \small a_{k+1,A} = (2^A*a_k -1)/3 $ todos Una que mantenga $ a_{k+1,A} $ impar y entero y comienzo a $\small a=1$, esto forma un árbol que debe contener todos los impares enteros positivos si la collatz-conjetura es verdadera.

Entonces vemos, que con un poco de $ \small a_k $ todos los $ \small 4 a_k + 1, 4(4 a_k+1)+1, ... ,{4^j a_k -1 \over 4-1 }, \ldots $ están en el árbol. Del mismo modo, esto puede ser expresado usando 64 en lugar de 4 , y así sucesivamente. Ver el gráfico en http://go.helms-net.de/math/collatz/aboutloop/collatzgraphs.htm donde he recogido algunos tipos de árboles, de las representaciones y, particularmente, en el que se expresa en la base-4-numbersystem.

No sé de inmediato, si la representación de ayuda cuando el foco está en la consideración de un intervalo de como es en la cuestión actual, pero tal vez puedo volver a ese problema de nuevo más tarde con una nueva idea...