euler !! 3

The next few problems are pretty easy, so I think we can knock out four (!!!) in one post.


Problem 4:
A palindromic number reads the same both ways. Find the largest palindrome made from the product of two 3-digit numbers.

A simple list comprehension accomplishes this. We can test for symmetry by using show, which converts a value to a string, and reverse.

[x | y <- [100..999], z <- [y..999], let x = y * z, show x == reverse (show x)]

let allows us to define local variables, similar to where.
We can improve the efficiency of this code by an order of magnitude by observing that any six-digit palindrome will be a multiple of 11, since it will be of the form 100001a + 1001b + 11c = 11*(9091a + 91b + c). Then we simply add a maximum and we're done:

problem4 = maxmimum [x | y <- [110,121..999], z <- [y..999], let x = y * z, show x == reverse (show x)]

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

This one is laughably trivial in Haskell, thanks to the built in lcm function:

problem5 = foldl1 lcm [1..20]

Folding a list is a common operation in functional languages. First, lcm is applied to 1 and 2, whose least common multiple is 2. Then lcm is applied to 2 and 6, yielding 6, and so on. It's almost identical to scanl1, except that it just returns the final result instead of a list of intermediate values (in other words, foldl1 = last . scanl1).

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

No explanation needed:

problem6 = (sum [1..100])^2 - (sum $ map (^2) [1..100])

And finally, the most trivial of them all (since we already wrote a prime generating function last time):

Problem 7:
What is the 10,001st prime number?

problem7 = primes!!10000 where
    primes = sieve [2..] where
        sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

Of course, this may take a while to execute, since we are using a rather simplistic algorithm. It's certainly faster than our Perl approach, though!

Leave a Reply

Theme: Esquire by Matthew Buchanan.