Project Euler Problem 97 Solution

Question

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2697259312^{6972593}-1; it contains exactly 2,098,9602,098,960 digits. Subsequently other Mersenne primes, of the form 2p12^p-1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,2072,357,207 digits: 28433×27830457+128433\times2^{7830457}+1.

Find the last ten digits of this prime number.

Commentary

The gmpy library makes this problem trivial. Using gmpy, this code takes about half a second to run. Without gmpy, well, let’s just say it takes considerably more than a minute to run.

If you’re dealing with large numbers in Python, I highly recommend gmpy.

Python

#!/usr/bin/env python
from gmpy2 import mpz
print(str(mpz(28433*2**7830457+1))[-10:])
$ time python3 non-mersenne.py
real   0m0.358s
user   0m0.308s
sys    0m0.012s

Questions? Comments? Send me an email: [email protected]