eulersPhi {numbers}

Eulers's Phi Function

Description

Euler's Phi function (aka Euler's ‘totient’ function).

Usage

eulersPhi(n)

Arguments

n

Positive integer.

Details

The phi function is defined to be the number of positive integers less than or equal to n that are coprime to n, i.e. have no common factors other than 1.

Value

Natural number, the number of coprime integers <= n.

Note

Works well up to 10^9.

See Also

primeFactors, Sigma

Examples

eulersPhi(9973)  == 9973 - 1                       # for prime numbers
eulersPhi(3^10)  == 3^9 * (3 - 1)                  # for prime powers
eulersPhi(12*35) == eulersPhi(12) * eulersPhi(35)  # TRUE if coprime

## Not run: 
x <- 1:100; y <- sapply(x, eulersPhi)
plot(1:100, y, type="l", col="blue",
               xlab="n", ylab="phi(n)", main="Euler's totient function")
points(1:100, y, col="blue", pch=20)
grid()
## End(Not run)