Thanks John, That sorted me out, sometimes I just can't get things worked out in my head, then get a sense of "instant enlightenment", which your comments did for me. I am ashamed to say I was using the wrong prime factors function, then changing the mult to mul all started to make sense. Thanks again Colin
2009/1/29 John Fouhy <j...@fouhy.net> > 2009/1/29 col speed <ajarnco...@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. >
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor