Topic: Euler totient function

[Jeremy]

I was trying to write some code for the Euler totient function and tried translating a C code snippet that I found. My end result was

Code: [Select]

;; Euler totient function for positive integers n
(defun totient ( n / result i )
  (setq result n)
  (setq i 2)
  (while (<= (* i i) n)
    (if (zerop (rem n i))
        (setq result (- result (/ result i)))
    )
    (while (zerop (rem n i))
      (setq n (/ n i))
    )
    (setq i (1+ i))
  )
  (if (> n 1)
      (setq result (- result (/ result n)))
  )
  result
)

This seems to work but I was wondering if anyone else has written their own algorithm knowing more of what they are doing than I am.

[irneb]

Well, the simplest "brute force" method:

Code - Auto/Visual Lisp: [Select]

1. (defun totient-brute-force  (n / k count)
2.   (setq count 0
3.         k n)
4.   (while (> k 0)
5.     (if (= (gcd k n) 1)
6.       (setq count (1+ count)))
7.     (setq k (1- k)))
8.   count)

But that's going to be a lot less optimal than any decent way. The loop itself is already O(N), but the gcd itself is an added O(log N). So that means it's O(N log N). Not to mention the GCD is (probably) using divisions to calculate - which in themselves are a lot less optimal than multiplication. Of course that takes no account of some of the totient's properties (e.g. a totient of a prime = one less the prime, a totient of a factor of two coprimes = the factor of each coprime's totient, etc.) - which is what your code makes use of.

Since this is a very similar idea to finding primes, perhaps a form of the Sieve of Eratosthenes would be more optimal (though for large numbers would consume huge amounts of RAM). E.g. http://abhisharlives.blogspot.com/2013/03/euler-totient-function-in-3-ways.html