Clojure and me has moved.

Tuesday, June 10, 2008

Google Treasure Hunt, Question #4

This post has moved, go to its new location
A friend of mine asked me how I solved the fourth question of Google Treasure Hunt 2008 using Clojure. I didn't keep the original code around, so below is how I could have done it.

First, define a primes seq.

Second, define a function which returns the sequence of sums of N consecutive primes:
(defn sum-primes [n] (map #(apply + %) (partition n 1 primes)))

Third, define a function which, taking a list of increasing sequences, returns the first common value.
(defn find= [seqs]
(if (apply == (map first seqs))
(ffirst seqs)
(let [[s1 & etc] (sort #(- (first %1) (first %2)) seqs)]
(recur (cons (rest s1) etc)))))

Last, use them! Here is a sample question:
Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 5 consecutive prime numbers,
the sum of 11 consecutive prime numbers,
the sum of 1493 consecutive prime numbers,
and is itself a prime number.

And here is how to compute the answer:
(find= (cons primes (map sum-primes [3, 5, 11, 1493])))
returns 9174901 in twenty seconds or so.

(Right now this code may throw a StackOverflow exception, please use one of those definition of partition.)


David said...

Very impressive. What's your implementation of primes? My Haskell implementation, with all compiler optimizations turned on, took about 16 minutes. (I'm a Haskell novice, but still, 20 seconds on JVM vs. 16 minutes for native code says something).

import Primes
import Data.List hiding (find)

sums n = map (\m -> sum . take n $ drop m primes) [0..]

find ss@((x:_):_) =
if all (== x) (map head ss) then x
else let ss' = map snd $ sort $ zip (map head ss) ss in
find $ tail (head ss') : tail ss'

main = print $ find (primes : map sums [3, 5, 11, 1493])

David said...

Here's a better presentation of my Haskell solution.

Christophe Grand said...

@david: my implementation of primes can be found here:

To be fair, I retimed:
user=> (time (find= (cons primes (map sum-primes [3, 5, 11, 1493]))))
"Elapsed time: 88650.283232 msecs"
user=> (time (find= (cons primes (map sum-primes [3, 5, 11, 1493]))))
"Elapsed time: 5894.601122 msecs"

I guess that I got 20s by having some primes computed from a prior invocation. So nearly 90s with no primes precomputed and 6s when all required primes are already computed.

que said...

Well, here is result of mine ruby implementation:
Found: 9174901. Testing...solved.
Time elapsed: 3.343

David said...

Ok, saw a canonical solution in Haskell by a more proficient author :) -- in defense of my language du jour, the canonical solution terminated in a couple seconds with no compiler optimizations as far as I know. I'm fairly certain that my bottleneck was my sums function, which potentially recalculated the first n primes to create a sum containing the n+1th prime.

Christophe Grand said...

@david: ah, it fits better in the natural order of all things :-)