Blog‎ > ‎

Project Euler in Clojure: The First 50 Problems - Problems 22-25

posted Jul 5, 2017, 8:06 AM by Frank Adrian

Problem 22

Problem 22 starts with a text file and... well, I'll let you read it here. We start with two helper functions:
(defn letter-value [c]
  (inc (- (int c) (int \A))))

(defn e22-evaluate [s]
  (reduce + (map letter-value  s)))
The first function gives the numeric value for a letter (A=1, etc.) while the second computes the string value for a name string.

The solution is fairly simple:

(defn euler-22 []
  (let [names (read-string (str "[" (slurp "resources/p022_names.txt") "]"))
        snames (sort names)
        nvals (map e22-evaluate snames)
        cnt (count names)
        x (range 1 (inc cnt))
        zip (map vector x nvals)]
    (reduce (fn [z [x y]] (+ z (* x y))) 0 zip)))
Here, we use slurp to read the file into a string, use str to turn it into an array by bracketing it, and read the string. Next we sort the array and get the evaluation value for all of the names. Next we get a sequence corresponding to 1..(count names) and zip it with the evaluation values. Finally we use reduce to calculate the Problem's answer.

Problem 23

A number n is abundant if the sum of its proper divisors exceeds n. Problem 23 asks us to find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. These numbers, according to the problem are all less than 28124.

Our first function checks to see if a number is abundant:

(defn abundant? [N]
  (> (reduce + (proper-divisors N)) N))
Our solution starts by finding all abundant numbers less than 28124 and collecting all numbers that are sums of pairs of abundant numbers. Next we take all numbers less than 28124 and form a set from them. Finally, we remove all the numbers that were formed from sums of abundant numbers and use reduce to get the solution to the problem:
(defn euler-23 []
  (let [count28123 (range 1 28124)
        abundants (filter abundant? count28123)
        abundant-pairs (combo/cartesian-product abundants abundants)
        sums (into #{} (map (fn [[x y]] (+ x y)) abundant-pairs))
        non-pairs (set/difference (into #{} count28123) sums)]
    (reduce + non-pairs)))

Problem 24

This problem asks what the 1000000'th entry is in the list of lexicographically sorted permutations of the digits from 1..9. The solution is a fairly straightforward transliteration:
(defn euler-24 []
  (let [s "0123456789"
        ps (combo/permutations s)
        nss (map #(apply str %) ps)
        snss (sort nss)]
    (first (drop 999999 snss))))
We first form the permutations of the characters from 1-9. We then convert the permutation sequences into strings. Next we sort the strings. Finally, we get the 1000000'th element.

Problem 25

This problem asks for the index of the first Fibonacci number having 1000 digits:
(defn euler-25 []
  (loop [idx 2
         a (bigint 1)
         b 1]
    ;(println cnt a b res)
    (if (= (count (str b)) 1000)
      idx
      (recur (inc idx) b (+ a b)))))
Our solution simply loops, producing the next Fibonacci number at each iteration until the number of digits is 1000. When this happens, the index is returned.
Comments