Clojure solutions to the first 33 Project Euler problems.

Unit tests are provided to compare the result of each problem's solution function to the official Project Euler answer for that problem. A simple way to run the tests is by using lein from the command line:

(/home/drc/code/euler)$ lein test



dev dependencies


(this space intentionally left almost blank)

Before launching into the problems, let's take a quick tour of some useful syntax.

(ns org.drcabana.euler.prequel)

Defining a function is the natural unit of work in functional programming. Clojure offers multiple ways to define functions, so let's look at some examples. This treatment is not exhaustive, it just covers some common cases.

The classic function of one argument.

(defn square
  (* x x))
=>(square 4)

A two argument function.

(defn sum-of-cubes
  [x y]
  (+ (* x x x) (* y y y) ))
=>(sum-of-cubes 2 3)

A single required argument, with a variable number of optional arguments. The more-args argument is treated as a sequence. The name does not matter; it is the & that signals that the next symbol will be the bound to the sequence of subsequent arguments.

(defn sum-of-squares
  [x & more-args]
  (+ (square x)
     (apply + (map square more-args))))
=>(sum-of-squares 2)
   =>(sum-of-squares 2 3 4)

There are a couple of ways two define anonymous functions. The first is to use fn. Here's an anonymous version of square, applied to the number 5. You can think of fn as Clojure's way of spelling lambda.

=>( (fn [x] (* x x)) 5)

An even terser way to define square is to use the #() form. Here % denotes the single argument to the function .

=>( #(* % %) 5)

The #() form allows for multiple arguments by numbering them. Here we define a function which divides its first arg by its second, and apply it.

=>( #(/ %1 %2) 20 5)

You can create functions of multiple arity, defined on a case per case basis.

(defn foo
  ([] "one meeellion")
  ([x] (* 2 x))
  ([x y] (+ x y))
  ([x y z] (max x y z)))
   "one meeellion"
   =>(foo 3)
   =>(foo 2 3)
   =>(foo 2 3 4)

Various Clojure data structures can be used both as data structures and as functions. For instance, sets can be used as functions. Let's define a set.

(def digits #{0 1 2 3 4 5 6 7 8 9})

A slick way way to use a set is to test for membership in the set itself. The way it works is that (digits x) returns x when x is an element of digits, and returns nil otherwise.

=>(digits 3)
   3    ;; 3 is truthy.
   =>(digits 22)
   nil  ;; nil is falsey.

This becomes problematic if nil is an element of the set in question. When that is not an issue, this way of testing membership can be quite handy. See the solution to problem 24 for an example.

For more (somewhat densely packed) information, check out the official documentation for Clojure's special forms and for the Clojure reader.

Clojure is fortunate to have several very good books. To my taste, the best introductory book is Programming Clojure. The Joy of Clojure is a must read, but perhaps not the best place to start for readers who don't already have some lisp in their veins.


Problem 1 is to sum the positive integers less than 1000 which are divisible by either 3 or 5. The original problem statement is available here.

(ns org.drcabana.euler.prob01)

The qualifies? function returns true if and only if x is divisible by 3 or by 5.

(defn qualifies?
  {:pre (integer? x)}
  (or (zero? (rem x 5))
      (zero? (rem x 3))))

The solution illustrates recurring patterns worth watching for in subsequent problems.

  • We begin by generating a sequence of data.
  • We then use filter and a predicate to extract a desired subsequence.
  • We wrap up by using reduce and a selected function to compute a value from the subsequence.
(defn solution []
  (reduce + (filter qualifies? (range 1000))))


Predicates are functions that return true or false. By convention, the names of predicates end with a question mark.

Notice that Clojure has some design-by-contract fu. We used a precondition in the definition of the qualifies function. For the official docs on pre-conditions, grep for "pre-expr" here. Post-conditions are also available. If you would like a stronger dose of Clojure dbc goodness, check out Trammel.

Docs: filter integer? range reduce rem zero?


Problem 2 is to sum the even Fibonacci numbers not exceeding four million. The original problem statement is available here.

(ns org.drcabana.euler.prob02)

fibonacci is an arity-0 function which returns the sequence of Fibonacci numbers. The +' operator performs addition with bigints, avoiding overflows for large values of a and b.

(defn fibonacci
  (letfn [(fib [[a b]] [b (+' a b)])]
    (->> [0 1]
         (iterate fib)
         (map first))))

The pattern is pretty much the same as in the previous problem. We generate a sequence, filter it with a predicate, and reduce the result to a single number.

(defn solution
  (->> (fibonacci)                  ;; generate an infinite lazy sequence
       (take-while #(< % 4000001))  ;; realize the subseq of interest
       (filter even?)               ;; filter out evens, then reduce
       (reduce +)))


The overall pattern of the solution is the same as in problem 1, but the code looks a bit different, due to the use of the ->> macro. I like ->> because it allows code to be read from top to bottom. By way of comparision, I could have written the code this way.

(defn solution-alternative []
  (reduce + (filter even? (take-while #(< % 4000001) (fibonacci)))))

Docs: ->> first iterate letfn map take-while


Problem 3 is to find the largest prime divisor of 600851475143. The original problem statement is available here.

(ns org.drcabana.euler.prob03
  (:use [clojure.math.numeric-tower :only (sqrt)]))

Return the least divisor of n in the closed interval [k ... n].

(defn least-divisor
  [k n]
  {:pre [(integer? k) (integer? n) (<= 2 k n)]}
  (let [limit (inc (int (sqrt n)))
        candidates (drop-while #(pos? (rem n %)) (range k limit)) ]
    (if (seq candidates) (first candidates) n)))

Return the prime factorization of n, as a vector of primes. By construction the factors will be in non-decreasing order. For example,

;=> (prime-factors 72)
[2 2 2 3 3]
(defn prime-factors
  {:pre [(integer? n) (< 0 n)]}
  (loop [n n factors [] k 2]
    (if (= 1 n)
      (let [d (least-divisor k n)]
        (recur (quot n d) (conj factors d) d)))))
(defn solution []
  (reduce max (prime-factors 600851475143)))

Docs: conj drop-while loop max quot recur seq


Problem 4 is to find the largest palindrome made from the product of two 3-digit numbers. The original problem statement is available here.

(ns org.drcabana.euler.prob04)

Is word a palindrome?

(defn palindrome?
  (let [chars (seq (str word))]
    (= chars (reverse chars))))

There are only 900 3-digit numbers, so brute force suffices. It suffices to consider only the cases where a <= b because multiplication is commutative.

(defn solution []
  (let [products
       (for [a (range 100 1000)
             b (range 100 1000) :when (<= a b)]
         (* a b))]
   (reduce max (filter palindrome? products))))

Notice that once again we constructed a sequence, filtered it, then reduced it.

Docs: for let str


Problem 5 is to find the least common multiple of the integers {1,2,...,20}. The original problem statement is available here.

The LCM function is well known to be associative:

LCM(LCM(a,b),c) = LCM(a, LCM(b,c)).

That means the Clojure solution to our problem is immediate: (reduce LCM (range 1 21)). We just need to construct an LCM function. A simple way is to use the greatest common divisor function, GCD. It can be proven that

LCM(a b) * GCD(a b) = a * b

so we can use GCD to implement LCM. Naturally, we use Euclid's algorithm to implement GCD.

(ns org.drcabana.euler.prob05)

gcd computes the greatest common divisor of positive integers a and b. It would be faster to replace the repeated subtractions with division, but this code is prettier because it is more symmetric. In recreational programming one is free to prefer beauty over speed.

(defn gcd
  [a b]
  {:pre [(integer? a) (integer? b) (pos? a) (pos? b)]}
   (= a b) a
   (> a b) (recur (- a b) b)
   :else   (recur (- b a) a)))

lcm computes the least common multiple of a and b.

(defn lcm
  [a b]
  (/ (* a b) (gcd a b)))
(defn solution []
  (reduce lcm (range 1 21)))

Each of the first five solutions in this problem set has used reduce. I did not set out to do that, and only noticed it after the fact. The reduce function will be used many times in the remaining problems.

Docs: cond


Problem 6 is to find the difference between the square of the sum of 1 ... 100 and the sum of the squares of 1 ... 100. The original problem statement is available here.

(ns org.drcabana.euler.prob06)
(defn solution []
  (let [square #(* % %)
        values (range 1 101)
        square-of-sum  (square (reduce + values))
        sum-of-squares (reduce + (map square values))]
    (- square-of-sum sum-of-squares)))

Problem 7 is to find the 10001-th prime number. The orginal problem statement is available here.

(ns org.drcabana.euler.prob07
  (:use [org.drcabana.euler.prob03 :only (least-divisor)]))

We already have a useful bit of number theoretic code from problem 3. We reuse it via the :use statement in the namespace declaration.

Return the least positive integer greater than 1 which divides n.

(defn least-nontrivial-divisor
  {:pre [(integer? n) (<= 2 n)]}
  (least-divisor 2 n))

Primes are easily defined in terms of the least-nontrivial-divisor function: an integer n>1 is prime if and only if its least non-trivial divisor is n.

(defn prime?
  {:pre [integer? n]}
  (if (< n 2)
    (== n (least-nontrivial-divisor n))))

Return the sequence of primes. We test only odd numbers for primality.

(defn primes
  (let [odd-numbers (iterate #(+ 2 %) 3)]
    (cons 2 (filter prime? odd-numbers))))

Clojure uses 0-based indexing, but the problem statement uses 1-based indexing, so we have to decrement the index.

(defn solution []
  (nth (primes) 10000))

Docs: cons iterate nth


In problem 8 we are given a string of numeric digits, and asked to find the maximal product of five consecutive digits. The original problem statement is available here.

(ns org.drcabana.euler.prob08)

We will need a way to convert a numeric character into an integer. Notice the idiom used in the precondition: membership in a set is tested by using the set as a function.

(defn char-to-int [char]
  {:pre [(#{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9} char)]}
  (Integer/parseInt (str char)))
(defn solution []
  (let [product (partial reduce *)
        digits "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"]
    (->> (map char-to-int digits)
         (partition 5 1)
         (map product)
         (reduce max))))

Picasso is alleged to have remarked that "good artists borrow, great artists steal". The extremely useful partition function was stolen from Mathematica. Well done.

I quietly used Java, in the call to Integer/parseInt. Java interop in Clojure can be so seamless you may not notice it.

Docs: partial partition


Problem 9 is to find the Pythagorean triple that sums to 1000, and form the product of its members. That is, return the product of postive integers a,b,c such that

a + b + c = 1000

a2 + b2 = c2.

The original problem statement is available here.

(ns org.drcabana.euler.prob09)
(defn pythagorean?
  [a b c]
  (= (* c c) (+ (* a a)
                (* b b))))

We choose c = 1000 - a - b, thus meeting the sum constraint. The :when condition ensures that the Pythagorean constraint is met.

(defn solution []
  (let [triples
        (for [a (range 1 1000)
              b (range a 1000)
              c [(- 1000 a b)]
              :when (pythagorean? a b c)]
          [a b c])]
    (reduce * (first triples))))

Docs: for


Problem 10 is to find the sum of all the primes less than two million. The original problem statement is available here.

(ns org.drcabana.euler.prob10
  (:use [org.drcabana.euler.prob07 :only (primes)]))

The machinery for generating primes is in place from problem 7. The only thing new here is the final reduction step.

(defn solution []
  (reduce + (take-while #(< % 2000000) (primes))))

Problem 11 is to find the maximal product of four consecutive numbers in a 20x20 square grid of numbers. Consecutive here means contiguous in a row, column, or diagonal. The original description is available here.

(ns org.drcabana.euler.prob11
  (:use [clojure.math.numeric-tower :only (sqrt)]))

Here are the numbers, or rather a string we'll later convert to a sequence of numbers.

(def digits
  "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
   49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
   81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
   52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
   22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
   24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
   32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
   67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
   24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
   21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
   78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
   16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
   86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
   19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
   04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
   88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
   04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
   20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
   20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
   01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48")

We want to work with a two-dimensional grid, so we define a constructor that turns a sequence (of suitable length) into square matrix. The matrix will be represented as an anonymous function of variable arity.

The matrix function returns a lookup function. Given two integer indices, the latter performs the expected lookup. Conveniently, the lookup function will return 1 if either index is out of bounds. Given no args, the lookup function will return the row length of the matrix.

(defn matrix
  (let [row-length (int (sqrt (count xs)))]
    (assert (= (count xs) (* row-length row-length)))
    (letfn [(valid? [j k] (and (integer? j)
                               (integer? k)
                               (< -1 j row-length)
                               (< -1 k row-length)))
            (idx [j k]    (+ j (* row-length k)))]
        ([] row-length)
        ([[j k]] (if (valid? j k) (nth xs (idx j k)) 1))))))

Compute the sequence of the indices of elements contiguous to origin in the given direction. The origin and direction should each be pairs [j k] of integers.

(defn contiguous
  [origin direction]
  (iterate #(map + direction %) origin))

Determine the largest contiguous length-four product in matrix M.

(defn score
     (reduce max (for [j (range (M))
                       k (range (M))]
                   (score M [j k]))))
  ([M [j k]]
     (let [directions [ [0 1] [0 -1] [1 0] [-1 0] [1 1] [1 -1] [-1 1] [-1 -1] ]]
       (reduce max (map #(score M [j k] %) directions))))
  ([M [j k] dir]
     (let [segment (take 4 (contiguous [j k] dir))]
       (reduce * (map M segment)))))
(defn solution []
  (let [numbers (->> digits
                     (re-seq #"\d+")
                     (map #(Integer. %)))]
    (score (matrix numbers))))

This was largely an exercise in using closures. I have the nagging feeling I could have done something simpler. But closure-object duality is cool.

Docs: assert letfn re-seq


Problem 12 is to find the first triangle number to have over five hundred divisors. Divisors are assumed to be positive. The original problem statement is available here.

We break this problem into two parts: how to compute triangle numbers, and how to count the divisors of integer.

(ns org.drcabana.euler.prob12
  (:use [org.drcabana.euler.prob03 :only (prime-factors)]))

The nth triangle number is the (inclusive) sum of the integers from 1 to n. The formula is well known, but worth explaining. Write the sum twice, but the second time write it in reverse order.

1 +  2 +  ...   + n
n + (n-1) + ... + 1

Summing the n columns, each totals n+1. So twice the sum of 1...n is equal to n(n+1).

(defn tri
  (/ (* n (inc n)) 2))

How many divisors does n have? Any divisor of n is the product of one or more prime factors of n. How many distinct such products are possible?

The simplest way to think about it is to from a product p1k1 p2k2 ... pmkm where the p's are distinct prime factors of n, and the exponents vary from 0 to the multiplicity of the corresponding prime factor. For example, the prime factors of 12 are [2 2 3] so we can form products 2j * 3k where j varies from 0 to 2, and k varies from 0 to 1, hence 12 has 6=3*2 divisors, [1 2 3 4 6 12].

(defn count-divisors [n]
  (->> (prime-factors n)
       (partition-by identity)
       (map count)
       (map inc)
       (reduce *)))

The pieces are in place, the only thing left is to put them together.

(defn solution []
  (->> (iterate inc 1)
       (map tri)
       (drop-while #(< (count-divisors %) 500))

We determined the number of divisors of n without actually computing the divisors. Another approach would have been to compute the divisors and count them. In problem 21 we will write a function to compute the divisors of n.

Docs: drop-while identity iterate partition-by


Problem 13 is to find the first ten digits of the sum of 100 50-digit numbers. Here are the 50-digit numbers, or rather, a string containing them, one per line. The original problem statement is available here

(ns org.drcabana.euler.prob13)
(def num-str
(defn solution []
  (->> (re-seq  #"\d+" num-str) ;; split the string
       (map #(bigint %))        ;; convert substrings to integers
       (reduce +)               ;; sum the integers
       (str)                    ;; convert the sum to a string
       (take 10)                ;; take the first ten digits
       (apply str)              ;; concat the digits into a string
                                ;; turn final string back into integer

Docs: apply bigint re-seq


Problem 14 is to find the positive integer less than one million with the largest Collatz length. The original problem statement is available here.

(ns org.drcabana.euler.prob14)

First let's define the Collatz function:

(defn collatz [n]
  {:pre [(pos? n) (integer? n)]}
  (if (even? n)
    (/ n 2)
    (+ (* 3 n) 1)))

For any positive integer n, we can form the corresponding Collatz sequence.

(defn C [n]
  (iterate collatz n))

It is conjectured that for any positive N, C(N) is eventually 1. According to the Wikipedia, the conjecture has been tested out to N = 20 * 2^58.

Define the Collatz-length of N to be the number of terms in C(N) before the first 1. The use of memoize speeds things up considerably, but this is the most time intensive of the problems in this set.

(def collatz-length
  (memoize (fn [n] (count (take-while #(< 1 %) (C n))))))

The question is what value of N less than one million has the largest collatz-length.

(defn solution []
  (->> (range 1 1000000)
       (map #(vector % (collatz-length %)))
       (sort-by second)
       (last)    ;; grab last pair, then 1st element of that pair

Docs: iterate memoize sort-by


In problem 15 we consider a 20 by 20 rectangular grid. Starting at the top left corner, on any move we can move down or right. The question is how many distinct paths to the bottom right there are. The original problem statement is available here.

There's not much to this one. To get to the bottom right we must make 40 moves: 20 downwards, and 20 to the right. Imagine we have 40 slots numbered 1 to 40. Once you have assigned the 20 downward moves to their slots, there is no choice about where to put the rightward moves. So the question is how many ways can you choose 20 slots from 40.

The answer is well known: the number of ways to choose K elements from N is C(N, K) = N!/(K! * (N-K)!)

In particular C(40,20) = 40!/(20! * 20!). A bit of cancellation simplifies the expression. In Clojure versions 1.3 and above, multiplication can overflow, though not silently. We avoid the overflow by using the *' operator.

(ns org.drcabana.euler.prob15)
(defn solution []
  (/ (reduce *' (range 21 41))
     (reduce *' (range 1 21))))

Problem 16 is to sum the decimal digits of 21000. The original problem statement is available here.

(ns org.drcabana.euler.prob16
  (:use [clojure.math.numeric-tower :only (expt)]))

Compute the sequence of digits in the base 10 representation of n.

(defn digits
  {:pre [(integer? n)]}
  (letfn [(char-to-int [c] (Integer. (str c))) ]
    (map char-to-int (str n))))
(defn solution []
  (reduce + (digits (expt 2 1000))))

Docs: Integer


Problem 17 is as follows. If the numbers 1 to 5 are written out in words (one, two, three, four, five) then there are 3 + 3 + 5 + 4 + 4 = 19 letters used. If all the numbers from 1 to 1000 were written out in words, how many letters would be used?

Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The original problem statement is available here.

(ns org.drcabana.euler.prob17)

Without much ado, here's a solution.

(def word-for
  {1 "one"
   2 "two"
   3 "three"
   4 "four"
   5 "five"
   6 "six"
   7 "seven"
   8 "eight"
   9 "nine"
   10 "ten"
   11 "eleven"
   12 "twelve"
   13 "thirteen"
   14 "fourteen"
   15 "fifteen"
   16 "sixteen"
   17 "seventeen"
   18 "eighteen"
   19 "nineteen"
   20 "twenty"
   30 "thirty"
   40 "forty"
   50 "fifty"
   60 "sixty"
   70 "seventy"
   80 "eighty"
   90 "ninety" })

The functions name-of and three-digit-name mutually call one another, so we get around the forward reference by declaring one of them.

(declare name-of)
(defn two-digit-name [n]
  (let [low  (rem n 10)
        high (- n low) ]
    (str (word-for high) (word-for low))))
(defn three-digit-name [n]
  (let [high (quot n 100)
        low  (rem  n 100)]
    (if (zero? low)
      (str (word-for high) "hundred" )
      (str (word-for high) "hundredand" (name-of low)))))
(defn name-of [n]
   (< n 20)   (word-for n)
   (< n 100)  (two-digit-name n)
   (< n 1000) (three-digit-name n)
   (= n 1000) "onethousand"))
(defn solution []
  (->> (range 1 1001)
       (map name-of)
       (map #(.length %))
       (reduce + )))

Docs: declare


Problem 18: Start at the top of the triangle, move to an adjacent number on the row below, continuing this way to construct a path to the bottom. Consider the sum of the integers along the path. What is the maximal sum that can be constructed? The original problem statement is available here.

(ns org.drcabana.euler.prob18
  (use [clojure.string :only (split-lines)]))
(def data-string
   95  64
   17  47  82
   18  35  87  10
   20  04  82  47  65
   19  01  23  75  03  34
   88  02  77  73  07  63  67
   99  65  04  28  06  16  70  92
   41  41  26  56  83  40  80  70  33
   41  48  72  33  47  32  37  16  94  29
   53  71  44  65  25  43  91  52  97  51  14
   70  11  33  28  77  73  17  78  39  68  17  57
   91  71  52  38  17  14  91  43  58  50  27  29  48
   63  66  04  68  89  53  67  30  73  16  69  87  40  31
   04  62  98  27  23  09  70  98  73  93  38  53  60  04  23")

Our data is given to us as a string, so we'll transform the string into something we can work with. First we'll turn it into a sequence of integers, then we'll turn that sequence into a data structure suited to our algorithmic needs.

Construct a sequence of integers from a string of whitespace delimited blocks of digits.

 => (split-into-nums "1 23 456")
 (1 23 456).
(defn split-into-nums
  (->> string
       (re-seq #"\d+")
       (map #(Integer. %))))

The data structure we want looks like this: ((75) (95 64) (17 47 82) (18 35 87 10) (20 4 82 47 65) ... )

(def triangle
  (map split-into-nums (split-lines data-string)))

The idea here is simple. Imagine the triangle has only three elements, say (a (b c)). Then the maximal path sum is (+ a (max b c)). The trick is to start with the two bottom rows, and work up.

(defn maximize [row]
  (letfn [(pair-max [[a b]] (max a b))]
    (map pair-max (partition 2 1 row))))
(defn merge-rows [row1 row2]
  (map + (maximize row1) row2))
(defn solution []
  (first (reduce merge-rows (reverse triangle))))

Notice that computing the maximal sum across all paths did not require determining the path along which the sum is maximal.

We resisted the temptation to use naked recursion. We could have tried transforming the numbers into the obvious binary tree, and defined the sum at the root to be the number at the root plus the max of the sums of the root's two subtrees, with appropriate stopping conditions at the leaves. For a small problem (like this one) it would have worked, but that algorithm uses resources exponential wrt to the depth of the tree. The algorithm actually used is quadratic wrt to the the number of elements in the last line of the triangle.

Docs: split-lines


Problem 19: how many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? The original problem statement is available here.

(ns org.drcabana.euler.prob19)
(defn solution []
      [year        (mapcat #(range 1 (inc %))
                           [31 28 31 30 31 30 31 31 30 31 30 31])
       leap-year   (mapcat #(range 1 (inc %))
                           [31 29 31 30 31 30 31 31 30 31 30 31])
       days-per-century (+ (* 25 366) (* 75 365))                    ;; 25 leap years, 75 std years
       days-of-week     (cycle [:tue :wed :thu :fri :sat :sun :mon]) ;; 1/1/1901 was a Tuesday
       calendar-dates   (cycle (concat year year year leap-year))    ;; 1904 was a leap year
       Sunday?          (fn [[day date]] (= :sun day))
       first-of-month?  (fn [[day date]] (= 1 date))]
    (->> (map vector days-of-week calendar-dates)
         (take days-per-century)
         (filter Sunday?)
         (filter first-of-month?)

The solution is quite mechanical. We construct two sequences: one of calendar dates, and one of weekdays. Both sequences cycle endlessly. We count off a century's worth of elements from each sequence, pair up corresponding elements, filter out the pairs which satisfy our criteria, and count how many did so.

Docs: cycle mapcat vector


Problem 20 is to find the sum of the digits in the number 100!. The original problem statement is available here.

(ns org.drcabana.euler.prob20)
(defn solution []
  (->> (reduce *' (range 1 101)) ;; use of *' avoids overflow
       (str)                     ;; convert to string
       (map #(Integer. (str %))) ;; convert each digit to an integer
       (reduce +)))

Problem 21: Define d(n) as the sum of the proper divisors of n. If d(a) = b and d(b) = a, where a != b, then a and b are called amicable numbers. Sum the amicable numbers less than 10000. The original problem statement is available here.

(ns org.drcabana.euler.prob21)

Compute the divisors of n. Each divisor is counted only once.

(defn divisors
  ([n d] (when (zero? (rem n d)) [d (quot n d)] ))
  ([n] (let [upperlim (inc (int (Math/sqrt n)))]
    (into #{} (mapcat #(divisors n %) (range 1 upperlim))))) )
(defn sum-of-divisors
  (reduce + (divisors n)))

Predicate: is n an amicable number?

(defn amicable?
  (let [m  (- (sum-of-divisors n) n)
        k  (- (sum-of-divisors m) m)]
    (and (= n k)
         (not= n m))))
(defn solution []
  (reduce + (filter amicable? (range 1 10000))))

Docs: into mapcat not= quot when


Problem 22: Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714. What is the total of all the name scores in the file? The original problem statement is available here.

(ns org.drcabana.euler.prob22)
(defn solution []
        point-values (zipmap alpha (iterate inc 1))
        score  (fn [name]
                 (reduce + (map point-values name)))
        names (->> (slurp "data/names.txt")
                   (re-seq #"[A-Z]+" )
    (reduce + (map * (map score names) (iterate inc 1) ))))

Docs: slurp sort zipmap


Problem 23: A positive integer n is called abundant if the sum of its proper divisors exceeds n. It can be proven that every integer greater than 28123 is the sum of two abundant numbers. Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. The original problem statement is available here.

(ns org.drcabana.euler.prob23
  (:use [org.drcabana.euler.prob21 :only (divisors)]))
(defn abundant?
  (let [divs (divisors n)
        sum-proper-divisors (fn [k] (- (reduce + divs) k))]
    (> (sum-proper-divisors n) n)))

The magic constant 28123 is stipulated by the problem.

(def limit (inc 28123))

There are 6072 elements in abundants.

(def abundants (vec (filter abundant? (range 1 limit))))

Construct the set of numbers below limit which are the sum of two members of abundants.

(defn sums-of-abundants []
  (into #{}
        (for [a abundants b abundants :when (<= a b) :when (< (+ a b) limit)]
          (+ a b))))
(defn solution []
  (let [total-all (reduce + (range 1 limit))
        total-soa (reduce + (sums-of-abundants))]
    (- total-all total-soa)))

Docs: into vec


Problem 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? The original problem statement is available here.

(ns org.drcabana.euler.prob24)

The simple approach is to use brute force. Notice that each :when condition uses a set as a function to test for membership in the set. We simply force a through j to be distinct.

(defn perms []
  (let [symbols (range 10)]
    (for [a symbols
          b symbols :when (nil? (#{a} b ))
          c symbols :when (nil? (#{a b} c))
          d symbols :when (nil? (#{a b c} d))
          e symbols :when (nil? (#{a b c d} e))
          f symbols :when (nil? (#{a b c d e} f))
          g symbols :when (nil? (#{a b c d e f} g))
          h symbols :when (nil? (#{a b c d e f g} h))
          i symbols :when (nil? (#{a b c d e f g h} i))
          j symbols :when (nil? (#{a b c d e f g h i} j))]
      [a b c d e f g h i j])))

The Project Euler problem statement require the permutation to be represented as a 10 digit integer.

(defn perm-to-integer [perm]
  (bigint (apply str perm)))

We generate permutations in lex order, and just pick the one we want. Clojure uses 0-based indexing, but the problem implicitly uses 1-based indexing. We need to adjust the index to get our answer.

(defn solution []
  (perm-to-integer (nth (perms) 999999)))

The brute force approach generated a lot of permutations we did not need. A fancier algorithm can compute the desired permutation directly. The algorithm takes advantage of a relationship between permutations of the digits 0...9 and the representation of integers in a factorial base. The details are beyond the scope of these comments, but the interested reader might look at this Wikipedia article.

Compute the factorial of n.

(defn fac
  (reduce * (range 2 (inc n))))

Compute the sequence of factorials of the positive integers.

(defn factorials
  (map fac (iterate inc 1)))

Express the positive integer n as the coefficients of linear combination of factorials.

=> (fdase 134)
(1 0 2 1 0)
;; 134 = 1*5! + 0*4! + 2*3! + 1*2! + 0*1!
(defn fbase
     (let [basis (reverse (take-while #(<= % n) (factorials)))]
       (fbase n basis [] )))
  ([n basis accumulator]
     (if (empty? basis)
       (let [b (first basis)]
         (recur (rem n b)
                (rest basis)
                (conj accumulator (quot n b)))))))

The nth permutation of the symbols 0-9 in lex order, indexing is 1-based.

(defn nth-perm
  (loop [symbols (range 10)
         indices (fbase (dec n))
         result  []]
    (if (empty? indices)
      (concat result symbols)
      (let [k           (first indices)
            sym         (nth symbols k)
            without-sym (concat (take k symbols)
                                (drop (inc k) symbols))]
        (recur without-sym
               (rest indices)
               (conj result sym))))))
(defn solution-alternative []
  (perm-to-integer (nth-perm 1000000)))

Docs: concat conj nth


Problem 25: What is the index of the first Fibonacci number at least 1000 digits long? The original problem statement is available here.

(ns org.drcabana.euler.prob25
  (:use [clojure.math.numeric-tower :only (expt)]
        [org.drcabana.euler.prob02  :only (fibonacci)]))

The problem implicitly uses 1-based indexing, Clojure uses 0-based indexing. So counting the 'too-small' cases gives the expected answer.

(defn solution []
  (let [limit (expt 10 999)
        too-small? #(< % limit)]
    (->> (fibonacci)
         (take-while too-small?)

Problem 26 is to find the positive integer k < 1000 for which 1/k contains the longest recurring cycle in its decimal expansion. The original problem statement is available here.

(ns org.drcabana.euler.prob26)

This problem centers about the algorithm for long division. Suppose n and d are positive integers. We want to divide n by d. If n > d, as our first step we compute (quot n d) and (rem n d). If not, we multiply n by 10 and then proceed as before. Each step subsequent step in long division is much the same.

(defn div-step [[n d]]
  (if (>= n d)
    [(* 10 (rem n d)) d]
    [(* 10 n) d]))

Lets see the division-step function in action. Consider 1/7, whose decimal expansion is 0.(142857) where the parens denote a recurring block of digits.

=> (take 7 (iterate div-step [1 7]))
([1 7] [10 7] [30 7] [20 7] [60 7] [40 7] [50 7])

Hmm, that may not seem entirely clear. It becomes clearer if we actually compute the quotients denoted by each pair.

(defn quotient [[n d]] (quot n d))
=> (take 7 (map quotient (iterate div-step [1 7])))
(0 1 4 2 8 5 7)

At this point we have the machinery needed to compute decimal expansions. Next we focus on finding the recurring block of digits. The following utility function will be useful.

Find the first repeated element in a sequence. If none is found, return nil.

(defn first-repeated-element
  ([xs] (first-repeated-element xs #{}))
  ([xs already-seen]
     (when-let [f (first xs)]
       (if (already-seen f)
         (recur (next xs) (conj already-seen f))))))

The first-repeated-element function would not terminate if given an infinite sequence with no repeated elements, but that is not a problem here. We are ready to go.

Compute the recurring digits in the decimal expansion of 1/k for integer k.

(defn recurring-digits
  (let [steps (iterate div-step [1 k])
        fre (first-repeated-element steps)]
    (->> steps
         (drop-while #(not= fre %)) ;; lose any noise such as leading 0's
         next                       ;; drop the leading fre
         (take-while #(not= fre %)) ;; grab upto next instance of fre
         (cons fre)                 ;; put back the fre we dropped
         (map quotient))))
=> (recurring-digits 7)
(1 4 2 8 5 7)

Let's wrap this up.

(defn solution []
  (let [scores (for [k (range 1 1001)]
                 [k (count (recurring-digits k))])]
    (->> scores
         (sort-by second) ;; 2nd element is the number of recurring digits
         last             ;; the last pair has the largest 2nd element

For quadratics of form n² + an + b, where |a| < 1000 and |b| < 1000, find the a and b that produce the longest run of primes for consecutive values of n, starting with n = 0. Return the product of a and b. The original problem statement is available here.

(ns org.drcabana.euler.prob27
  (:use [org.drcabana.euler.prob07 :only (prime? primes)]))

We'll need to construct quadratic functions specified by parameters a and b. Each generated function will be tagged with the product a*b.

(defn quadratic [a b]
  (let [q (fn [n] (+ (* n n) (* a n) b))
        t (* a b)]
    [t q]))

We score the quadratic function q by counting the length of the run of primes it generates. The returned value is a pair [t n] where t is the tag a*b, and n is the length of the run.

(defn score
  [[t q]]
  (->> (map q (range))
       (take-while prime?)
       (vector t)))

A quick glance at the problem statement might suggest that we need to vary both a and b over (range -999 1000), giving nearly four million cases to consider. We can do better by an order of magnitude.

We are interested in quadratics that generate primes. In particular, for any quadratic q, we require (q 0) to be prime. But (q 0) is equal to b. Instead of testing 1999 values of b, we can restrict b to the 168 primes less than 1000.

(defn solution []
  (let [quads (for [a (range -999 1000)
                    b (take-while #(< % 1000) (primes))]
                (quadratic a b))]
    (->> (for [q quads] (score q))
         (sort-by second)
         last ;; the last pair contains the high score

Notice the similarity of the solution function for this problem to that of problem 26.


Starting at 1 and moving to the right in a clockwise direction, a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

The sum of the diagonals is 101. What is the sum of the the diagonals in a 1001 by 1001 spiral formed in the same way? The original problem statement is available here.

(ns org.drcabana.euler.prob28)

Forget the diagonals. Consider the concentric squares centered at 1. Notice that the square with upper right corner 9 contains exactly 9 numbers, and so has a side of length 3. Similarly, the square with upper right corner 25 contains 25 numbers and has side 5. A bit of thought shows that the sides of the concentric squares are the odd numbers, starting from 3.

Why do we care about the concentric squares? Because it is easy to sum the corners of the squares, and that sum across all the squares differs from the sum of the diagonals by exactly 1.

Consider a particular square, say the square of side n=5, with corners 25, 21, 17, and 13. Expressed symbolically, the corners are n2, n2 - n + 1, n2 - 2n + 2, and n2 - 3n + 3.

(defn sum-of-corners [n]
  (+ (* 4 n n ) (* -6 n) 6))

The solution is immediate, and uses the standard idioms.

(defn solution []
  (let [odds (range 3 1002 2)]
    (inc (reduce + (map sum-of-corners odds)))))

Problem 29 is to count the distinct terms are in the sequence generated by a*b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100. The original problem statement is available here.

(ns org.drcabana.euler.prob29
  (:use [clojure.math.numeric-tower :only (expt)]))

This one is immediate.

(defn solution []
  (count (distinct (for [a (range 2 101)
                         b (range 2 101)]
                     (expt a b)))))

Problem 30 is to find the sum of the integers greater than 1 that can be written as the sum of fifth powers of their digits. The original problem statement is available here.

(ns org.drcabana.euler.prob30
  (:use [org.drcabana.euler.prob16 :only (digits)]
        [clojure.math.numeric-tower :only (expt)] ))

We'll need a function to compute the sequence of digits of n. Fortunately, we already have one of those, digits, left over from problem 16.

=>(digits 12345)
(1 2 3 4 5)

It's hard to come up with a good short name for a function that computes the sum of the fifth powers of the digits of n. I'll just call it phi, which is Greek for foo.

(defn phi [n]
  (reduce + (map #(expt % 5) (digits n))))

We need a name for integers that satisfy (== n (phi n)). Let's call them guilty numbers, and write a predicate to recognize them.

(defn guilty? [n]
  (== n (phi n)))

The question is what to do now. We could use guilty? to filter the integers. Let's do that, and take a peek at the first element of the sequence.

=>(take 1 (filter guilty? (iterate inc 2)))

The trouble with this approach is that we don't know how many guilty numbers there are. The problem statement implies that there are only finitely many, but we don't know exactly how many. So using take as above is out. If we try to take too many, the search for more will not terminate.

We need an upper bound B on the size of the largest guilty number. Given such a bound, our solution would be (reduce + (filter guilty? (range 2 B))).

As it turns out, guilty numbers can't get very large. Why? Given any k-digit n, (phi n) is bounded above by (* k (expt 9 5)). Let's look at some concrete numbers.

=>(for [k '(9999 99999 999999)] [k (phi k)])
([9999 236196] [99999 295245] [999999 354294])

Notice that 999999 is much larger than (phi 999999), so there can not be any guilty numbers larger than 999999. This upper bound is not very tight, but it's good enough for the purpose at hand.

(defn solution []
  (reduce + (filter guilty? (range 2 999999))))

In British currency there are eight coins: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). How many different ways can one make change for £2? The original problem statement is available here.

(ns org.drcabana.euler.prob31)

Some variation of this problems appears in almost every introduction to combinatorics. Two simple ideas combine to give an elegant solution to the problem.

The first idea is obvious. When making change for N, either we use coin c, or we don't. So the number of ways to to make change is A+B, where A and B denote the following:

A : the number of ways to make change using c

B : the number of ways to make change without using c

The second idea is that the number of ways to make change for N using c is exactly the same as the number of ways to make change for N-c. Why? Consider any way to make change for N using c. Simply remove one instance of the coin c and you have change for N-c.

These two insights combine to give a very pretty recursive solution to the problem.

(defn ways-to-make-change [amount coins]
  {:pre [(apply < coins)]}  ;; we require the coins sorted
  (let [c (first coins)]
     (nil? c) 0             ;; no coins, no change
     (< amount c) 0         ;; if c is too big, so are the remaining coins
     (== amount c) 1
     :else (+ (ways-to-make-change amount (rest coins))
              (ways-to-make-change (- amount c) coins)))))
(defn solution []
  (ways-to-make-change 200 [1 2 5 10 20 50 100 200]))

This is one of those problems where recursion leads to a very natural solution. Just for grins, try writing a non-recursive solution.

Docs: apply


An n-digit number is pandigital if it makes use of each of the digits 1 to n exactly once. For example, the 5-digit number 15234 is pandigital.

The product 7254 is unusual because the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital. Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital expresssion. Count each product only once. The original problem statement is available here.

(ns org.drcabana.euler.prob32
  (:use [clojure.math.combinatorics :only [permutations]]))

The fact that we want to use each of the digits 1 through 9 exactly once immediately suggests that we will want to generate permutations. Way back in problem 24 we generated permutations of the digits 0-9, by brute force.

(defn perms []
  (let [symbols (range 10)]
    (for [a symbols
          b symbols :when (nil? (#{a} b ))
          c symbols :when (nil? (#{a b} c))
          d symbols :when (nil? (#{a b c} d))
          e symbols :when (nil? (#{a b c d} e))
          f symbols :when (nil? (#{a b c d e} f))
          g symbols :when (nil? (#{a b c d e f} g))
          h symbols :when (nil? (#{a b c d e f g} h))
          i symbols :when (nil? (#{a b c d e f g h} i))
          j symbols :when (nil? (#{a b c d e f g h i} j))]
      [a b c d e f g h i j])))

That was fine for a one time thing, and it allowed me to illustrate both the :when notation, and the use of sets as their own characteristic functions. But one time was enough. It is rarely a good idea to roll your own mathematical functions when those functions are available as library functions. This time we'll use the permutations function provided by the clojure.math.combinatorics library.

Given a permutation, for example [ 3 9 1 8 6 7 2 5 4], we will split it into three parts, say [[3 9] [1 8 6] [7 2 5 4]], and then turn each of the parts into the number represented by the corresponding digits, here [39 186 7254]. We'll then test to see whether the product of the first two numbers is equal to the third.

Let's write some code. First we'll handle turning sequences of digits into numbers. Horner's algorithm is simple, efficient, and easily expressed using the reduce function. Notice that reduce can take an initial scalar argument in addition to the usual sequence argument. That initial arg shines here.

(defn horner
  [& digits]
  (reduce #(+ (* 10 %1) %2) 0 digits))

There are only two ways to split the permutations into three numbers such that the product of the first two is equal to the third. For instance, the product of two single digit numbers cannot equal a seven digit number. A bit of thought eliminates the other impossible cases. The feasible splits are either a two digit number and a three digit number producing a four digit number, or a one digit number and a four digit number producing a four digit number.

(defn phi [[a b c d e f g h i]]
  (let [x (horner a b)
        y (horner c d e)
        y1 (horner b c d e)
        z (horner f g h i)]
        (== z (* x y)) z
        (== z (* a y1)) z
        :else 0)))

I did not even try to give that last function a meaningful name. Mathematicians have very few qualms about meaningless function names, but some programmers find it difficult to let go. To them I say relax, take a walk on the wild side.

The problem requires that any given product be counted only once. The distinct function is tailor made for that job.

(defn solution []
  (->> (range 1 10)
       (map phi)
       (reduce +)))

Docs: cond distinct reduce


49/98 is a curious fraction, because it allows incorrect cancellation. One can cancel the 9, which is absurd, and still get the right result 49/98 = 4/8. We shall consider fractions like 30/50 = 3/5 as trivial. There are four non-trivial curious fractions less 1, with two digit numerator and denominator. If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

The original problem statement is available here.

(ns org.drcabana.euler.prob33)

Here's a better way to think about 'curious' fractions. The fraction 4/8 is curious because there exists a single digit integer n (n=9 as it happens) such that 4/8 = 4n/n8. Here juxtaposition does not denote mulitplication. Instead 4n denotes 4*10+n, and n8 denotes n*10 +8.

We need a way to turn two digits into a number in the obvious way.

(defn number [a b]
  (+ (* 10 a) b))

When the fraction j/k is curious return j/k, otherwise return nil. The numerator and denominator of Clojure ratios are relatively prime, i.e., have no common factors.

(defn curious
  ([[j k]]
     (first (keep (partial curious [j k])
                  (range 1 10))))
  ([[j k] n]
     (let [jn (number j n)
           kn (number k n)
           nj (number n j)
           nk (number n k)]
       (some #{(/ j k)}
             [(/ jn kn) (/ jn nk) (/ nj kn) (/ nj nk)] ))))
(defn solution []
  (->> (for [a (range 1 10)
             b (range 1 10)]
         [a b])
       (keep curious)
       (filter #(< % 1))
       (reduce *)

Something I have neglected to mention so far is that in the ->> macro, one is not required to put parens around a function of a single argument. For instance, I could have written the solution this way.

(defn solution-alternate []
  (->> (for [a (range 1 10)
             b (range 1 10)]
         [a b])
       (keep curious)
       (filter #(< % 1))
       (reduce *)

Notice that denominator is not enclosed in parens. As a matter of taste I prefer the parens. It looks more uniform to me. I'm going to guess that anyone reading this is not likely to be parenphobic.

Docs: denominator keep partial some