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?
My solution (very fast):
asFarAsPossibleCondition :: (a -> Bool) -> [a] -> Maybe [a]
asFarAsPossibleCondition _ [] = Nothing
asFarAsPossibleCondition f xs = if f $ last xs then Just xs else asFarAsPossibleCondition f $ init xs
maxPrimeSum :: Int -> Int
maxPrimeSum n = snd $ maximumBy (comparing fst) series
where
series = map (\x -> (length x, last x)) $ mapMaybe checkSeries [0..10]
checkSeries x = asFarAsPossibleCondition (isPrime) $ takeWhile (<n) $ scanl1 (+) $ drop x primes
asFarAsPossibleCondition
looks for the last element in a list that satisfies a condition then returns that list up to that point (e.g. asFarAsPossibleCondition (<5) [1..10]
-> Just [1,2,3,4]
. (Note that it differs from takeWhile
, since takeWhile
will start at the beginning of the list and stops as soon as it encounters an element that does not satisfy the condition. My function starts at the end of the list and looks for the last element that satisfies the condition, regardless of whether there are elements before that that don't satisfy the condition, e.g. asFarAsPossibleCondition (<5) [1,2,3,4,5,6,7,8,9,10,4] -> Just [1,2,3,4,5,6,7,8,9,10,4]
. This is useful to check a list of consecutive prime sums (e.g. [2, 5, 10, ...]
) and get the longest one that adds to a prime, for instance:
last $ fromJust $ asFarAsPossibleCondition isPrime $ scanl1(+) $ take 20 primes
281
This is the highest consecutive prime sum that results in a prime number that you can get with x<=20
prime numbers starting from 2 (2+3+5+7+11+13+17+19+23+29+31+37+41+43 = 281).
To start from the next prime, you simply drop the first prime, and so forth, e.g.
last $ fromJust $ asFarAsPossibleCondition isPrime $ scanl1(+) $ take 20 $ drop 1 primes
499
This is the highest consecutive prime sum that results in a prime number that you can get with x<=20
prime numbers starting from 3.
The rest is fairly obvious; it checks for each starting prime the greatest prime below 1,000,000, gets the length and the prime it adds up to, then gets the prime with the maximum length.
Any advice is welcome, specifically on:
- the use of Maybe (I'm just learning about this); is it correct? Justified? ...
- how to determine on how many items that I should map the checkSeries function on. ([0..10] was sufficient, but that was simply because I got lucky).
- is there a builtin that does what my
asFarAsPossibleCondition
function does?
scanl
you create sums of consecutive primes starting from 2. The problem text says nowhere that all the sums should start from 2. I think that's your problem. \$\endgroup\$filter isPrime
is very efficient. Since you already have a list of primes, you could check if a number is present or not. \$\endgroup\$