This one doesn't warrant much discussion:

Problem 16:
What is the sum of the digits of the number 2^1000?

problem15 = sum . digits (2^1000) where
    digits n = map (\x -> read [x] :: Int) $ show n

Now for a much more interesting problem (deja vu?):

Problem 18:
Find the route from top to bottom with the largest sum in the triangle below:
   75
95 64
...

The triangle has 15 rows, so it's not unreasonable to simply brute force it. We could go about this by recursively asking a node in the triangle for the greater of its two child routes, e.g. a function like this:

maxRoute node
    | noChildren node = node
    | otherwise       = node + max (maxRoute leftChild) (maxRoute rightChild)

Unfortunately, we can't just pass a simple number to maxRoute, because there would be no way of determining what leftChild and rightChild are. I'm sure we could accomplish it using some sort of custom-defined type, but I haven't read up on defining custom types in Haskell. Instead, we'll just pass a pair of coordinates, which we can use to lookup the value in our triangle data structure (which will be a simple two-dimensional list):

maxRoute row col
    | row == 14 = tri !! row !! col
    | otherwise = tri !! row !! col + max left right where
        left  = maxRoute (row + 1) col
        right = maxRoute (row + 1) (col + 1)
    tri = [[75],
           [95,64],
           [17,47,82],
           ...

Then a simple problem18 = maxRoute 0 0 will compute the answer.

A more sophisticated approach would be to go "bottom up" instead of "top down," as in the brute force strategy. Starting at the bottom of the triangle, we reduce each parent-left-right set with parent = parent + max left right. Then we can simply fold this operation upwards until we reach the top of the triangle, at which point we'll have our answer.
This algorithm winds up looking a bit more complex, mainly because now we're processing two whole rows at a time instead of just three nodes. That means we'll be using zipWith3, which works as you might expect. The function we'll be zipping with is exactly what we described above, and the list arguments will be the parent row, the child row, and the child row with an offset of 1 (via tail).

problem18 = head $ foldr1 maxRow tri where
    maxRow pRow cRow = zipWith3 reduce pRow cRow (tail cRow)
    reduce parent left right = parent + max left right
    tri = [[75],
           [95,64],
           [17,47,82],
           ...

Note that we have to use foldr instead of the usual foldl since we're starting at the bottom.

Let's finish off this post with another easy one:

Problem 20:
Find the sum of the digits in the number 100!

This is as easy as:

problem20 = sum . digits $ factorial 100

...except that we haven't defined a factorial function yet. In an earlier post, we covered a few methods of implementing a factorial function in Perl. As it turns out, it's even more fun in Haskell (in fact, there's an entire web page devoted to it). Let's cover just a few:

fac 0 = 1
fac n = n * fac (n - 1)

fac n = product [1..n] -- essentially syntactic sugar for:
fac n = foldl1 (*) [1..n]

facs = scanl (*) 1 [1..]
fac n = facs !! n

Efficiency-wise, it doesn't make much difference which implementation you choose, but if you're going to computing lots of values, the memoized version (that last one) is probably your best bet. Memoization means that before carrying out the factorial computation, we first check to see if we already know the answer. Then we can just use that instead of recalculating it from scratch. In most languages, a memoized implementation of factorial will be quite a bit more verbose, but it comes almost for free in Haskell because of the lazy nature of infinite lists. fac is just looking up a value in facs, and when we ask facs for an entry it hasn't calculated yet, it carries out the necessary computation. So asking for fac 10000 might take a bit, but after that you'll be able to look up any factorial under 10000 almost instantly. Pretty cool!

First post in months! Now that school is done with I should be able to bang out some more of these. Let's get right down to it then, shall we?

Problem 13:
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers:
37107287533902102798797998220837590246510135740250, 46376937677490009712648124896970078050417018260538, 74324986199524741059474233309513058123726617309629 ...

Straightforward enough. Summing lists of numbers is nothing new to us, and it turns out that we only need the first 11 digits or so to get the accuracy we need:

problem13 = take 10 . show . sum $ numbers where
    numbers = [37107287533, 46376937677, 74324986199, ... ]

Now for a much more interesting problem:

Problem 14:
A Collatz chain is an iterative sequence that obeys the following rules:
  -  n → n/2 (if n is even)
  -  n → 3n + 1 (if n is odd)
  -  The sequence ends when n = 1
Which starting number, under one million, produces the longest Collatz chain?

What is the best way to approach this problem? One method would be to write a function that produces the next value in the Collatz chain. We could then use iterate to generate the full sequence:

nextCollatz n
    | even n = n `div` 2
    | odd n  = 3*n + 1

collatzChain n = takeWhile (/= 1) $ iterate nextCollatz n

and use a list comprehension to obtain the longest chain:

problem14 = maximum [ (length (collatzChain x), x) | x <- [1..1000000] ]

Alternatively, we could rewrite our nextCollatz function to do the list-generating itself. Then we wouldn't need a separate chaining function to string the values together:

collatzChain 1 = [1]
collatzChain n
    | even n = n : collatzChain (n `div` 2)
    | odd n  = n : collatzChain (3*n + 1)

However, it turns out that the former version runs just a hair faster.
Next problem:

Problem 15:
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?

Oh boy. This is an interesting one. If you're a functional programmer, your first instinct should be to model this as a recursive problem. At each intersection, the number of paths to the bottom right corner is just the sum of the value below and the value to the right, so we can work backwards to find the total sum at the top left corner. On the other hand, the more mathematically inclined may notice that the value at each intersection can be computed without the need for recursion, using the formula factorial n `div` (factorial n/2)^2.
If you are a true Haskell wizard, though, there is another solution:

problem15 = (iterate (scanl1 (+)) (repeat 1)) !! 20 !! 20

It should blow your mind that we can compress this problem down to essentially just a scanl and an iterate. Note the array indices: we are actually constructing an infinite grid of route numbers and then extracting the value for a 20x20 grid. We can shed some light on how it works by examining just the subset of the infinite grid that we're interested in:

take 20 $ iterate (scanl1 (+)) $ take 20 (repeat 1)
[1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
[1, 2, 3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91,105,120,136,153,171,190,210]
...

The iterate and scanl1 combine to implement the "sum" that we discussed earlier. In a way, you can think of scanl1 as adding the left value, and iterate as adding the above value. Super cool!

Let's do two easy problems and then a harder one.

Problem 9:
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a^2 + b^2 = c^2. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

We can accomplish this by using a simple list comprehension to enumerate all the Pythagorean triplets that fit these constraints:

[ [a,b,c] | a <- [1..999], b <- [1..a], let c = 1000 - a - b, a^2 + b^2 == c^2]

Since we know that a + b + c = 1000, we can define c in terms of a and b. We can also avoid doing excessive computation by taking b from the range [1..a] instead of [1..999]. Once we have our set of three numbers, it's a simple matter of multiplying them together to get the final answer:

problem9 = product $ head [ [a,b,c] | a <- [1..999], b <- [1..a], let c = 1000 - a - b, a^2 + b^2 == c^2]

The next one is even easier:

Problem 10:
Find the sum of all the primes below two million.

We already covered a method for generating primes, so our solution is just:

problem10 = sum $ takeWhile (<2000000) primes

And now for a slightly trickier problem:

Problem 12:
What is the value of the first triangle number to have over five hundred divisors?

(Yes, I skipped over problem 11. I haven't found a good way of doing it yet.)
The triangular numbers can be easily generated using scanl1. To find the number of factors of a number, we use the following trick: find the prime factorization of the number, add 1 to each exponent in the factorization, then multiply the exponents together. This makes sense because any factor must be a combination of prime factors. So really you're evaluating all the possible combinations of exponents in the prime factorization, with each term pⁿ having n+1 possible exponent states (since n = 0 is also a valid state).

The only real challenge here is to find a way get the exponents of each prime factor. Recall that our primeFactors function returns a unique list of prime numbers that multiply together to form the original number. So one way we can get the exponent of each number is to simply count the number of times a number appears in the list. To accomplish this, we will use a new function called span, which takes a list and a comparison as arguments and returns a tuple.

Have we covered tuples yet? A tuple is just a pair of two values. The reason they're useful is that the values can have different types, which isn't true of a list. In this case, span looks for the first element in the list that does not satisfy the comparison function, and splits the list in two at that element. The first part goes in the first value of the tuple, and the latter part goes to the second value.

Normally we could not use span to count the number of occurrences of an element in a list, but this is a special case. Since the way we defined primeFactors means that its output is in ascending order, the repeated prime factors will already be grouped together. So all we have to do is get the length of the first part, then call our function on the latter part to get the next value. Here's the implementation:

getExp [] = []
getExp xs = length (fst spanTuple) : getExp (snd spanTuple) where
    spanTuple = span (== (head xs)) xs

As you might have guessed, fst and snd are simply functions that let us access the first and second values in a tuple. Also note that we must define the base case getExp []; otherwise our function would never terminate.

Now that we have our list of exponents, it is a simple matter to add 1 to them and take the product. Then we simply run this calculation on each triangular number and perform a list comprehension:

problem12 = head [x | x <- triangles, numFactors x > 500] where
    triangles = scanl1 (+) [1..]
    numFactors = product . getExp . primeFactors
    getExp [] = []
    getExp xs = length (fst spanTuple) : getExp (snd spanTuple) where
        spanTuple = span (== (head xs)) xs

Note that we have defined numFactors in pointfree style here.

Originally I used group to count the number of occurrences, but it seemed unnecessarily verbose. Fortunately, Haskell makes it easy to define custom-tailored functions like getExp inline, right where you need them.