I am almost embarrassed to make a post about problem 97 of Project Euler which reads

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: 284332^{7830457}+1.

Find the last ten digits of this prime number.

I decided to use the BigInteger class for solving this, so I didn’t have to care about numerical issues. The only other insight that was needed was to use the ModPow method which takes the modulo along with the power instead of doing those seperatly.

When doing that the code looks like

long mod = 10000000000; BigInteger result = 28433 * BigInteger.ModPow(2, 7830457, mod) +1; result %= mod;

It could have been done in a oneliner, but then I couldn’t fit it onto the website without scrolling.

This runs in

The last 10 digits are 8739992577 Solution took 0,062 ms

What took the longest was the fact that I forgot to add one to the end of the result.

You can find the source file here as usual.

;_;

I don’t have modpow in tcl, and that single calculation (2 to the power of ridiculousness) doesn’t work for me, it overloads the cpu & never returns.

(Normally your explanations are very helpful when I’m stuck and I’m looking for direction btw, thank you for that).

But for anyone who’s interested in solving this problem without using this modpow witchcraft, the following should be of some use. I played around with the powers of 2 and observed:

– the powers of 2, modulo 10, follow a pattern of length 4, starting at 2^1 (2,4,8,6,2,4…)

– the powers of 2, modulo 100, follow a pattern of length 20, starting at 2^2 (04,08,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52,04,08,16…)

– the powers of 2, modulo 1000, follow a pattern of length 100, starting at 2^3

So there’s a more general pattern, where the powers of 2, modulo 10^n

follow a pattern of length 4*5^(n-1), starting at 2^n. It seems like there should be some way to prove this, but it’s beyond me.

Anyway, the upshot of all this is that

(2^7830457)%10000000000 = (2^17957)%10000000000

I thought I had a nice solution and then come here to see something that “could be a one-liner”. 🙂

I used a loop to multiply a long X by 2 7830457 times. Each time I convert the value to a string and see if its length exceeds 10. If so, then chop off the left most digits, convert back to a long, and assign to X. Once the loop is done, multiply by 28433 and add 1.

Done in under a minute.

Since I mostly use C++, I like to avoid biginteger packages whenever possible. I had run into “modular exponentiation” before, and it was easy to write a function to calculate 2^7830457 etc. without overflowing 64-bit integers.

Wikipedia has a good article and algorithms for it.