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

### Primes

unsorted — cgrand, 7 June 2008 @ 10 h 43 min

Last night on #clojure Lau_of_DK asked for a way to define the sequence of prime numbers.

Having helped Lou Franco in his effort to parallelize primes computation and solved the fourth question of Google Treasure Hunt using Clojure, I thought I knew pretty well how to produce primes in Clojure but I stumbled accross some Haskell code that was far smarter. Here it is, now ported to Clojure:

```(def primes (lazy-cons 2 ((fn this[n]
(let [potential-divisors (take-while #(<= (* % %) n) primes)]
(if (some #(zero? (rem n %)) potential-divisors)
(recur (inc n))
(lazy-cons n (this (inc n)))))) 3)))
```

It’s interesting to note that the seq is seeded with 1 and 2 because Clojure’s lazy seqs have a off by one evaluation (when one asks for the nth value, the nth+1 is computed — to know if the end of the seq is reached). No, no, no! I was plain wrong: if I need to seed with [1 2] 2 it’s because of the take-while whose predicate must return at least one false.

Update: In comments, Cale Gibbard points out that my definition of prime numbers is loose: 1 isn’t a prime. I fixed the code.