Google Treasure Hunt primes question

- Magnus Therning

In the comments to my post on the Google treasure hunt Andre asked me to put up my solution for the fourth problem. The problems were personalised and here is mine:

Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 29 consecutive prime numbers,
the sum of 373 consecutive prime numbers,
the sum of 665 consecutive prime numbers,
and is itself a prime number.

The idea behind my solution is that if I have four lists of the sums, and a list of primes, then the solution to the problem is the smallest member of the intersection of all five lists.

I saved the problem of finding primes to the last and instead concentrated on summing up lists of integers in a convenient way. I ended up with the following solution to that:

sumN :: Int -> [Integer]
sumN n = map fst sumi
    where
        sumi = tail $ iterate (sumn) (0, primes)
        sumn (r, xs) = (sum $ take n xs, tail xs)

The real work happens in the inner functions. sumn picks out as many numbers as I want and sums them up, the reason for taking and returning a tuple is that sumi can use iterate to calculate the sequence of sums. The first item in the result of iterate a is a, so sumi drops the first one. This lets me create the needed lists of sums:

sum3 = sumN 3
sum29 = sumN 29
sum373 = sumN 373
sum665 = sumN 665

After having a quick look at the implementation of Data.List.intersect I realised it probably would be a bit too slow. Instead I wrote one that exploits that all the involved lists are ordered:

intersection a@(x:xs) b@(y:ys)
    | x == y = x : intersection xs ys
    | x < y = intersection (dropWhile (< y) xs) b
    | x > y = intersection a (dropWhile (x >) ys)

After convincing myself that this code did what I wanted (basically through playing in GHCi using an incorrect definition of primes, primes = [1..]) I turned to the problem of finding the primes. Of course someone else had already written the Haskell code to find primes. That code fitted perfectly with mine since it produces an infinate list of Integers. Brilliant! :-)

Finally here’s the main that allows me to compile the code and get the answer quickly (it’s slightly modified for the medium, basically I wrote it all on one, long line):

main :: IO ()
main = let
        i1 = (primes `intersection` sum665)
        i2 = (sum3 `intersection` sum373)
        s =  i1 `intersection` i2 `intersection` sum29
    in
        print $ head s

Compiled, it runs in about 5.5 seconds on my desktop machine.

Tags: google, haskell, treasure hunt

foobar

The following looks nicer to me:

sumN 1 = primes
sumN n = [x+y | (x, y) <- zip (tail $ sumN (n-1)) primes]

Andre

Ah, I see. My problem was the naive implementation of the sieve. The optimized version runs much faster. :-)

My intersection-function is similar, although it finds elements which are in each passed (infinite) list. Here’s my implementation:

intersect :: (Eq a, Ord a) => [[a]] -> [a]
intersect [] = []
intersect xs | or (map null xs) = []
             | and $ map ((== x) . head) xs = x : (intersect $ map tail xs)
             | otherwise = intersect $ map (dropWhile (< max)) xs
   where max = let comp (x:_) (y:_) = compare x y
               in  head $ maximumBy comp xs
         x   = head $ head xs

(Sorry for the formatting.)

Therefore I’ve a more general function for finding the prime which fulfills the required conditions: ~~~ { .haskell } prime :: [Int] -> Integer prime = head . intersect . (primes:) . map (calc primes) ~~~

Whereas calc is semantically equivalent to your sumN-function.

Using your test-data and the optimized sieve my program needs circa 10 seconds for finding the solution. Great work of yours!

Russell O'Connor

This is almost the same as my code, except I wrote sumN as sumN xs = map (sum . take n) (tails primes)

Peter

Thanks for showing us what you did!

I really like foobar’s definition of sumN – much better than the one I came up with – although I’d have used zipWith, like this:

sumN 1 = primes
sumN (n+1) = zipWith (+) primes $ tail $ sumN n

For extra prettiness, notice that primes == sumN 1 and that Andre’s version of intersect can be derived from Magnus’ version of intersect using foldl1:

main = print $ head $ foldl1 intersect [sumN n primes | n &lt;- [1, 3, 29, 373, 665]]

:-)

Peter

Oops. There’s a typo in my previous comment. It should be:

main = print $ head $ foldl1 intersect [sumN n | n &lt;- [1, 3, 29, 373, 665]]

Magnus

@Russel,

That is a beautiful definition of sumN! I wasn’t aware of the existence of the tails function before.

@Peter,

Thanks for pointing that out, it does make it a bit more beautiful and readable.

Samuel

Interesting how we all used pretty much the same solution. :)

I used the following definition of sumN (equivalent to Russel’s function). Should be much faster, since it doesn’t need to iterate through 665 primes for each element.

sumN n = sumN' primes (drop n primes) (sum $ take n primes)
sumN' (x:xs) (y:ys) accum = accum:sumN' xs ys (accum+y-x)

My definition of primes, btw, is the following. Slower than the fastest one on the quoted page, but still pretty fast and elegant.

primes = 2:[x | x &lt;- [3,5..], is_prime x]
is_prime n = all (/= 0) [n `mod` x | x &lt;- takeWhile ((&lt;=n).(^2)) primes]

Nikolay

I’ve used such definition of sums with stream-fusion:

sprimesS :: Int -> Stream Integer
sprimesS n | n == 1 = stream primes
                 | n > 1 = Stream next (L (sum h,primes,t))
    where
        (h,t) = splitAt n primes
        next (L (s,(x:xs),(y:ys))) = Yield s (L (s-x+y,xs,ys))

sprimes = unstream . sprimesS

That should prevent much GC, because all we need is primes list, all other is shifting sums.

Leave a comment