Finding Mersenne primes with Python
Finding Mersenne primes with Python Data Science Project
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!
Start this project
Finding Mersenne primes with PythonFinding Mersenne primes with Python
Project Created by

Santiago Basulto

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.

Finding Mersenne primes with PythonFinding Mersenne primes with Python
Project Created by

Santiago Basulto

This project is part of

Python Collections

Explore other projects