Consecutive Prime Sum (Project Euler - Problem 50)


Problem

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Note

Some libraries used in this code are F# modules I use, but have also published as a Nuget library, such as EulerLib.GetPrimes() and EulerLib.isPrime(). You need to reference the NuGetLibrary to use this code as is.

Solution

 #load "Stat.fs"  
 #load "Print.fs"  
 #load "EulerLib.fs"  
 open Stat  
 open Print  
 open EulerLib  
 open System  
   
 let rec FindLongestPrimeSequenceSum   
     (primeList:list)   
     (nextItem:int)   
     lessThanValue   
     (primeArray:list)   
     bestPrime   
     (correctArray:list) =   
       if List.sum(primeArray) + primeList.[nextItem] >= lessThanValue then  
         (bestPrime, correctArray.Length)  
       else  
         let newArray = List.append primeArray [primeList.[nextItem]]  
         let nextCounter = nextItem + 1  
         let testNum = List.sum newArray  
         if EulerLib.IsPrime(testNum) then  
           FindLongestPrimeSequenceSum   
                   primeList   
                   nextCounter   
                   lessThanValue   
                   newArray   
                   testNum  
                   newArray  
         else  
           FindLongestPrimeSequenceSum   
                   primeList   
                   nextCounter   
                   lessThanValue   
                   newArray   
                   bestPrime   
                   correctArray  
                                     
 let primeStart2 = Seq.toList(EulerLib.GetPrimes(1000000))  
 let primeStart3 = [for i = 1 to primeStart2.Length - 1 do yield primeStart2.[i] ]  
 let primeStart4 = [for i = 1 to primeStart3.Length - 1 do yield primeStart3.[i] ]  
 let primeStart5 = [for i = 1 to primeStart4.Length - 1 do yield primeStart4.[i] ]  
 let primeStart6 = [for i = 1 to primeStart5.Length - 1 do yield primeStart5.[i] ]  
   
 let result2 = FindLongestPrimeSequenceSum primeStart2 0 1000000 [] 0 []  
 let result3 = FindLongestPrimeSequenceSum primeStart3 0 1000000 [] 0 []  
 let result4 = FindLongestPrimeSequenceSum primeStart4 0 1000000 [] 0 []  
 let result5 = FindLongestPrimeSequenceSum primeStart5 0 1000000 [] 0 []  
 let result6 = FindLongestPrimeSequenceSum primeStart6 0 1000000 [] 0 []  
   

Popular posts from this blog

Microsoft Azure Notebooks - Live code - F#, R, and Python

Digit cancelling fractions (Project Euler Problem 33)