Haskell: Project Euler 6-10

Due to the popularity of my previous post on the same subject (click here if you haven’t read it), I decided to write a sequel tackling problems 6 through 10. It will be the last one about Project Euler and I hope this pair of articles will have served as a great starting point in learning Haskell.

I have been getting a lot of comments that the Project Euler website specifically asks not to post solutions online so I just want to clarify that the purpose of these articles is not denying you the epiphany of discovering your own solution. My intention is to spread the word about the combinatorial capabilities of Haskell and to introduce Project Euler to a broader audience, which I think is a perfect place to start learning any programming language.

With that out of the way, let’s solve some problems.

 6. Sum of squares

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.

The solution to this is very straightforward.

To find the sum of squares we square all numbers from 1 to 100 and then sum the resulting list.

To find the square of the sum we add all numbers from 1 to 100 and then square the answer.

sumOfSquares = sum $ map (^2) [1..100]
squareOfSum = sum [1..100] (^2)

The difference between them is the answer.

 7. 10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

For this one we will reuse the factors function from problem 3 to generate a list of prime numbers, but if you scroll down to problem 10 you will be introduced to a much more efficient algorithm.

I have pasted the factors function below for convenience.

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
    }

primes = concat $ filter (\(x:xs) -> null xs) $ map factors [2..]
-- primes = [2, 3, 5, 7, 11, ...]

What this does is selecting all factors with a length of 1. We could’ve used length instead of null in the filtering but length is a slow operation in Haskell.

The 10001st prime is primes !! 10001.

 8. Largest product in a series

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Let’s convert the number to a list where the elements are the digits of the number. Conveniently enough, the Data.List.Split module contains the function chunksOf (previously splitEvery), which takes two arguments – the size of the chunks and the list to split.

import Data.List.Split

number = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
chunks = map (\x -> read x :: Int) $ chunksOf 1 number
-- chunks = [7, 3, 1, 6, 7, ..., 0]

Now we need a function which generates a list of all possible adjacencies. It’s not enough to just split the list in thirteen chunks and compare the products, we also have to consider that the list can be split in thirteen different ways.

adj :: Int -> Int -> [a] -> [[a]]
adj n m xs
 | n >= m           = []
 | otherwise        = list ++ adj (n + 1) m (tail xs)
    where list      = filter (\x -> length x >= m) $ chunksOf m xs

Below is a demonstration of the function getting all possible combinations of two and three adjacent digits respectively.

adj 0 2 [1, 2, 3, 4, 5, 6]
[[1,2], [3,4], [5,6], [2,3], [4,5]]

adj 0 3 [1, 2, 3, 4, 5, 6]
[[1, 2, 3], [4, 5, 6], [2, 3, 4], [3, 4, 5]]

The biggest product of thirteen adjacent digits is obtained with maximum $ map product $ adj 0 13 chunks.

 9. Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Generating Pythagorean triplets in Haskell can be done with a simple list comprehension. The only thing we need is a helper function which can tell us if the root of a2 + b2 is a natural number.

We start sampling a from 1 to 1000. Since a < b we sample b from a to 1000. Then we calculate c from the two former, because we know a2 + b2 = c2. Lastly we filter the list to only contain triplets with a natural hypothenuse.

isRoot n = (sqrt n) == fromIntegral (round (sqrt n))

triplets = [(a, b, sqrt (a^2 + b^2))
           | a <- [1..1000], 
             b <- [a..1000],
             isRoot (a^2 + b^2)]
-- triplets = [(4.0, 3.0, 5.0), (8.0, 6.0, 10.0), (12.0, 5.0, 13.0), ...]

We now have a list which we can filter and map to get the product of the triplet with a sum of 1000.

map (\(a, b, c) -> a * b * c) $ filter (\(a, b, c) -> a + b + c == 1000) triplets

 10. Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

For the last problem the factors function we have used previously won’t do because it is too ineffective.

We need a sieve algorithm and luckily there is an ancient one named the Sieve of Eratosthenes which you probably have already stumbled upon in math class. It is, according to Wikipedia, “one of the most efficient ways to find all of the smaller primes (below 10 million or so)”.

The solution below is taken from literateprograms.org.

merge :: (Ord a) => [a] -> [a] -> [a]
merge xs@(x:xt) ys@(y:yt) = 
    case compare x y of
        LT -> x : (merge xt ys)
        EQ -> x : (merge xt yt)
        GT -> y : (merge xs yt)

diff :: (Ord a) => [a] -> [a] -> [a]
diff xs@(x:xt) ys@(y:yt) = 
    case compare x y of
        LT -> x : (diff xt ys)
        EQ -> diff xt yt
        GT -> diff xs yt

primes, nonprimes :: [Integer]
primes    = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes) 
nonprimes = foldr1 f $ map g $ tail primes
    where 
        f (x:xt) ys = x : (merge xt ys)
        g p         = [ n * p | n <- [p, p + 2 ..]]

Running sum $ takeWhile (<2000000) primes in ghci is a CPU-intensive task and it took 19.34 secs (timed with :set +s) to get the answer on my Macbook Air from 2012.

 
46
Kudos
 
46
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 →