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