Project Euler – Problem 97 Solution


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.


// define a function which returns the last n digits of a number
let getLastDigitsOf n number =
let numberStr = number.ToString()
let digits =
if numberStr.Length > n then numberStr.Substring(numberStr.Length – n, n)
else numberStr.Substring(0, numberStr.Length)

// define a function which iteratively powers up the base (b) but all the time
// only keeping track of the last n digits of the result
let F b pow n =
let mutable tracker = 1L
for i = 1 to pow do tracker <- getLastDigitsOf n (tracker * b) tracker let answer = getLastDigitsOf 10 (28433L * (F 2L 7830457 10) + 1L) [/code] Initially I tried the brute force approach to this problem and needless to say it brought me no luck whatsoever.. so trying a slightly clever approach I decided to only keep track of the last 10 digits as I iteratively power up 2 from 1 all the way to 7830457. The resulting 10 digits number is then multiplied by 28433 and added by 1 before the same function is applied to fetch the last 10 digits.

Yan Cui

I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.

You can contact me via Email, Twitter and LinkedIn.

Hire me.