Euler’s Totient Function in R

Step 1

First we need to define a function to get all prime numbers smaller than the input value.

AllPrimes <- function(x){
  primes <- c()
  for (num in 1:x){
    is.prime <- F
    if (num > 1) {
      is.prime = T
      for (i in 2:(num - 1)) {
        if ((num %% i) == 0) {
          is.prime <- F
          break
        }
      }
    }
    if (num == 2)
      is.prime <- T
    if (is.prime) {
      primes <- c(primes, num)
    }
  }
  return(primes)
}

Example:

AllPrimes(15)

## [1]  2  3  5  7 11 13

AllPrimes(50)

##  [1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47

AllPrimes(100)

##  [1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Step 2

Second we need to program a function to extract prime factors for any givven number.

PrimeFactors <- function(x){
  primeFactors <- c()
  allPrimes <- AllPrimes(x)
  for (prime in allPrimes) {
    if(x%%prime == 0)
      primeFactors <- c(primeFactors, prime)
  }
  return(primeFactors)
}

Example:

PrimeFactors(10)

## [1] 2 5

PrimeFactors(97)

## [1] 97

PrimeFactors(prod(AllPrimes(15)))

## [1]  2  3  5  7 11 13

Step 3

Now we can implement the Phi() function.

Phi <- function(n){
  res <- n
  Ps  <- PrimeFactors(n)
  for (P in Ps) {
    res <- res * (1-(1/P))
  }
  return(res)
}

Examplpe

Phi(4)

## [1] 2

Phi(5)

## [1] 4

Phi(30)

## [1] 8

General plot

We apply the Phi() function to all the values in range 2 and 100, and store the result in phi variable and plot it.

vec <- 2:100
phi <- apply(matrix(vec, ncol = 1), Phi, MARGIN = 1)
plot(type="h", phi)
points(phi, col="red2")