Calcular el máximo de la secuencia de Collatz

Question

Consideremos la famosa función de Collatz $$T(n) = \begin{cases}(3n+1)/2&\text{ if $n$ is odd,}\\n/2&\text{ if $n$ is even.}\end{cases}$$

Una de las técnicas de aceleración más importantes de la prueba de convergencia es el uso de un tamiz (prueba $k$ bits menos significativos de $n$ el tamiz tiene el tamaño de $2^k$ entradas), y probar sólo los números que no se unen a la ruta de un número inferior en $k$ pasos. Esta técnica está muy explicada, por ejemplo, aquí o aquí .

Por ejemplo, considere el tamiz para $k=2$ y en particular los números de la forma $4n+1$ que se unen a la ruta de $3n+1$ en dos pasos. Su camino es $$4n+1 \rightarrow 6n+2 \rightarrow 3n+1 \text{.}$$

Lo que no entiendo es cómo se puede utilizar esto para buscar el número más alto que aparece en la secuencia ( registros de la trayectoria en la terminología de Eric Roosendaal). El tamiz corta el cálculo antes de la computación de cualquier valor intermedio (que en realidad puede ser el máximo, como el valor $6n+2$ en el ejemplo anterior). ¿Cómo puedo detectar que $4n+1$ lleva a un máximo si no hay $6n+2$ ¿se calcula? Comprobación de la trayectoria de $3n+1$ ya no tiene sentido porque el máximo $6n+2$ se produce antes de este plazo. ¿Me he perdido algo?

Answer 1

Cita: "Como $k$ aumenta, la búsqueda sólo necesita comprobar aquellos residuos $b$ que no se eliminan con valores más bajos de $k$ "

Por ejemplo, el residuo 15. Sobrevive $\mod 2^5$ pero se elimina al tamizar $2^7$ por lo que cualquier valor $x\equiv 15 \mod 2^7$ no se buscará más por $k>7$

El residuo 15 se eliminó porque alcanzó un valor inferior a sí mismo $\mod 2^7$ . Esto significa que estos números no pueden alcanzar valores más altos, más tarde con $k>7$ que no se alcanzaron (con una menor $k$ ) por el valor inferior que acaban de alcanzar.

Answer 2

(Notación: residuo $n_0\mod 2^{\lceil i \log_23\rceil}$ = residuo $b\mod2^k$ de su página wiki)

Sobre el "descartado" 5 que alcanza el máximo 8 (o 16), ya alcanzado por el "superviviente" 3:

• Uno de los desechado es la secuencia V-Shape inversa que se eleva para $i$ pasos de $f(x)=\frac{3x+1}{2}$ y luego baja por debajo del valor inicial por la división sucesiva por $2$ ( Ver aquí ). De todas las secuencias descartadas $2^{\lceil i \log_23\rceil}n+n_0$ para un determinado $n$ , este es el tipo de secuencia que potencialmente alcanza el valor más alto: $$(2^{\lceil i \log_23\rceil}n+n_0+1)\frac{3^i}{2^{i}}-1$$

Nota: $n_0\leq 2^{\lceil i \log_23\rceil}-3$ y el valor exacto se puede encontrar en el enlace anterior

por ejemplo, con $4n+1=5$ donde $n_0=1$ , $i=1$ , $n=1$ que alcanza $8$ antes de bajar a $4<5$

• Uno de los sobreviviendo a secuencia es la línea recta que sube por toda la $k={\lceil i \log_23\rceil}$ pasos de $f(x)=\frac{3x+1}{2}$ . De todas las secuencias supervivientes para un $n$ Esta es la secuencia (a partir de $2\cdot2^{\lceil i \log_23\rceil}n-1$ ) que alcanza el valor más alto (limitado a $k={\lceil i \log_23\rceil}$ pasos): $$3^{\lceil i \log_23\rceil}(n+1)-1$$

Nota: aquí siempre tenemos $n_0= 2^{\lceil i \log_23\rceil}-1$

por ejemplo, con $4n+3=7$ donde $i=1$ , $n=1$ que alcanza $17$ (en 2 pasos), o con $n=0$ : $3$ llega a $8$

Ahora es fácil demostrar que el mayor valor que puede alcanzar una secuencia descartada en $n$ es menor (o igual) que el valor más alto ya alcanzado por una secuencia superviviente en $n-1$

por ejemplo, con el descarte $4(1)+1=5$ llega a $8$ que ya fue alcanzada por los supervivientes $4(1-1)+3=3$

El valor más alto que sobrevive en $n-1$ es mayor que el valor descartado en $n$ ?

$$3^{\lceil i \log_23\rceil}n-1 \geq (2^{\lceil i \log_23\rceil}n+n_0+1)\frac{3^i}{2^{i}}-1$$ y con $n_0< 2^{\lceil i \log_23\rceil}-1$ Sólo tenemos que demostrar que $$3^{\lceil i \log_23\rceil}n-1 \geq (2^{\lceil i \log_23\rceil}(n+1))\frac{3^i}{2^{i}}-1$$ $$\Big(\frac{3}{2}\Big)^{\lceil i \log_23\rceil}n \geq \Big(\frac{3}{2}\Big)^i(n+1)$$ $$\Big(\frac{3}{2}\Big)^{\lceil i \log_2\frac{3}{2}\rceil} \geq 1+\frac{1}{n}$$ lo que ya es cierto para $n-1=0$ cuando $i\geq 3$ (comprobado manualmente para $i=1$ y $i=2$ utilizando el valor exacto de $n_0$ en esos casos)

por ejemplo, con $n-1=0$ : desechado $32n+23$ llega a $188$ pero sobreviviendo $32(n-1)+31$ ya se ha alcanzado $242$

Nota: puedes multiplicar ambos lados por 2 para obtener el máximo "real" (16 en lugar de 8).

La idea clave es que incluso si la forma V inversa descartada en $n$ estaba en el residuo más alto posible $n_0= 2^{\lceil i \log_23\rceil}-3$ alcanzaría un valor menor que la línea recta en $n-1$ (siempre con residuos $n_0= 2^{\lceil i \log_23\rceil}-1$ ).

Esto significa que las rutas de registro siempre se encuentran en el residuo $b\mod2^k$ (en otras palabras, en $2^k\cdot n+b$ con $n=0$ )

EDITAR:

aún más, al tamizar $2^{k+1}$ Valores de la tabla: valores inferiores a $2^k$ que están cayendo no pueden producir nuevos registros de ruta (obviamente), pero el valor por encima de $2^k$ que no sobreviven después de $2^{k+1}$ tamiz son ahora conocidos, y allí el máximo sigue siendo el RHS arriba: de hecho la condición $n_0+2^{\lceil i \log_23\rceil}< 2^{\lceil i \log_23\rceil+1}-1$ o $n_0< 2^{\lceil i \log_23\rceil}-1$ no cambian, y el valor de $i$ (escalones de subida) ni desde el último paso fue una caída por debajo del valor inicial.

Por lo tanto, aunque el valor máximo en el LHS no suba más en el paso $k+1$ La cantidad de dinero que se puede gastar en un proyecto es mayor (la ecuación se mantendría igual).

Esto significa que las nuevas rutas de registro sólo se encuentran en sobreviviendo a residuo $b\mod2^k$

No es necesario comprobar el residuo desechado en absoluto, ni siquiera dentro del rango del tamiz.