Variación Collatz: La Rana Prime

Question

En codegolf.SE, había un post sobre una variación de Collatz llamada " la rana de primera ". Se pidió a los usuarios que crearan un código que iterara la función

$$f(n)=\bigg\{\begin{array}{cc}2n-1 & \mathrm{if\ }n\mathrm{\ is\ prime} \\ n-d &\mathrm{otherwise}\end{array}$$

donde en el segundo caso, $d$ es el mayor divisor primo de $n$ . Se pidió a los usuarios que indicaran si la función (dada una entrada concreta) se quedaba atascada en el bucle

$$3\to 5\to 9\to 6\to 3$$

o el bucle

$$19\to 37\to 73\to 145\to 116\to 87\to 29\to 57\to 38\to 19.$$

Mi pregunta es: ¿Se puede demostrar que esto siempre termina en uno de estos dos bucles? Según Keyu Gan en el post original, se ha probado para primos hasta $10^8$ .

Como era de esperar, no he podido avanzar mucho. Las únicas cosas que he descubierto son relativamente elementales:

1. Si un número compuesto $pm$ tiene $m\leq p$ ( $p$ es primo), la secuencia se reducirá a $p$ . En concreto, para un producto de primos $pq$ la secuencia se reducirá al mayor de los dos primos.

2. Si $p$ es el mayor primo que divide a $n$ el siguiente primo en la secuencia formada iterando $n$ será $\geq p$ .

¿Alguna idea?

Answer 1

No sé lo suficiente sobre números primos y el Teorema de los Números Primos como para dar una respuesta definitiva, pero en general puedo explicar el comportamiento del algoritmo de la rana prima y explicar cómo podrías romperlo.

$2n-1$ es una Regla de Collatz que toma sus números de partida impar $n$ hasta el infinito. Esto ocurre porque cada número impar se itera a otro número impar, por lo que nunca se realiza $n/2$ o reduciendo. Esta regla es conveniente para el algoritmo de la "rana prima" porque todos los números primos son Impares, pero no todos los números Impares son primos (excepto 2, pero 2 va a 3 así que ¿a quién le importa?).

La segunda parte del algoritmo es $n-d$ que a veces se reduce a $d$ . Cuando no se reduce a $d$ se filtrará a través de diferentes $n(d)$ hasta que alcance un factor primo final mayor.

La acción "disminuir" reducirá un número $n$ en un mínimo del 50%, suponiendo que se reduzca a la $d$ de $n$ . Si la reducción conduce a otro número primo, es posible que la operación $2n-1$ puede compensarlo. Sin embargo, esto sólo ocurriría si se produjera una reducción inferior al 50% aproximadamente del número compuesto original una vez alcanzado un número primo. Viendo cómo las condiciones de 'la rana prima' son ciertas hasta $10^8$ en el mejor de los casos.

Sin embargo, la reducción o el crecimiento globales se basan en el número de veces que la operación $2n-1$ alcanza otro número primo y cuánto se redujo del número compuesto anterior. Esta relación de aumento y disminución es diferente de la de $3n+1$ y tiene más que ver con cuántas veces se alinearán los números primos después de realizar $2n-1$ y la factorización de los números durante el proceso y después.

Como era de esperar, se produce un bucle de la regla de Collatz cuando la cantidad de "decreciente" se "anula" con la cantidad de "creciente". Dado que los números primos establecen las reglas sobre la cantidad de cambio que se produce y cuándo, va a ser difícil predecir, y mucho más probar la existencia de otros bucles. Por lo tanto, es completamente posible que existan otros bucles.

Debido a la imprevisibilidad de este algoritmo en cuanto a cuánto se reduce un número compuesto, es posible que los números correctos puedan recrear el comportamiento "creciente" general de $5n+1$ . El algoritmo de la 'rana primo' también podría vagar hasta el infinito realizando $2n-1$ para siempre. No sé si esto es cierto, pero el Teorema de los Números Primos podría utilizarse para averiguar si una cadena de números primos puede o no existir. Al menos puedo admitir la operación $2n-1$ para cualquier $n$ siempre creará otro número $k$ con una factorización de primos que no contenga ninguno de $n$ o ser divisible por 2.