Google Treasure Hunt, Question #4

unsorted — cgrand, 10 June 2008 @ 10 h 12 min

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.)

5 Comments »

  1. 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])

    Comment by David — 10 June 2008 @ 22 h 35 min
  2. @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.

    Comment by Christophe Grand — 11 June 2008 @ 7 h 41 min
  3. Well, here is result of mine ruby implementation:
    Solving…
    Found: 9174901. Testing…solved.
    Time elapsed: 3.343
    :)

    Comment by que — 11 June 2008 @ 14 h 15 min
  4. 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.

    Comment by David — 17 June 2008 @ 8 h 13 min
  5. @david: ah, it fits better in the natural order of all things :-)

    Comment by Christophe Grand — 17 June 2008 @ 8 h 38 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2014 Clojure and me | powered by WordPress with Barecity