Google Treasure Hunt, Question #4
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.)
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: my implementation of primes can be found here: http://clj-me.blogspot.com/2008/06/primes.html
To be fair, I retimed:
user=> (time (find= (cons primes (map sum-primes [3, 5, 11, 1493]))))
“Elapsed time: 88650.283232 msecs”
9174901
user=> (time (find= (cons primes (map sum-primes [3, 5, 11, 1493]))))
“Elapsed time: 5894.601122 msecs”
9174901
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.
Well, here is result of mine ruby implementation:
Solving…
Found: 9174901. Testing…solved.
Time elapsed: 3.343
:)
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.
@david: ah, it fits better in the natural order of all things :-)