Project Euler 97: Find the last 10 digits of the non-Mersenne prime: 28433 × 2^7830457+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 2^6972593-1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p-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×2^7830457+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 10⁹) 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 M₃₅ through M₄₈. Since 430 BC when the first M.Prime was found, if those same techniques were used to find M₄₈, the sun would have since grown cold for over 10 billion years.

This program and method
solves all test cases
on HackerRank

Project Euler 97 Solution

Afterthoughts

• See also, Project Euler 48 Solution:
  
• See also, Project Euler 188 Solution: