(11 votes, average: 5.00 out of 5)

Project Euler 97: Find the last 10 digits of the non-Mersenne prime: 28433 × 27830457+1

Project Euler 97 Problem Description

Project Euler 97: The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593-1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p-1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.
Find the last ten digits of this prime number.

Analysis

We recognized we could reuse our understanding from Problem 48 and print the result with a left-side zero fill to provide for leading zeros if they exist.

To prevent having to deal with a power with millions of digits we use the third parameter in the intrinsic Python `pow()` function to perform the power modulus. Then taking the modulus again after performing the multiplication to keep the result to 10 digits.

In the HakerRank version, more aggressive parameters (up to 109) are provided for hundreds of thousands of test cases and then the results from the test cases summed.

Something I’ve always found interesting and continue to support is the Great Internet Mersenne Prime Search (GIMPS). It uses aggregated computing and since 1996 has found the Mersenne primes M35 through M48. Since 430 BC when the first M.Prime was found, if those same techniques were used to find M48, the sun would have since grown cold for over 10 billion years.

Project Euler 97 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 97 Solution Python 2.7 source.

Afterthoughts

Project Euler 97 Solution last updated