P37: Calculate Euler’s totient function phi(m) (improved)

L-99 is a list of Prolog challenges with solutions in Lisp. However, the solutions you can find here are written in q.

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)] * ...

Note that a ** b stands for the b’th power of a.

qSolution

Using primeFactorsMult the solution is rather easy:

totientPhi2:{[n]
  if[n=1;:n];
  mult:primeFactorsMult n;
  :`int$(*/)(mult[;0]-1)*mult[;0] xexp mult[;1]-1;
  };

Example
totientPhi2 each 1+til 15
1 1 2 2 4 2 6 4 6 4 10 4 12 4 8