Itera Euler ' función φ

Question

Deje $\phi(n)$ ser el de Euler totient función: $$ \phi(2)=1 \;,\; \phi(11)=10 \;,\; \phi(12)=4\;,$$ etc. Definir $\Phi(n)$ a ser el número de iteraciones $k$, de modo que $\phi^k(n)$ llega a $1$. Por ejemplo, $\Phi(25)=5$ porque $\phi(25)=20$ y de continuar, se tarda $5$ aplicaciones para llegar a $1$: $$25,20,8,4,2,1 \;.$$ Otro ejemplo: $\Phi(113)=7$: $$113,112,48,16,8,4,2,1 \;.$$ Aquí está una parcela de $\Phi(n)$:

---

         
          ^{Curva roja: $0.43 + 1.22 \ln( n )$.}

---

$\Phi(n)$ se ajustan bastante bien (y más allá de lo que se muestra arriba) por $c \ln(n)$.

Dos preguntas:

Q1. Lo que explica el crecimiento logarítmico, en un alto nivel?

Q2. Lo que explica el constante $c \approx 1.22$?

Probablemente ambos de estas preguntas son respondidas en la literatura.

Answer 1

Tenga en cuenta que $\phi(n)$ es incluso (para $n\ge3$), y si $n$ aun así es $\phi(n)\le n/2$. Esto inmediatamente le da límite logarítmico de superior de Pillai.

Answer 2

Erdős et al. decir esto en el Comportamiento Normal de la Recorre De algunas Funciones Aritméticas:

[...] es fácil ver que el conjunto de números de la forma $k(n)/ \log n$ es denso en $[1/ \log 3,1/ \log 2]$. Lo que aún está en duda acerca de la $k(n)$ es su promedio y normal comportamiento. Se conjetura que hay algunas constantes $\alpha$ tal que $k(n) \sim \alpha \log n$ sobre un conjunto de densidad asintótica $1$.

Aquí, $k(n)$ es lo que el OP llama a $\Phi(n)$.

El artículo original fue publicado en 1990. Quizás todavía es el estado de la técnica.