Problem 005: Smallest Multiple

From Project Euler:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

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

This is a pretty straight-forward problem: we're just trying to find the least-common multiple (LCM) of a set of numbers. To find the LCM, it is just the product of the two numbers $a$ and $b$ divided by their greatest common divisor (GCD). If we think for a second about why this works: any number is just a product of prime factors. A prime number is just a product of itself and 1, composite numbers are a more complex sequence: 12 is a product of 2 * 2 * 3, 8 is a product of 2 * 2 * 2. When you multiply the two numbers together, you're a making a long sequence of prime factors that will result in the product of $a$ and $b$.

This product however is not the least common multiple, because there could be factors in common between $a$ and $b$: both 8 and 12 have a common factor of 2 * 2, if we simply multiplied them together we'd get 96 when the LCM is actually 24. We should divide by the GCD (2 * 2) to filter out these common factors. This gives us the correct result: 96 / 4 = 24.

Here's the code, which uses the Euclidean algorithm to find the GCD of two numbers:

(defn gcd [a b]
  (cond 
    (< a b) (gcd b a)
    (== 0 b) a
    :else (gcd b (mod a b))))

(defn lcm [a b]
  (if (or (== a 0) (== b 0))
    0
    (quot (* a b) (gcd a b))))

Then we can just do a reduce to get the LCM of the range:

(println (reduce lcm (range 1 21)))

This runs pretty fast (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 5.clj
232792560

real 0m1.585s
user 0m3.136s
sys 0m0.151s

An alternative approach is to use something like the Sieve of Eratosthenes (SoT). This is an algorithm for finding prime numbers, but we can use the same idea here. The way the SoT works is you take a list of numbers from 2 to $N$. For each number $i$, you loop through the rest of the list, removing any multiple of $i$. After the first pass we'll have removed all numbers divisible by 2, after the second pass all numbers divisible by 3, etc. What we'll be left with is just a list of prime numbers. We'll apply the same idea here, but instead of removing the number if it is divisible, we'll divide out our current factor.

(defn lcm-sieve [xs]
  (if (empty? xs) ()
    (let [head (first xs)
          tail (rest xs)]
      (cons head
            (lcm-sieve (map #(if (== 0 (mod % head))
                               (quot % head)
                               %)
                              tail))))))

This algorithm efficiently gives us the list of prime factors for the LCM:

user=> (lcm-sieve (range 1 11))
(2 3 2 5 1 7 2 3 1)

These can be combined using reduce:

(println (->> (range 1 21)
              (lcm-sieve)
              (reduce *)))

This gives the correct result:

rob@alien ~/code/euler $ time clj 5.clj
232792560

real 0m1.549s
user 0m3.014s
sys 0m0.143s

Both methods seem quite fast, I hit integer overflow on my machine without either of them taking more than half a second. The reason I dove into the second one is that the SoT algorithm is the basis for a lot of my solutions in the future, so it's good to see a version of it now.

Problem 004: Largest Palindrome Product

From Project Euler:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

For this one we'll need to define a few helpers. First, we need a function that determines if a number is palindromic. In order to do that, we'll need to create a function to reverse a number. We could do this easily by converting the number to a string, reversing it, and then converting it back to a number (to avoid issues with leading zeroes) but that's cheating and we can just do it with integer math. Each iteration we have an accumulated number, we just take modulo 10 of our current number and add it to 10 times our accumulator, and then divide our number by 10 to chop off that digit:

(defn reverse-num [n]
  (letfn [(helper [i reversed]
            (if (== i 0)
              reversed
              (helper (quot i 10)
                      (+ (mod i 10)
                         (* 10 reversed)))))]
    (helper n 0)))

We can then use that to define is-palindromic?:

(defn is-palindromic? [n] (== n (reverse-num n)))

Once we have those, we can (mostly) brute force things to get the correct result. We can use a for comprehension to get all the numbers that are products of two 3-digit numbers. We'll do one optimization which is where the second variable y only ranges from the first variable x to 999, since multiplication is commutative and once we've checked 101 * 500 we don't need to check 500 * 101.

(def N 1000)

(println (->> (for [x (range 100 N)
                    y (range x N)]
                (* x y))
              (filter is-palindromic?)
              (apply max)))

There are several other optimizations we can do, if you're interested you can look in the forums for all sorts of creative solutions. However, this code gives the result in a reasonable amount of time (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 4.clj 
906609

real 0m1.747s
user 0m3.478s
sys 0m0.176s

Problem 003: Largest Prime Factor

From Project Euler:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

This is the first problem with primes. There are some good ways to find primes, however for this simple problem we'll use a simple solution. First, let's define a function that tells us if a number $n$ is prime. The way it works is it will test every number $i$ from 2 to $\sqrt{n}$ to see if $n$ is divisible by $i$. If it is, then $n$ is not prime. We only need to go up to $\sqrt{n}$ because all non-prime numbers will have at least one factor between 2 and their square root.

(defn is-prime? [n]
  (->> (range 2 (int (Math/ceil (Math/sqrt n))))
       (some #(== (mod n %) 0))
       (not)))

From here, we can now filter through and find divisors of 600851475143, and figure out which is the maximum.

(def N 600851475143)

(println
  (->> (range 2 (int (Math/ceil (Math/sqrt N))))
       (filter #(== (mod N %) 0))
       (filter is-prime?)
       (apply max)
       ))

This gives us the correct result (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 3.clj
6857

real 0m1.651s
user 0m3.232s
sys 0m0.138s

There are more efficient ways to find primes: one good one to use is a prime sieve. We don't really need that for this problem since the number is fairly small, but for more advanced problems later on we'll want to use that approach.

Problem 002: Even Fibonacci Numbers

From Project Euler:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

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

There are typically two ways to work with Fibonacci numbers. You can either use the formula to generate the nth Fibonacci number, a formula that involves taking powers of the golden ratio $\phi$; or you can just simply start from the beginning and iterate through them.
For this one, we'll iterate through and accumulate values as we go along. A simple approach here would be to generate the list of Fibonacci numbers that are less than 4 million, filter out the odd ones, then reduce the list. Something like this:

(<<- (gen-fibs-to 4000000)
     (filter even?)
     (reduce +))

This has a time complexity of O(n), but it also has a space complexity of O(n). We can do better than that. Instead of first generating all the Fibonacci numbers, we can instead just stream through, accumulating values as we need to. A common pattern to do this is to define a local function that accepts an accumulator value, and add the even numbers to it. We quit when we've passed our limit.

(defn sum-even-fibs [n]
  (letfn [(accum [a b sum n]
            (if (>= b n)
              sum  ; we've passed the limit, return the total
              (accum b (+ a b)
                     (+ sum (if (even? b) b 0))
                     n)))]
    (accum 1 2 0 n)))

(println (sum-even-fibs 4000000))

Running this program gives us the correct answer very quickly (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 2.clj 
4613732

real 0m1.532s
user 0m3.136s
sys 0m0.096s

Problem 001: Multiples of 3 and 5

From Project Euler:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

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

For this one, it's pretty simple just to iterate through all the numbers and add them up as needed (I use threading syntax here because I think it's more readable):

user=> (->> (range 1 1000)
            (filter #(or (== 0 (mod % 3)) (== 0 (mod % 5))))
            (reduce +))
233168

However we don't even need to loop. Since we care only about the sum and not the numbers themselves, we can apply a little bit of number theory. What we want is the sum of all the multiples of 3 or 5. This is equal to the sum of all the multiples of 3, plus the sum of all the multiples of 5, minus the sum of all the multiples of 15 to avoid double-counting.

We can rewrite the sum of the multiples of 3 from 1 to 999 (because we don't want to include 1000) as 3 times the sum of all numbers from 1 to 999 / 3, or 333. There's a formula to get the sum of numbers from 1 to n:
$$
\sum^n_{i=1} i = \frac{n(n+1)}{2}
$$
Which we can write in Clojure like this:

(defn sumto [n] (quot (* n (+ n 1)) 2))

To get the sum of the multiples of 3 from 1 to 1000, we can just write:

(* 3 (sumto (quot 999 3)))

Then to get the final result, it's simply a matter of combining everything together:

user=> (+ (* 3 (sumto (quot 999 3)))
          (* 5 (sumto (quot 999 5)))
          (- (* 15 (sumto (quot 999 15)))))
233168