¿Cómo fue la $3x+1$ problema comprobado hasta $5 \times 2^{60}$ ?

Question

El artículo de Wikipedia sobre el Conjetura de Collatz afirma que:

La conjetura se ha comprobado por ordenador para todos los valores de partida hasta $5 \times 2^{60} \approx 5.764 \times 10^{18}$ .

Da una cita en línea a la URL http://www.ieeta.pt/~tos/3x+1.html que parece haber expirado, y dirige a un instituto de investigación computacional llamado IEETA "Recuperado el 27 de noviembre de 2011". Buscando en su sitio 3x+1 , Collatz y conjecture me dejó con las manos vacías.

Q : ¿Cómo fue el $3x+1$ problema comprobado hasta $5 \times 2^{60}$ ?

Me interesa especialmente si hay mejoras algorítmicas no triviales sobre el cálculo directo. O tal vez esto era simplemente una cuestión de golpear con un gran ordenador ?

Answer 1

Basta con demostrar que para cada valor inicial $a_0>1$ Hay un poco de $k$ con $a_k<a_0$ .

• Tenemos $a_1<a_0$ si la secuencia de pasos comienza con abajo es decir, si $a_0\equiv 0\pmod 2$
• Tenemos $a_3<a_0$ si los pasos comienzan arriba, abajo, abajo (porque $\frac{3a_0+1}4<a_0$ para $a_0>1$ ); esto descarta $a_0\equiv 1\pmod 4$
• Mirando arriba, abajo, arriba, abajo, abajo, abajo podemos excluir $a_0\equiv 3\pmod {16}$

Incluso después de estas simples observaciones, ya hemos manejado $81.25\,\%$ de todos los números iniciales.

En general, una secuencia de $u$ y $d$ downs implica que $a_{u+d}=\frac{3^u a_0+c}{2^d}$ , donde $c\in\mathbb N$ depende del orden exacto de las subidas y bajadas. Proporcionado $3^u<2^d$ Esto elimina la clase de residuo $a_0\equiv 3^{-u}c\pmod{2^d}$ con posibles pequeñas ejecuciones (es decir, cuando $a_0\le \frac c{2^d-3^u}$ ). El truco de empujar el límite de $a_0$ más allá de $2^N$ es seguir investigando secuencias cada vez más largas de arriba y abajo .

Answer 2

La conjetura de Collatz dice que a partir de cualquier número entero $x \geq 1$ la secuencia de Collatz tendrá finalmente un elemento igual a 1. Es bastante fácil demostrar que es equivalente a lo siguiente: Para cada $x \geq 2$ la secuencia de Collatz tendrá finalmente un elemento menor que x.

Cambiamos la regla para que $x$ se sustituye por $\frac{3x + 1}{2}$ o con $\frac{x}{2}$ . Llamamos a la sustitución $x$ con $\frac{3x + 1}{2}$ un paso de impar, y $\frac{x}{2}$ un paso parejo. Si tenemos $o$ impar sale de $n$ pasos, entonces $x$ se sustituye aproximadamente por $\frac{3^o}{2^n}$ . $x$ se reduce si $o \times \log_2 (3) < n$ o $o < 0.63093n$ .

Si escribe $x$ como un entero binario, el último $n$ bits le dirá lo que el próximo $n$ pasos de la secuencia son. También te dice si después de alguno de esos $n$ pasos el resultado fue menor que $x$ . Así que inmediatamente se excluyen grandes cantidades de números del cálculo.

Entonces, para esos valores de la última $n$ bits que pasan esta prueba, se mira el último $2n$ bits. Calcula lo que el último $n$ bits será después de $n$ pasos, y comprobar con los datos precalculados si estos 2n bits conducirán a un valor menor dentro de $2n$ pasos.

Ahora se han reducido enormemente las cifras que hay que examinar. Y puede realizar $n$ pasos del cálculo en un solo paso. ( $n$ probablemente serán unos 24 más o menos).