Project Euler - first 100 problems

Last updated: Mar 20, 2025.

My solutions to the problems from Project Euler.

Problem 1

Difficulty: 5%

Find the sum of all multiples of 3 or 5 below 1000.

(->> (range 1000)
     (filter #(or (zero? (mod % 3)) (zero? (mod % 5))))
     (reduce +))

233168

Problem 2

Difficulty: 5%

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

(loop [f1 1,
       f2 2,
       even-sum 0]

  (if (>= f2 4000000)
    even-sum
    (if (zero? (mod f2 2))
      (recur f2 (+ f1 f2) (+ even-sum f2))
      (recur f2 (+ f1 f2) even-sum))))

4613732

Problem 3

Difficulty: 5%

Find the largest prime factor of 600851475143.

We’ll just brute force all primes below \(\sqrt{N}\) and try them as divisors.

(let [N 600851475143]
  (->> (primes/sieve-of-eratosthenes (int (Math/sqrt N)))
       reverse
       (filter #(zero? (mod N %)))
       first))

6857

Problem 4

Difficulty: 5%

Find the largest palindrome made from the product of two 3-digit numbers.

We write a function to check if an integer is a palindrome.

(defn is-palindrome? [x]
  (let [xstr (Integer/toString x)]
    (= (map char xstr) (reverse xstr))))

Run through all \(a \times b\) where \(a, b \in [100, 999]\).

(->> (for [a (range 100 1000)
           b (range 100 1000)
           :when (is-palindrome? (* a b))]
       (* a b))
     sort
     last)

906609

Problem 5

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I was happy to solve this with just pen and paper. Let \(N\) be the answer we seek. It has to be divisible by every prime and composite number \(\le 20\). But since the composite numbers upto \(20\) are themselves just products of primes smaller than themselves, we can write

\[ N = 2^a \cdot 3^b \cdot 5^c \cdot 7^d \cdot 11^e \cdot 13^f \cdot 17^g \cdot 19^h \]

For each prime above, the exponent has to be the highest exponent of that prime that appears in the factorization of any of the numbers \(1..20\). For example, \(a = 4\) because \(16 = 2^4\) and for \(N\) to be divisible by \(16\) it must have \(2^4\) as a factor. Similarly for \(N\) to be divisible by \(18\) and \(9\) it must have \(3^2\) as a factor. By doing this for all the primes we get the answer:

(* (* 2 2 2 2) (* 3 3) 5 7 11 13 17 19) 232792560

Problem 6

Difficulty: 5%

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

(- (int (Math/pow (->> (range 1 101)
                       (reduce +))
                  2))
   (->> (range 1 101)
        (map #(int (Math/pow % 2)))
        (reduce +)))

25164150

Problem 7

Difficulty: 5%

What is the 10,001st prime number?

As a consequence of the Prime Number Theorem (wiki), the \(N\)th prime is approximately

\[N \ ln(N)\]

So we’ll generate all primes upto a little more than that number and pick out the 10,001st one.

(let [N 10001
      approx-nth-prime (* N (Math/log N))]
      (nth (primes/sieve-of-eratosthenes
            (int (* 1.2 approx-nth-prime)))
           (dec N)))

104743

Problem 8

Difficulty: 5%

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

We slide a 13-digit window across the 1000-digit number, compute each product and pick the maximum.

(def INPUT-8 (filter #(not= % \newline)
                     (slurp "src/code/data/euler-8-input.txt")))

(->> (for [i (range 0 (- (count INPUT-8) 13))]
       (reduce * 1 (map #(Character/digit % 10)
                        (take 13 (drop i INPUT-8)))))
     sort
     last)

23514624000

Problem 9

Difficulty: 5%

Find the one Pythagorean triplet for which \(a + b + c = 1000\).

We first write a function to check if a triplet is Pythagorean (\(a^2 + b^2 = c^2\)).

(defn is-pythagorean? [v]
  (let [[a b c] (sort v)]
    (= (* c c)
       (+ (* a a) (* b b)))))

(->> (for [c (range 1 1000)
           :let [aplusb (- 1000 c)]]
       (for [a (range 1 aplusb)
             :let [b (- aplusb a)]
             :when (and (distinct? a b c)
                        (is-pythagorean? (vector a b c)))]
         (sort [a b c])))
     (mapcat identity)
     distinct
     first
     (reduce * 1))

31875000

The triplet is (200 375 425).

Problem 10

Difficulty: 5%

Find the sum of all the primes below two million.

(reduce + 0 (primes/sieve-of-eratosthenes 2000000)) 142913828922

Problem 13

Difficulty: 5%

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

I absolutely love Clojure’s thread-last macro because it makes certain transformations of sequences perfectly concise and natural. Compare the English description and the code in the solution to this problem. In English,

1. Read the file with the input numbers.
2. Split the file into lines.
3. Convert each line (String) into a number (BigInteger).
4. Sum all the numbers.
5. Convert the sum back to a string.
6. Take the first 10 characters of the string.
7. Convert the sequence of 10 characters into a single string.

In code:

(->> (slurp "src/code/data/euler-13.txt")
     str/split-lines
     (map #(BigInteger. %))
     (reduce + 0)
     .toString
     (take 10)
     (apply str))

“5537376230”

Problem 14

Difficulty: 5%

The Collatz sequence is defined as: \(n_{i+1} = n_i / 2\) (when \(n_i\) is even) and \(n_{i+1} = 3n_i + 1\) (when \(n\) is odd). Assuming that every starting value eventually converges to 1, which starting value under one million produces the longest sequence?

(defn collatz-length
  "Return the length of the Collatz sequence starting at x"
  [x]
  (loop [n 1
         xi x]
    (cond
      (= xi 1) [x n]
      (= (mod xi 2) 0) (recur (inc n) (quot xi 2))
      :else (recur (inc n) (+ (* 3 xi) 1)))))

(->> (range 2 1000000)
     (map collatz-length)
     (apply max-key second))

[837799 525]

Problem 16

Difficulty: 5%

Find the sum of the digits of \(2^{1000}\).

(->> (.toString (.pow (BigInteger/valueOf 2) 1000))
     (map #(Character/digit % 10))
     (reduce + 0))

1366

Problem 17

Difficulty: 5%

Write out each number 1-1000 (inclusive) as words. For example \(342\) = “three hundred and forty-two”. Count the total number of letters, excluding spaces and hyphens.

We define all the words needed for this problem.

(def DIGITS
  {
   1 "one"
   2 "two"
   3 "three" 
   4 "four"
   5 "five"
   6 "six"
   7 "seven"
   8 "eight"
   9 "nine"
   }
)

(def TEENS
  {
   11 "eleven"
   12 "twelve"
   13 "thirteen"
   14 "fourteen" 
   15 "fifteen"
   16 "sixteen"
   17 "seventeen"
   18 "eighteen"
   19 "nineteen"
  })

(def TENS
  {
   10 "ten"
   20 "twenty"
   30 "thirty"
   40 "forty"
   50 "fifty"
   60 "sixty"
   70 "seventy"
   80 "eighty"
   90 "ninety"
  })

Next we define two functions to count the number of letters needed to express the hundreds place value and the tens place value parts of a number.

(defn hundreds-count [h]
  (if (zero? h) 0
      (+ (count (DIGITS h)) (count "hundred"))))

(defn tens-count [t]
  (cond 
    (zero? t) 0                              ;; when t is 0
    (< t 10) (count (DIGITS t))              ;; single digit numbers
    (<= 11 t 19) (count (TEENS t))           ;; teen numbers
    :else (+ (count (TENS (* 10 (quot t 10))))  ;; numbers 20-99
             (if (zero? (mod t 10))
               0
               (count (DIGITS (mod t 10)))))))

When counting the letters for a number, we need to handle the special case of whether “and” needs to be included. For example, \(342\) = “three hundred and forty-two” but \(100\) = “one hundred”.

(defn number-in-words-count [x]
  (let [h (quot x 100)
        t (mod x 100)
        and-count (if (and (> h 0) (not (zero? t))) (count "and") 0)]
    (+ (hundreds-count h) (tens-count t) and-count)))

The last special case to handle is the number \(1000\).

(+ (->> (range 1 1000)
     (map number-in-words-count)
     (reduce + 0))
   (count "onethousand"))

21124

Problem 19

Difficulty: 5%

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

First we need the definition of a leap year:

(defn is-leap-year? [y]
  (let [four (zero? (mod y 4))
        hundred (zero? (mod y 100))
        four-hundred (zero? (mod y 400))]
    (or (and four (not hundred))
        (and four hundred four-hundred))))

(map is-leap-year? [1900 1996 2000]) (false true true)

Then we need the number of days in any month of any year:

(defn days-in-month [m y]
  (case m
    1 31
    2 (if (is-leap-year? y) 29 28)
    3 31
    4 30
    5 31
    6 30
    7 31
    8 31
    9 30
    10 31
    11 30
    12 31))

Idiomatic Clojure style is to write immutable code. But I find this problem easier to solve by imagining adding up the days for each month starting from 1901.

(let [day (atom 2)      ;; Jan 1 1901 was a Tuesday
      result (atom 0)]

  (doseq [year (range 1901 2001)
          month (range 1 13)]
    (reset! day (mod (+ @day (days-in-month month year)) 7))
    (when (zero? @day)
      (println year month)
      (swap! result inc)))
  @result)

171

Problem 21

Difficulty: 5%

Let \(d(n)\) be the sum of all proper divisors of \(n\) (numbers less than \(n\) that divide \(n\)). If \(d(b) = a\) and \(d(a) = b\) while \(a \ne b\), then both \(a\) and \(b\) are called amicable numbers. Find the sum of all amicable numbers under 10000.

We sum the proper divisors of a number by brute force.

(defn sum-proper-divisors
  "Returns the sum of all divisors of n, excluding n itself"
  [n]
  (->> (range 1 (inc (Math/ceil (/ n 2))))
       (filter #(= (mod n %) 0))
       (reduce + 0)))

Define an amicable number.

(defn amicable? [a]
  (let [b (sum-proper-divisors a)]
    (and (not= a b)
         (= (sum-proper-divisors b) a))))

Check each number under 10000.

(->> (range 2 10001)
     (filter amicable?)
     (reduce + 0))

31626

Problem 22

Difficulty: 5%

Let the word-score of a name be the sum of its letters expressed as numbers (A = 1, B = 2, …). So for example COLIN = 53. Sort the list of names in the input file, compute the word score for each name, multiply the position of each name in the sorted list by its score and sum everything.

(defn word-score [w]
  (reduce + 0 (map #(- (int (Character/toUpperCase %)) 64) w)))

(word-score “COLIN”) 53

The key useful function here is map-indexed that turns a sequence into (index, value) pairs and applies a function to each such pair.

(let [sorted-names (->> (str/split
                         (slurp "src/code/data/euler_0022_names.txt")
                         #",")
                        (map #(str/replace % #"\"" ""))
                        sort)]
  (reduce + 0 (map-indexed
               #(* (inc %1) (word-score %2))
               sorted-names)))

871198282

Problem 65

Difficulty: 15%

\(e\) can be written as the continued fraction \([2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ... , 1, 2k, 1, ...]\)

The \(n\)th “convergent” of a continued fraction is the result of summing it upto \(n\) terms. Find the sum of the digits in the numerator of the 100th convergent of the fraction for \(e\).

First we write a generic function to sum the first \(n\) terms of a continued fraction.

(defn sum-terms
  [xs]
  (if (empty? xs)
    0
    (/ 1 (+ (first xs) (sum-terms (rest xs))))))

We can test that it works by computing \(\sqrt{2}\) upto 10 terms.

(float (+ 1 (sum-terms (repeat 9 2)))) 1.4142137

The fraction for \(e\) is slightly more complicated because the \(k\)th term can be either \(2k\) or \(1\).

(defn e-terms
  "The first n terms of the continued fraction for e"
  [n]
  (take n (map (fn [k]
                 (case (mod k 3)
                   0 1
                   1 (* 2 (inc (quot k 3)))
                   2 1))
               (range n))))

Now sum the first 100 terms and compute the sum of the digits of the numerator.

(reduce + (map #(Character/digit % 10)
               (str (numerator (+ 2 (sum-terms (e-terms 99)))))))

272

Helpers

These are helper functions used across problems.

Since many of the problems deal with prime numbers, let’s write the Sieve of Eratosthenes to generate all prime numbers below \(n\).

(defn sieve-of-eratosthenes
  [n]
  (let [sieve (BitSet. (inc n))]
    ;; Set all bits to true initially
    (.set sieve 0 (inc n))

    ;; 0 and 1 are not prime
    (.clear sieve 0)
    (.clear sieve 1)

    (doseq [x (range 2 (inc (int (Math/sqrt n))))]
      (doseq [i (range 2 (inc (quot n x)))]
        (.clear sieve (* x i))))

    (filter #(.get sieve %) (range 2 n))))