Python Collections

Finding Mersenne primes with Python

Mersenne primes are a specific type of prime numbers that are extremely important in the field of computing, number theory and cryptography. They're defined as any prime number that can also be written in the form `2^n - 1` (for any integer `n`). In this project, you'll be tasked with reading 1 million prime numbers form a text file, and identifying the Mersenne primes in there. All using Python lists and sets!
Project Created by

Project Activities

All our Data Science projects include bite-sized activities to test your knowledge and practice in an environment with constant feedback.

All our activities include solutions with explanations on how they work and why we chose them.

codevalidated

Write the function `is_mersenne` to identify if a prime is a Mersenne prime

Write the function `is_mersenne` that receives a single prime number `p` and returns `True` if it is a Mersenne prime, or `False` otherwise.

codevalidated

Find all Mersenne primes

Now it's time to find which of the prime numbers in the `primes` variable are indeed Mersenne primes. Find all Mersenne primes and store them in the variable `mersenne_primes`. Your list will contain the elements `[3, 7, 31, 127, ...]`.

codevalidated

Create the list `mersenne_numbers`

Create a list of Mersenne numbers from `1` up to the one that is larger than the largest prime in the list of primes. That is, suppose our list of primes contained the first 12 primes: `[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]`

You should start calculating all integers starting from 1

``````1 = (2^1) - 1 = 1
2 = (2^2) - 1 = 3
3 = (2^3) - 1 = 7
4 = (2^4) - 1 = 15
5 = (2^5) - 1 = 31
6 = (2^6) - 1 = 63  <<<< 63 is LARGER than the largest prime in our list, which is 37. This is NOT included.
``````

In this case, your list should contain only the mersenne numbers: `[1, 3, 7, 15, 31]`.

codevalidated

Even more efficient, turn `mersenne_numbers` into a set

We'll use the list `mersenne_numbers` to check which numbers in `primes` are Mersenne numbers. So, the ultimate efficient gain will be to turn `mersenne_numbers` into a set, as the operations of membership in sets are `O(1)`.

Transform the variable `mersenne_numbers` into a set containing the same elements.

codevalidated

Find Mersenne primes using `mersenne_numbers`

Now, create a new variable `efficient_mersenne_primes` that contains all the mersenne numbers (same as before), but this time, check if the prime is a mersenne using the set `mersenne_numbers` created in the previous activity.

Project Created by

Santiago Basulto

This project is part of

Python Collections

Explore other projects