Euler's totient function

:For other meanings, see Euler function (disambiguation).

Growth of the function

The growth of φ(n) as a function of n is an interesting question, since the first impression from small n that φ(n) might be noticeably smaller than n is somewhat misleading. Asymptotically we have

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:n1−ε < φ(n) < n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for any given ε > 0 and n > N(ε). In fact if we consider

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:φ(n)/n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

we can write that, from the formula above, as the product of factors

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:1 −p−1

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

taken over the prime numbers p dividing n. Therefore the values of n corresponding to particularly small values of the ratio are those n that are the product of an initial segment of the sequence of all primes. From the prime number theorem it can be shown that a constant ε in the formula above can therefore be replaced by

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:C log log n/log n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This behavior also holds in an average sense:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:rac{1}{n^2} sum_{k=1}^n arphi(k)= rac{3}{pi^2} + mathcal{O}left(rac{ln n }{n} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where the big O is the Landau symbol.

Related Topics:
Big O - Landau symbol

~ ~ ~ ~ ~ ~ ~ ~ ~ ~