Only three problems this update, since we’re coming to the end of the arithmetic section of the problems. The Goldbach Conjecture is fun to say, and fairly easy to solve. Unfortunately, I think I misunderstood the “secondary” problem of P41. I returned all even numbers that can be expressed as the sum of two primes that are over 50. The solution in the scala version of the problems seems to find the first possible pair of primes that equal a prime, and then find which “initial” pair of primes is over 50.
(defn prime? [n prime-cache]
(= 0 (count (filter zero? (map (fn [e] (mod n e)) prime-cache)))))
(defn primes-upto [n]
(loop [possible 3
primes '()]
(cond
(< n 2) primes
(= n 2) '(2)
(>= possible n) (reverse primes)
(prime? possible primes) (recur (+ 2 possible) (conj primes possible))
:else (recur (+ 2 possible) primes))))
; P39 (*) A list of prime numbers.
(comment "Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.")
(defn prime-list [start end]
(drop-while (fn [e] (< e start)) (primes-upto end)))
; P40 (**) Goldbach's conjecture.
(comment "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 (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.")
(defn goldbach [n]
(let [primes (primes-upto n)]
(loop [[head & tail] primes]
(let [match (first (filter #(= % (- n head)) primes))]
(cond
(nil? head) nil
(nil? match) (recur tail)
:else (list head match)
)))))
(defn limited-goldbach [n limit]
(let [primes (primes-upto n)]
(loop [[head & tail] primes]
(let [match (first (filter #(= % (- n head)) primes))]
(cond
(nil? head) nil
(> head (/ n 2)) nil
(nil? match) (recur tail)
(< head limit) (recur tail)
:else (list head match)
)))))
(comment "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.")
(defn print-goldbach-list-limited [a end limit]
(loop [start a]
(cond
(> start end) nil
(< start limit) (recur (inc start))
(zero? (rem start 2)) (do
(let [gbp (limited-goldbach start limit)]
(if (nil? gbp) nil
(let [[a b] gbp] (println start "=" a "+" b ))))
(recur (inc start)))
:else (recur (inc start)))))
; P41 (**) A list of Goldbach compositions.
(comment "Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.")
(defn print-goldbach-list [a end]
(print-goldbach-list-limited a end 0))
So yeah, some extra work… oh well! I learned about the “do” function today, which allows me to do something in addition to “recur”.