This is a way of finding how many coprimes there are for a number - eg 144
How many positive numbers less than or equal to 144 are relatively prime to
144?
Factor 144 = 2 4 × 3 2 .
Use the formula for each prime:
>From 2 4 , we get 2 - 1 = 1 and 2 4 - 1 = 2 3 = 8.
>From 3 2 , we get 3 - 1 = 2 and 3 2 - 1 = 3 1 = 3.
Multiply these numbers together to get the answer. 1 × 8 × 2 × 3 = 48.
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".
The website is
http://wiki.python.org/moin/ProblemSets/99%20Prolog%20Problems%20Solutions#Problem33.3ADetermineiftwonumbersarecoprime
I've attached a script that *should *work out the number of coprimes of 144
*Please don't bother too much about this. I've included it for your
information as syou have replied, but I think I'll leave it until I
understand a bit more - I'm biting off more than I can chew.*
Message: 6
Date: Wed, 28 Jan 2009 08:29:09 -0000
From: "Alan Gauld" <[email protected]>
Subject: Re: [Tutor] operator, mult
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; format=flowed; charset="iso-8859-1";
reply-type=original
"col speed" <[email protected]> wrote
> I got the following function while googling:
>
> def totient(n):
> 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)])
>
> I already have the "prime_factors" function. The problem is that I
> cannot
> find "mult".
Given it says mult is in operators then it must be (or have been
in a previous version) a standard Python operator that is intended.
Did it menton which version of Python was used? Is it an old site?
> I tried using "mul" which is in "operator" but that is
> obviously not the same thing.
How so? What did it do?
>>> from operator import mul
>>> reduce(mul,[1,2,3,4])
24
Does what I would expect it to do... What do you think mult should do?
Alan G
#!/usr/bin/env python
def prime_factors(n):
"""find factors of n using trial division by primes.
>>> prime_factors(315)
[3, 3, 5, 7]
"""
factors = []
for p in primeGenerator(n):
if p*p > n: break
while n % p == 0:
n /= p
factors.append(p)
if n != 1:
factors.append(n)
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 mul # change to "mult"?
if n == 1: return 1
return reduce(mul, [(p-1) * p**(m-1) for p,m in prime_factors_mul(n)]) # change to "mult?
print totient(144)
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
