¿Cuánto tiempo tarda esta secuencia en obtener este bucle?

Question

Para números enteros positivos $m,n$ definen una secuencia $S_m(n)$ para que $S_m(1)=m$ , $S_m(n+1)=S_m(n)^2-1$ si $S_m(n)$ es primo, y $S_m(n+1)$ es el mayor factor primo de $S_m(n)$ de lo contrario. Está claro que, independientemente de $m$ esta secuencia siempre queda atrapada en el bucle infinito $2,3,8,2,3,\dots$ porque para cualquier primo $p$ , $p^2-1=(p+1)(p-1)$ y si $p\neq 2$ entonces el mayor factor primo de este término es como máximo $\lceil p/2\rceil<p$ .

Lo que no está tan claro es la velocidad a la que la secuencia se queda atascada en ese bucle. Si definimos $t(m)$ para ser el menor número entero $n$ para que $S_m(n)=2$ Entonces, ¿cómo es que $t(m)$ ¿Crecer? Mediante algunas pruebas numéricas he descubierto que $t(m)<20$ para todos $m<10000$ lo que parece sugerir una velocidad de crecimiento logarítmica. En particular, para cualquier número entero positivo $N$ ¿es siempre cierto que existe un $m$ para que $t(m)>N$ ? Se agradece cualquier idea.

Answer 1

Registra la siguiente observación para poner en marcha el proceso.

Supongamos que $\ell>2$ es un Sophie Germain prime es decir, un primo tal que $p=2\ell+1$ también es un primo. En ese caso $$ (p+1)(p-1)=(2\ell+2)\cdot2\ell=2^3\cdot\frac{\ell+1}2\ell $$ lo que implica que $\ell$ es el mayor factor primo de $p^2-1$ . Así que si $S_m(n)=p$ entonces $S_m(n+2)=\ell$ .

Una cadena Cunningham de longitud $k$ es una secuencia de primos iterados de Sophie Germain $$p_1<p_2<p_3<\cdots<p_k$$ tal que $p_{i+1}=2p_i+1$ para todos $i$ . Por ejemplo, $5<11<23<47$ es la secuencia de Cunningham de longitud $4$ . La iteración del argumento del párrafo anterior nos dice que si $S_m(n)=p_k$ para algunos $m,n$ entonces $S_m(n+2(k-1))=p_1$ . Esto implica que si una cadena Cunngham de longitud $k$ existe, entonces se tarda alrededor de $2k$ pasos para que su secuencia se reduzca a $p_1$ .

Según la página citada de Wikipedia es una conjetura abierta que existan cadenas de Cunningham arbitrariamente largas. A la luz de lo anterior esa conjetura implicaría que la función $t$ no tiene límites.

---

Por supuesto, no es necesario tener cadenas de Cunningham cada vez más largas para $t$ para no tener límites. Me pareció que esta conexión podía ser interesante. Por supuesto, es fácil demostrar que el conjunto de factores primos de números de la forma $p^2-1$ es ilimitada, pero no pude ver cómo la ilimitación de $t$ se desprende de un hecho tan simple.