Project Euler 97: Find the last ten digits of the non-Mersenne prime: 28433 × 2^7830457 + 1

Project Euler 97: Find the last ten digits of the non-Mersenne prime: 28433 × 2^7830457 + 1

Written by on 19 May 2012

Topics: Project Euler

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 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.

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.

1 Comment For This Post I'd Love to Hear Yours!

  1. Lou says:

    ;_;
    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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.