Code Words by John Biesnecker

Project Euler solutions in Clojure (1-3) 23 Jan 2012


In the last few posts I've written about my experiences with 4clojure. The problems there have been an absolutely fantastic way to improve my grasp of the language. The only downside to them is that they're specifically for Clojure, and often are aimed directly at understanding quirks in the language. Very useful, yes, but I want to try out my luck with Clojure on more general problems.

Enter Project Euler!

I'm going to try to work through the Project Euler problems in order, in Clojure. It's going to take a while — there are 368 of them as of this writing — but it should be an interesting and enlightening journey. I want to write about them so that 1) I can potentially get feedback from people that know more than I do about my solutions; and 2) to keep a record and (hopefully) be able to watch my Clojure-fu get stronger over time.

Wish me luck!

Problem 1

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.

This problem is actually the same as 4clojure #148, but a bit easier because asking for only numbers less than 1000 makes a number of naive approaches feasible (one of the 4clojure tests has n = 100003, which crushes a simple "check every number between 1 and n" solution).

An efficient solution involves calculating the sum of arithmetic progressions. In this problem, we're looking for the sum of two arithmetic progressions — multiples of 3 less than 1000 and multiples of 5 less than 1000. Since calculating the number of terms we care about is simple ((quot 999 3) and (quot 999 5)) we can use a simple formula to calculate the sum:

a is the first term, d is the difference between each term, and n is the number of terms being added together. Because we're interested in multiples of a single number, a and d are the same, so we could simplify the function if we wanted to, but instead we'll create a multiple-arity function that is a bit more reusable:

Just this function will almost give you the answer. If the question was asking for the sum of the multiples of a single number this function alone would be enough, but because it's asking for the sum of the multiples of either 3 or 5, there's an extra step involved.

Calculating the sum of multiples of 3 and 5 is now trivial, but since we're calculating them separately, numbers of that are divisible by both 3 and 5 are being counted twice, and they should only be counted once. In order to do this, we need subtract the sum of the multiples of 15 from the sum of the two sums. Enough talking, here's the (general) solution to the problem:

Because this approach doesn't rely on filtering long series of numbers, it will work efficiently for massive values of n. Running (euler-1 1000 3 5) in the REPL gives us 233168, which is the correct answer.

Problem 2

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.

The Fibonacci sequence is a classic, and is frequently used in explanations of Clojure's lazy sequences. The actual meat of the question (less than four million, sum of the even-valued terms) are very simple to do in Clojure, so the really interesting part of the question is how to actually generate the sequence.

The Clojure Programming wikibook already has a page outlining many different methods, though, so there's no need to go into much depth here. Check out the examples — all of them will work for our purposes. I personally prefer the "Properly Scoped Version" near the bottom of the page because of the garbage collection issues mentioned, so that's the one I'll use in my solution.

We can solve the rest of the problem using three functions: take-while, filter, and reduce. First, take-while will consume the Fibonacci sequence until the numbers exceed four million. filter will then strip all of the odd numbers out of the sequence, and finally we'll use reduce to sum all of the remaining numbers together. The final product looks like this:

Running (euler-2) in the REPL gives us 4613732, which is the correct answer.

It took me a while to appreciate the value and power of infinite lazy sequences, but now that I have (at least to some degree) I see their application in lots of places (it helps that Clojure's sequence manipulation tools are as powerful as they are).

Problem 3

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

What is the largest prime factor of the number 600851475143?

Here's another example where we can use Clojure's lazy sequences and sequence manipulation functions to make our life easier. To restate the problem, we're looking for the largest number that is:

  1. Less than the square root of 600851475143 (since one of any two factors of a number is always less than the square root of that number).
  2. A factor of 600851475143.
  3. A prime number.

Only the third constraint is at all challenging, so we'll start there.

By definition, a prime number if a number with only two factors: itself and 1. Thus, to prove that a number isn't prime, we just need to find another factor. If we start at 2 (which will weed out every even number in a single calculation) and go up to the square root of the number in question, we can either find another factor (generally near the beginning of the sequence) or prove that the number is a prime number. By using a function that produces a lazy sequence (in this case, map) and only consuming as much of that sequence as we absolutely need (using some to stop at the first hit) we do as few calculations as possible on each number. While this still wouldn't work on a very large number, the square root of 600851475143 is 775146.099, and on my laptop this function can prove that a six digit number if a prime in about 5 milliseconds (thank you Mr. Moore!).

The function to check if a number if a prime number is below:

Now that we have a way to check to see if a number is prime, the rest of the problem is simple. We just need to go from the square root of the number and head down toward one, stopping as soon as we find a factor that is also a prime (since we only care about the largest prime factor). Again, I'll give a general solution (though be warned call it with too large of a number it will take a long time, consume too much memory, etc.):

(euler-3 600851475143) gives 6857, which is the right answer. More importantly, it only takes about 100 milliseconds to compute on my laptop (and we could have parallelized it if we wanted to get more out of our CPU). Not too shabby for a 12 digit number.

Update

So, in an effort to make this problem easier I ended up making it much harder and more complicated than it needed to be. What I should have done is written a function that generates all of the prime factors of a number, and then picked the largest one out of that list. As long as the number is big and not prime, generating the prime factors is going to be a lot faster than blindly brute forcing my through all possible factors.

Here's a fairly efficient prime factorization function (that I wrote for a later Project Euler problem):

(prime-factors 600851475143) takes about half a millisecond, 1/200 of the time my original solution required.

If you liked these, you may also be interested in my other Project Euler solutions in Clojure.

Will and I at the beach in Panama City

how to contact me