Project Euler in Clojure: The First 25 Problems - Problems 5-9

Post date: Mar 23, 2017 4:37:48 PM

Problems five through nine all have relatively simple solutions in Clojure. My apologies for those wanting more length.

Problem 5

Problem 5 asks for the smallest number cleanly divisible by all numbers 1 through 20. To meet the cleanly divisible criteria, our number must include all of the prime factors of the numbers from 1 through 20. To be the smallest, it must be the product of the minimum number of prime factors that meets the previous criterion.

We'll start by looking through the numbers one-by-one. Our number must be divisible by 2 and then 3. So the number must be divisible by 2*3. The next divisor, 4=2², meaning that to keep the number minimal, we need have only another single factor of 2 in the number or that the number must be divisible by 2*3*2. Five is a new prime divisor and so the number must be divisible by 2*3*2*5. Continuing in this manner, we can see that divisibility by 6 can be satisfied by the existing factors of 2 and 3, seven can be added to the list, and 8 can be accounted for by adding another factor of 2 to the product, meaning that the number must be divisible by 2*3*2*5*7*2. Nine brings in the second factor of 3 and continuing writing factors in this manner up to 20 (whose divisibility is already accounted for by 2 factors of 2 and one of 5 at that point) leaves us with a number that must be divisible by 2*3*2*5*7*2*3*11*13*2*17*19, which having all the factors of numbers less than or equal to 20 is the solution to the problem.

Using Clojure as a desk calculator gives us the answer:

(defn euler-5 "Expand numbers by prime factors and read off non-dupe factors." [] (* 2 3 2 5 7 2 3 11 13 2 17 19))

Problem 6

This problem is another simple calculation problem - find the difference between the square of the sum of the numbers from 1 to 100 and the sum of the squares of these same numbers. Using reduce to calculate the sums leads to another fairly self-explanatory function:

(defn euler-6 [] (let [to100 (range 1 101)] (- (* (reduce + to100) (reduce + to100)) (reduce + (map #(* % %) to100)))))

Problem 7

What is the 10001'st prime number? To determine this, we use a helper function, nth-prime:

(defn nth-prime [n] (nth (gen-primes) (dec n)))

Note the (dec n) - Clojure's counting is zero-based, the problem counts from 1. This allows us to write our solution for Problem 7:

(defn euler-7 [] (nth-prime 10001))

Problem 8

Problem 8 gives us a very big number and asks us for the largest product of thirteen consecutive digits in this number. If we can find all thirteen-character substrings of this number, then we need only map a function over this collection that finds the product of the digits and then take the maximum of these mapped products. Lets start by finding the thirteen-character substrings. This is easily accomplished using Clojure's partition function:

(def ce8 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450) (defn get-partitions [] (partition 13 1 (str ce8)))

This function returns a lazy sequence of lazy sequences of characters:

((\7 \3 \1 \6 \7 \1 \7 \6 \5 \3 \1 \3 \3) (\3 \1 \6 \7 \1 \7 \6 \5 \3 \1 \3 \3 \0) (\1 \6 \7 \1 \7 \6 \5 \3 \1 \3 \3 \0 \6) ...)

Each sub-sequence contains the thirteen characters of the substring it corresponds to. To convert these to their products, we must convert the character sequences to integer sequences and multiply. To do the first, we construct an auxiliary function char->int:

(defn char->int [c] (- (int c) (int \0)))

Once this function is available, we can solve the problem as follows:

(defn euler-8 [] (->> (get-partitions) (map #(apply * (map char->int %))) (apply max)))

In this solution, we take the partitions, use the map function to get the products, and take the max. The internal function in the map form takes the sequence, converts its characters to integers, and multiplies them together.

Problem 9

There is a single Pythagorean triple (i.e., [a, b, c] such that a²+b²=c²) where a+b+c=1000. Our problem asks for a*b*c for this number. Assuming we can find all triples summing to 1000 and have a function that tests whether or not a triple is Pythagorean, we can write our solution as:

(defn euler-9 [] (->> (triples-summing 1000) (filter pythagorean-triple?) (map #(apply * %)) (first)))

The test for being a Pythagorean triple is simple:

(defn pythagorean-triple? [[a b c]] (= (* c c) (+ (* a a) (* b b))))

The code for producing a set of all positive integer pairs summing to N is:

(defn doubles-summing [N] (let [rangeN (range 1 (inc N))] (take (dec N) (map (fn [x] [x (- N x)]) rangeN))))

Here, we take the numbers i from 1 to N, and use the map function to pair them with N-i. We only use the first N-1 of these because we do not want to consider the number pair [N, 0]. We will use these doubles to find triples summing to N:

(defn triples-summing [N] (apply concat (let [rangeN (range 1 (inc N))] (map (fn [k] (let [doubles (doubles-summing (- N k))] (map (fn [[a b]] [a b k]) doubles))) (take (dec N) rangeN)))))

In this function, the first map is applied to the numbers k from 1 to N, where for each it maps the doubles [a, b] summing to N-k and packages them into a triple [a, b, k] summing to N. The sequences of triples produced by this map are then concatenated to form the final list of all triples. Again, note the (take (dec N) ...) clause. This is again because we do not want to consider solutions of the form [a, b, 0], where a+b = N.