¿Cuáles son los valores más grandes que terminan más rápido en esta secuencia?

Question

Si tenemos un número entero cualquiera $N$ mayor que $1$ , $$N=\prod_{n=1}^bP_n^{a_n}$$ donde $P_i$ es primo y $P_i<P_{(i+1)}$ , dejemos que $$F(N)=\prod_{n=1}^b(P_n^{a_n}-1)$$ Repita $F$ hasta que la secuencia termine, es decir, hasta que se alcance $1$ . Sabemos que terminará ya que $F(N)<N$ .

¿Existe un valor máximo $N$ que terminará en un determinado $a$ ¿Movimientos? Por ejemplo $2\to 1$ , por lo que sería $1$ mover. Ningún otro número termina en $1$ moverse. ¿Hay un límite para cada número de movimientos? Parece que la respuesta es sí, pero no sé exactamente por qué. Creo que tiene que ver con el hecho de que sólo un número finito de enteros devolverá un número entero determinado.

Answer 1

Sostiene que $F(N) > \sqrt{N}$ para $N > 6$ . Tenemos que comparar los factores de los productos $$F(N) = \prod (p_n^{a_n} - 1) \quad \text{and} \quad \sqrt{N} = \prod p_n^{a_n/2}.$$ De hecho, supongamos que queremos $N$ para satisfacer $F(N) \le \sqrt{N}$ . El único número natural $m = p_n^{a_n}$ para lo cual $m - 1 \le \sqrt{m}$ es $m = 2^1$ y la relación de estas cantidades en este caso es $1/\sqrt{2}$ . Para $m = 3$ la relación es $2/\sqrt{3}$ para $m \ge 4$ , es por lo menos $3/2$ .

Así que si $N$ es divisible por una potencia prima al menos 4, entonces el cociente $F(N)/\sqrt{N}$ es mejor que $3/2 \cdot 1/\sqrt{2} > 1$ . En particular, esto es cierto para $N > 6$ .

Ahora arreglar $a \ge 1$ . Si $N > 2^{2^{a+2}}$ entonces iterando la desigualdad $F(N) > \sqrt{N}$ se obtiene $F^a(N) > 2^{2^2}$ . Por lo tanto, hay un límite en los números que terminan después de $a$ pasos.

Answer 2

Arreglemos $N$ y por lo tanto $b$ El $P_i$ y el $a_i$ . Entonces, para cada $i$ ,

$$\begin{eqnarray} P_i && \geq && i+1 \\ \therefore P_i^{a_i} && \geq && i+1 \\ \therefore 1-\frac{1}{P_i^{a_i}} && \geq && 1-\frac{1}{i+1} \\ \therefore \frac{P_i^{a_i}-1}{P_i^{a_i}} && \geq && \frac{i}{i+1} \end{eqnarray}$$

Tomando el producto de $i=1$ a $i=b$ ,

$$\frac{F(N)}{N} \geq \frac{1}{b+1}$$

$N$ es al menos $(b+1)!$ . Por lo tanto, $b+1$ es como máximo el factorial inverso de $N$ . Por lo tanto, el factorial inverso de $F(N)$ es menor que el factorial inverso de $N$ como máximo en 1. Por inducción, cualquier $N$ más grande que $(b+1)!$ requiere al menos $b$ se mueve.

Answer 3

Método alternativo: $F(N) \ge \varphi(N)$ y es bien sabido que $\varphi(N)/N^{1-\varepsilon}$ va al infinito para cualquier $\varepsilon > 0$ ; ver Wikipedia. Aquí $\varphi$ es la función totiente de Euler.