Haskell: Project Euler 1-5

According to it’s website

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I chose Haskell to solve the first 5 problems because

The answers are left out (no spoilers) although they can easily be obtained by running the code in ghci.

 1. Multiples of 3 and 5

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.

The important thing to notice here is that “multiples of 3 or 5” is analogous to “numbers evenly divisible by 3 or 5”. We want to create a set of these numbers and then sum them up to get the correct answer.

It turns out creating a set of numbers satisfying certain conditions is very simple in Haskell.

set = [x | x <- [0..999], x `mod` 3 == 0 || x `mod` 5 == 0]
-- set = [0, 3, 5, 6, 9, 10, ..., 999]

Now all that needs to be done is sum set.

 2. Even Fibonacci numbers

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 4000000, find the sum of the even-valued terms.

First we have to find a way to generate a Fibonacci sequence. Thanks to Haskell’s ability to handle infinite lists we can do the following.

fibonacci = 1 : 2 : zipWith (+) fibonacci (tail fibonacci)
-- fibonacci = [1, 2, 3, 5, 8, 13, ..., ∞]

This can seem confusing for someone with no previous experience with Haskell, so below is a step-by-step visualisation of the algorithm in action.

-- for demonstration purposes x + y = zipWith (+) x y
fibonacci = [1, 2]
[1, 2] + [2] = [3]
fibonacci = [1, 2, 3]
[1, 2, 3] + [2, 3] = [3, 5]
fibonacci = [1, 2, 3, 5]
[1, 2, 3, 5] + [2, 3, 5] = [3, 5, 8]
fibonacci = [1, 2, 3, 5, 8]
-- repeat forever

With the infinite list of Fibonacci numbers we once again want to create a set of numbers which satisfy the conditions mentioned in the problem description.

set = [x | x <- (takeWhile (<=4000000) fibonacci), even x]
-- set = [2, 8, 34, 144, 610, 2584, ...]

Finally, to get the sum of the even-valued terms simply run sum set.

 3. Largest prime factor

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

What is the largest prime factor of the number 600851475143?

A prime number is by definition a natural number greater than 1 that has no positive divisors other than 1 and itself.

The solution that comes to mind when attempting to check if a number n is prime is to try and divide it with all numbers from 2 to n - 1. Though correct, it becomes ineffective if n is large.

The largest number we actually have to divide by to know if n is prime is the square root of n.

If we want to get the prime factors of 13195 we first check if it is evenly divisible by any number from 2 to the square root of itself. The first prime number we find is 5. Now we only have to check if it’s evenly divisible by any number from 2 to the square root of 2639 (13195 / 5 = 2639 because we already know 5 is a prime factor) and so on.

Below is my implementation of integer factorisation using Haskell guards.

factors :: Integer -> [Integer]
factors n
 | prime == []  = [n]
 | otherwise    = head prime : factors (n `div` head prime)
    where { 
        prime   = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. (isqrt n)];
        isqrt   = floor . sqrt . fromInteger
    }

Getting the largest prime factor is as easy as last $ factors 600851475143.

 4. Largest palindrome product

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.

The easiest way to check if a number is palindromic is to convert the number to a string, reverse it, convert it back to integer and compare it to the original.

palindrome n = n == (read $ reverse $ show n)

Then we create a set of all palindromic numbers made from the product of two 3-digit numbers.

set = [x * y | x <- [100..999], y <- [x..999], palindrome (x * y)]

Use maximum set to get the largest palindrome.

 5. Smallest multiple

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?

Using the factors method from earlier, we can create a set of factors for all numbers from 2 to 20.

factorList = map factors [2..20]
-- factorList = [[2], [3], [2, 2], [5], ..., [2, 2, 5]]

First off, we need to remove all non-uniform lists (e.g. [2, 2, 5] or [2, 3]) from the set.

set = filter (\(x:xs) -> xs == (replicate (length xs) x)) factorList
-- set = [[2], [3], [2, 2], [5], ..., [19]]

Then we need to remove duplicates. By that I mean if we have [2, 2, 2], [2, 2] and [2] we must remove the two latter since they are factors of the former.

This is where I got stuck and had to resort to help from StackOverflow.

The solution, thanks to ThreeFx, was to group the lists with the same head together and then filter out the ones with the shortest length.

import Data.List
import Data.Function

f :: (Ord a) => [[a]] -> [[a]]
f = map (maximumBy (compare `on` length)) 
    . groupBy ((==) `on` head) 
    . sortBy (compare `on` head)

Lastly, multiply everything together using product $ map product $ f set.

 Remarks

Learn you a Haskell is the perfect book for learning the basics of Haskell and has helped me a lot while solving these problems. If you don’t want to buy it you should check out their online version.

Follow me on twitter to keep up to date or to post comments and criticism.

The second part of this series can be found here.

 
103
Kudos
 
103
Kudos

Now read this

Raspberry Pi: yts.re python wrapper

A YIFY-Torrents API wrapper written in python 3.41, which combined with btstream from my previous post serves as a command-line media center. Dependencies Python 3.41 (included by default) btstream (for torrent streaming) Usage Options... Continue →