Sunday, July 13, 2014

99 Clojure Problems: 41: A List Of Goldbach Compositions

"Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition."


(print-goldbach (range 9 21))
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17

"In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than, say, 50. Try to find out how many such cases there are in the range 2..3000.

Example (minimum value of 50 for the primes)":

(print-goldbach (range 2000) 50)
992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867


A simple problem as we have already implemented all the bits that do most of the work. To create a list of Goldbach compositions we take the input range (note the range semantics in Clojure: the upper limit is exclusive) filter out the even numbers that are greater than 2 (as required by Goldbach's conjecture). We then map the Goldbach function over the range and apply the mimimum filter for the first prime in the results (see the second example above).

We format the result and println it, generating a new line for every Goldbach composition. Have a look at the source once you tried it yourself.

The interesting aspect of this problem is the use of doall, which we have to call at the very end. Why? The intermediate representation of the data is a lazy sequence. By mapping println over that sequence we declare that we want to trigger a side effect (the printing). But the effect does not occur, due to laziness, until we force it with doall.

Read more about this series.

No comments: