Project Euler solutions in Clojure (4-6) 25 Jan 2012
I thought these three problems were significantly easier than the first three, but YMMV.
Problem 4
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.
With such a small search space, I decided to just brute force this one.
First, I needed a function to tell whether or not a number is a palindrome. Since numbers can be converted to strings and strings can be treated like sequences, a combination of str, seq, and reverse were enough to do the job. palindrome? takes a number, converts it to a string and then to a sequence, and then sees if the sequence and its reverse are the same.
The solution itself is just a brute force walk through the search space. I made a guess that the answer would be the product of two numbers above 900 (if the search had come up empty I could have just expanded the search space), and a simple for loop did the trick. One thing to note in this solution is the definition of the y term — because multiplication is commutative, if I defined both x and y as (range 999 900 -1) I would get every palindrome twice. Of course the max function would still return the correct answer, but it's a massive waste of time. By defining y in terms of x, so that it always begins at x and then descends to 900, I cut the number of computations in each loop down significantly.
Problem 5
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 problem in which the brute force approach doesn't work (or at least it doesn't work fast enough to avoid me getting impatient and killing the process). The first time I tried it, I just created an infinite lazy sequence of integers and checked them one by one. I waited a minute or two and then killed the bugger and went back to the drawing board.
I'm ashamed to say it took me more than a few minutes to notice the really big clue in the first sentence of the question. If 2520 is known to be divisible by the numbers from 1 to 10, then any number that is divisible by the numbers 1 to 20 (a superset of 1 to 10) would also have to be divisible by 2520! Instead of incrementing by 1 and checking, I can increment by 2520 — yessir, I'll take that 2520x speed increase. :)
The solution is still brute force, but it's fairly quick (234ms on my laptop). I wrote a utility function divisible-by-sequence? (which I bet will come in handy in the future) which returns true if n is evenly divisible by every number in xs, and then I just generate multiples of 2520 until I find a match.
Problem 6
The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 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.
I thought this problem was ridiculously easy, though perhaps it's just that manipulating sequences of numbers in Clojure is ridiculously easy. To solve it, I need to generate two numbers, and then subtract one from the other. Since they're both based on the same range (the first 100 natural numbers), the appropriately named range function will give me the raw material to work with, and then a couple of simple reduce calls and a map will bring me to glory. :)
Like I said, ridiculously easy. s1 is the square of sums and s2 is the sum of squares. Clojure doesn't have a built-in function to raise a number to an exponent, but Java's Math/pow function is available (it returns a double, though, so I forced them back into integers using int).
If you liked these, you may also be interested in my other Project Euler solutions in Clojure.
- Next: Introducing clj-numbers
- Previous: Project Euler solutions in Clojure (1-3)
