¿Esta extensión de la secuencia de Collatz convergen para n = 550?

Question

La función de Collatz, o $3n + 1$ función es bien conocido. Una heurística argumento de que la mayoría de las entradas deberían converger con la aplicación repetida de la función es como sigue. Con una probabilidad de 1/2 de entrada de $n$ será par o impar. Si es que, incluso, será multiplicado por un factor de 1/2. Si es impar, será multiplicado por un factor de aproximadamente 3, y luego se divide por 2. Así, en promedio, se esperaría que la tasa de crecimiento por dos iteraciones para ser $\frac{1}{2}*\frac{3}{2} = \frac{3}{4} < 1$.

Ahora considere la siguiente extensión a los números de $p$$q$.

$f(n) = \begin{cases} n/p & \quad \text{if } n \text{ is divisible by }p\\ qn \text{ rounded up to the nearest multiple of }p & \quad \text{if } n \text{ is not divisible by }p\\ \end{casos}$

También podemos expresar esta función (para facilidad de cálculo)

$f(n) = \begin{cases} n/p & \quad \text{if } n \text{ mod }p=0\\ qn + p - (qn\text{ mod }p) & \quad \text{otherwise}\\ \end{casos}$

A continuación, de forma heurística podemos argumentar que una entrada de $n$ $\frac{1}{p}$ de probabilidad de ser un múltiplo de $p$ y, por tanto, será multiplicado por el $\frac{1}{p}$ $\frac{p-1}{p}$ de probabilidad de ser multiplicada por un factor de $\frac{q}{p}$. Por lo que el promedio del factor de crecimiento esperamos que después de $p$ iteraciones es $\frac{1}{p}(\frac{q}{p})^{p-1}$.

Ahora, considere el caso $p=3$, $q=5$. La heurística del factor de crecimiento es $\frac{1}{3}(\frac{5}{3})^2 = \frac{25}{27} < 1$, por lo que podemos predecir la convergencia. De hecho, por cada partida $n \leq 549$ la secuencia formada por la aplicación repetida de $f$ converge a uno de los dos ciclos.

$4 \rightarrow 21 \rightarrow 7 \rightarrow 36 \rightarrow 12 \rightarrow 4$

$8 \rightarrow 42 \rightarrow 14 \rightarrow 72 \rightarrow 24 \rightarrow 8$

Sin embargo, la secuencia, comenzando con $n = 550$ eventualmente se desborda la aritmética de enteros en Matlab. (~$10^{200}$). Tenga en cuenta que la secuencia se cierne en el $10^{15}$ rango por un tiempo antes de que las nubes directamente a $10^{200}$, por lo que no acabo de confiar en el cálculo.

Puede que alguien o $(a)$ muestran que $550$ realmente hace converger utilizando mejor los caracteres numéricos o $(b)$ demostrar que $550$ diverge?

Answer 1

Aquí le damos un poco de python que se puede ejecutar esta tarea.

def f(n, p, q, max_trials=10000):
    if n <= 0:
        return 0
    trial = 0
    ret = []
    while (n != 4) and (n != 8) and (trial<max_trials):
        ret.append(n)
        if n%p == 0:
            n = n/p
        else:
            n = q*n + p - (q*n % p)
    return ret

if __name__ == "__main__":
    print f(550, 3, 5)

Como se mencionó en los comentarios, la secuencia termina en un lazo en el paso 2831st. Hay $8$ números en la secuencia más grande que $10^{17}$, $77$ mayor que $10^{16}$ y $167$ mayor que $10^{15}$. Tan los términos "más" en la secuencia son más pequeños que $10^{15}$.