Project Euler — Problem 97 Solution

Problem

The first known prime found to exceed one mil­lion dig­its was dis­cov­ered in 1999, and is a Mersenne prime of the form 26972593-1; it con­tains exact­ly 2,098,960 dig­its. Sub­se­quent­ly oth­er Mersenne primes, of the form 2p-1, have been found which con­tain more dig­its.

How­ev­er, in 2004 there was found a mas­sive non-Mersenne prime which con­tains 2,357,207 dig­its: 28433x27830457+1.

Find the last ten dig­its of this prime num­ber.

Solution

// define a func­tion which returns the last n dig­its of a num­ber
let get­Last­Dig­it­sOf n num­ber =
let num­ber­Str = number.ToString()
let dig­its =
if numberStr.Length > n then numberStr.Substring(numberStr.Length — n, n)
else numberStr.Substring(0, numberStr.Length)
int64(digits)

// define a func­tion which iter­a­tive­ly pow­ers up the base (b) but all the time
// only keep­ing track of the last n dig­its of the result
let F b pow n =
let muta­ble track­er = 1L
for i = 1 to pow do track­er - get­Last­Dig­it­sOf n (track­er * b) track­er let answer = get­Last­Dig­it­sOf 10 (28433L * (F 2L 7830457 10) + 1L) [/code] Ini­tial­ly I tried the brute force approach to this prob­lem and need­less to say it brought me no luck what­so­ev­er.. so try­ing a slight­ly clever approach I decid­ed to only keep track of the last 10 dig­its as I iter­a­tive­ly pow­er up 2 from 1 all the way to 7830457. The result­ing 10 dig­its num­ber is then mul­ti­plied by 28433 and added by 1 before the same func­tion is applied to fetch the last 10 dig­its.