Processing math: 100%

31 votos

Itera Euler ' función φ

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


          Phi_n100
          Curva roja: 0.43+1.22ln(n).


Φ(n) se ajustan bastante bien (y más allá de lo que se muestra arriba) por cln(n).

Dos preguntas:

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

Q2. Lo que explica el constante c1.22?

Probablemente ambos de estas preguntas son respondidas en la literatura.

21voto

user8269 Puntos 46

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

12voto

lhf Puntos 83572

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)/logn es denso en [1/log3,1/log2]. Lo que aún está en duda acerca de la k(n) es su promedio y normal comportamiento. Se conjetura que hay algunas constantes α tal que k(n)αlogn sobre un conjunto de densidad asintótica 1.

Aquí, k(n) es lo que el OP llama a Φ(n).

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X