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