Yan Cui

I help clients go faster for less using serverless technologies.

#### Problem

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.

#### Solution

// 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)

int64(digits)

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

**Whenever you’re ready, here are 4 ways I can help you:**

**Production-Ready Serverless**: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for**quickly levelling up your serverless skills**.- Do you want to know
**how to test serverless architectures**with a fast dev & test loop? Check out my latest course,**Testing Serverless Architectures**and learn the smart way to test serverless. - I help clients
**launch product ideas**,**improve their development processes**and**upskill their teams**. If you’d like to work together, then let’s**get in touch**. **Join my community on Discord**, ask questions, and join the discussion on all things AWS and Serverless.