#-(and) "
P37 (**) Calculate Euler's totient function phi(m) (improved).
See problem P34 for the definition of Euler's totient function. If
the list of the prime factors of a number m is known in the form
of problem P36 then the function phi(m) can be efficiently
calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the
list of prime factors (and their multiplicities) of a given number
m. Then phi(m) can be calculated with the following formula:
phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...
Note that a ** b stands for the b'th power of a.
"
;;; https://secure.wikimedia.org/wikipedia/en/wiki/Euler%27s_totient_function#Computing_Euler.27s_function
(defun phi (m)
;; (p1 - 1) * p1 ** (m1 - 1)
;; + (p2 - 1) * p2 ** (m2 - 1)
;; + (p3 - 1) * p3 ** (m3 - 1)
;; + ...
(reduce (function *)
(mapcar (lambda (item)
(destructuring-bind (p-i m-i) item
(* (1- p-i) (expt p-i (1- m-i)))))
(prime-factors-mult m))))
;; There's something wrong, phi is not equal to totient-phi, so there
;; must be some error in the problem statements. We need to check them.
;; (loop
;; :for n :from 2 :to 100
;; :do (unless (= (totient-phi n) (phi n))
;; (format t "(totient-phi ~A) = ~A /= ~A = (phi ~A)~%"
;; n (totient-phi n) (phi n) n)))
;;;; THE END ;;;;