Problem Description

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 the understanding from Problem 48.

Solution

Runs < 1 seconds in Python.

def PE97(a, b, c, m):
    return (c * pow(a, b, 10**m) + 1) % 10**m
print "Answer to PE97 = ",PE97(2, 7830457, 28433, 10)

Comments

• See also problem 48 & problem 188.
• Perl allows underscores to be used in numeric literals for readability.
• Don’t forget that leading zeros are not printed.

You can reduce the number of iterations significantly by breaking out the multiplication as follows:

my $max_n = 7_830_457;
my $m = 1e10;
my $nx = 1;
 
$nx = ($nx * 2**100) % $m for (1..$max_n/100);
$nx = ($nx * 2) % $m for (1..$max_n%100);
 
print "Answer to PE97 = ",($nx * 28_433 + 1) % $m,"n";

This version runs in a fraction of a second in Perl.