Clojure Euler: Problem 006

The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + … + 10^2 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

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

Permalink: http://projecteuler.net/problem=6

This problem is very simple, even simpler than previous one, that confirms fact that all Project Euler problems are NOT in increasing complexity order. Ok, let’s split our problem into two subproblems.

Sum of the squares

First, we need a square function:

(defn sqr [n] (* n n))

Then, sum of squares of the first one hundred natural numbers we calculate with common (reduce + list) idiom:

(reduce + (map sqr (range 1 101)))

Square of the sum

Just take a sum, and square it:

(sqr (reduce + (range 1 101)))

Bind all together

We splitted our problem into two smaller, now is time to bind all. We can just subtract results obtained but you see, that both of smaller solutions uses common piece of code (range 1 101). Move it to let form.

(let [rn (range 1 101)]
  (- (sqr (reduce + rn)) (reduce + (map sqr rn)))))

That’ all. I’ve got result in less than millisecond. Maybe there are some pitfalls in this problem (e.g. integer overflow for larger ranges) but this most straightforward solution works fine.

Congratulations!

GitHub

P.S. First time I solved this problem and was confused: Where is the trick? Seems nowhere. That’s why using most straightforward solution is often the best choice (excluding obvious cases, of course). It has fast implementation, and if it fails, it fails fast.

Fail Fast, Succeed Faster

mishadoff 17 November 2012
blog comments powered by Disqus