99 problems - python - 37

Calculate Euler's totient function phi(m) (improved). See problem 34 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 36 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. Note: Actually, the official problems show this as a sum, but it should be a product.

# using prime_factors_mult from earlier
def totient_phi2(n):
    if n == 1:
        return 1

    def product(lst):
        return reduce(lambda x,y: x*y, lst)
    return product([((p-1)*(p**(m-1)))  for (p, m) in prime_factors_mult(n)])

I'm pretty sure that "reduce" will be leaving python 3. We hardly knew ye. I don't understand that removal. Of course I'll just be adding it right the hell back in. And no one can stop me!