# [Tutor] operator, mult

John Fouhy john at fouhy.net
Thu Jan 29 05:38:50 CET 2009

```2009/1/29 col speed <ajarncolin at gmail.com>:
[...]
> What I expected  "mult" to do was (somehow)to work out  what the powers of
> the prime factors would be. Another reason I didn't think it was "mul" is
> the part that says "  prime_factors_mult(n)" as the prime_factors function
> is just "prime_factors(n)" - without the "_mult".

Well, it's been a while since my number theory course, so I was just
going from the code comments:

def totient(n):
"""calculate Euler's totient function.

If [[p_0,m_0], [p_1,m_1], ... ] is a prime factorization of 'n',
then the totient function phi(n) is given by:

(p_0 - 1)*p_0**(m_0-1) * (p_1 - 1)*p_1**(m_1-1) * ...

>>> phi(1)
1
>>> phi(10)
4
"""
from operator import mult

if n == 1: return 1

return reduce(mult, [(p-1) * p**(m-1) for p,m in prime_factors_mult(n)])

If we imagine for a moment that we have:

prime_facs = [(p_0, m_0), (p_1, m_1), (p_2, m_2), (p_3, m_3)]

then

reduce(operator.mul, [(p-1) * p**(m-1) for p,m in prime_facs])

translates exactly to

(p_0-1)*p_0**(m_0-1) * (p_1-1)*p_1**(m_1-1) * (p_2-1)*p_2**(m_2-1)
* (p_3-1)*p_3**(m_3-1)

which seems to match the description in the comment.

--
John.
```

More information about the Tutor mailing list