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

Example

(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

Discussion

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.

99 Clojure Problems – 40: Goldbach's Conjecture

Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers. Write a predicate to find the two prime numbers that sum up to a given even integer.

Test/Example

(deftest p40-goldbach
  (is (= [5 23] (goldbach 28))))

(def even-nats-greater-two (gen/such-that #(< 2 %) (gen/fmap #(* 2 %) gen/nat)))


(defspec goldbach-conjecture
  100
  (prop/for-all [i even-nats-greater-two]
                (let [res (goldbach i)]
                  (and
                   (= 2 (count res))
                   (every? prime? res)
                   (= i (reduce + res))))))

Discussion

A naive approach just looks at all prime numbers below the input value. We are then only interested in those primes that if subtracted from that input leave us with another prime number. Both numbers obtained by that method form the result. We already got a list of prime numbers, Clojure's take-while and filter do the rest. I expressed the fact that Goldbach's conjecture is only defined for even natural numbers greater than two with a precondition.

If you have been following this series you might have noticed that the example I give in the blog posts is almost always a unit test. I think this a quite succinct way to illustrate the intended behaviour of a function. But this time you will have noticed that there is something else.

I have added a dependency to clojure.test.check. Test.check is a QuickCheck inspired property-based testing library for Clojure. You can learn more about QuickCheck by having a look at the original paper.

Looking at the code above you will notice that a generative test consists of two parts. First a property (within the defspec). In this case I specified that for all even natural numbers greater than two the Goldbach function should return two prime numbers whose sum is equal to the input value. This property is an almost literal translation of Goldbach's conjecture.

Secondly you need to specify how to generate all possible input values that the test runner should use. Again: Instead of doing this explicitly for every single input value, as you would have to in a traditional exemplary unit test, you just define a generator. I used the built-in generator for natural numbers called nat. But in order to create only valid input values for the Goldbach function the generated values need to be greater than two and even. You can achieve this by using combinators on the original generator. A fmap * 2 shifts the domain of the generator into the even values. I then used the such-that combinator to filter out everything below two.

While writing these generative tests seems like more work at first sight you get back a more thorough verification of your program in return.

Property-based testing recognises the impossibility of coming up with test inputs that expose all edge cases. Instead it encourages you to define properties of your function that you expect to hold. The flip side of the coin is that property based tests won't contribute as much to the design of your APIs and your system as the traditional TDD approach did. But it is a very valuable attempt at automated verification.

Read more about this series.

99 Clojure Problems: 39 – A List Of Prime Numbers

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

Example:

(deftest p39-primes-range
  (is (= '(7 11 13 17 19 23 29 31) (primes-range 7 31))))

Solution:

This is a quick one. As we have already defined a lazy seq of prime numbers to solve P35 we can reuse that. To produce the desired range drop from that sequence until we reach the lower bound and then take until we reach the upper bound. Have a look at the solution if this was too terse.

Read more about this series.