Deje ϕ(n)ϕ(n) ser el de Euler totient función: ϕ(2)=1,ϕ(11)=10,ϕ(12)=4,ϕ(2)=1,ϕ(11)=10,ϕ(12)=4, etc. Definir Φ(n)Φ(n) a ser el número de iteraciones kk, de modo que ϕk(n)ϕk(n) llega a 11. Por ejemplo, Φ(25)=5Φ(25)=5 porque ϕ(25)=20ϕ(25)=20 y de continuar, se tarda 55 aplicaciones para llegar a 11: 25,20,8,4,2,1.25,20,8,4,2,1. Otro ejemplo: Φ(113)=7Φ(113)=7: 113,112,48,16,8,4,2,1.113,112,48,16,8,4,2,1. Aquí está una parcela de Φ(n)Φ(n):
Curva roja: 0.43+1.22ln(n)0.43+1.22ln(n).
Φ(n)Φ(n) se ajustan bastante bien (y más allá de lo que se muestra arriba) por cln(n)cln(n).
Dos preguntas:
Q1. Lo que explica el crecimiento logarítmico, en un alto nivel?
Q2. Lo que explica el constante c≈1.22c≈1.22?
Probablemente ambos de estas preguntas son respondidas en la literatura.