Large non-Mersenne prime¶

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.

Idea¶

Only need to care about last 10 digits, so split $ 2^7830457 $ into $ 2^{\frac{7830457}{34} + 7830457\mod34} $, then power them up.

import sys, os; sys.path.append(os.path.abspath('..'))
from timer import timethis

for i in range(50):
    if len(str(pow(2, i))) > 10:
        print(i)
        break

34

@timethis
def solve():
    p = 7830457
    pp = p // 34
    r = p % 34
    p34 = pow(2, 34)
    last_10_digits = 1
    for _ in range(1, pp+1):
        n = last_10_digits * p34
        last_10_digits = n % int(1e10)
    return (last_10_digits * pow(2, r) * 28433 + 1) % int(1e10)

solve()

Run for 0.125 seconds

8739992577