Euclid proved that if both p and 2**p - 1 are prime then (2**p - 1) * (2**(p-1))
ID: 3750505 • Letter: E
Question
Euclid proved that if both p and 2**p - 1 are prime then (2**p - 1) * (2**(p-1)) is a perfect number.
If p and 2**p - 1 are both prime, 2**p - 1 is known as a Mersenne prime.
Euler proved that there is a 1-1 correspondence between Mersenne primes and the even perfect numbers. (It is not known whether there are any odd perfect numbers.) See Wikipedia for details.
Complete this function with a list comprehension. (It's easier than it looks.) Use the answers from previous questions to generate the primes and to test for being prime.
def EuclidEulerPerfectNumbers(k):
"""
Returns a list of triples of the form ( p, 2**p - 1, perfect ),
where p and 2**p - 1 are prime, perfect is the associated perfect number,
and p is in range(2, k+1).
For example
print(EuclidEulerPerfectNumbers(19)) =>
[(2, 3, 6), (3, 7, 28), (5, 31, 496),
(7, 127, 8128), (13, 8191, 33550336),
(17, 131071, 8589869056), (19, 524287, 137438691328)]
Even though some of the numbers are very large, this takes less than 1 second to run.
"""
return <your list comprehension>
Explanation / Answer
The list comprehension is
[(x, pow(2,x)-1, (pow(2,x)-1)*pow(2, x-1)) for x in range(2, k+1)
if all([x % y != 0 for y in range(2,x)] + [(pow(2,x)-1) % y != 0 for y in range(2,(pow(2,x)-1))] )]
So the function looks like this
def EuclidEulerPerfectNumbers(k):
return [(x, pow(2,x)-1, (pow(2,x)-1)*pow(2, x-1)) for x in range(2, k+1) if all([x % y != 0 for y in range(2,x)] + [(pow(2,x)-1) % y != 0 for y in range(2,(pow(2,x)-1))] )]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.