Project Euler: Problem 12

It’s time once again for a favorite blog theme, The Project Euler post. This time around I am answering problem twelve. The website states the problem as:

1
2
3
4
5
The sequence of triangle numbers is generated by adding the natural
numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 =
28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1

3: 1,3

6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

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

To spice things up I decided to use a language I haven't used for these in a while, Perl. I also included the usual suspects: Python and Haskell. So, here's the Perl code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#!/usr/bin/perl

use strict;
use warnings;

my $index = 7;
my $total = 28;
my $divisors = 0;

sub divisors
{
    my ($number) = @_;
    my $sq_n = sqrt($number);
    my $i = 1;
    my $t = 0;

    while ($i <= $sq_n)
    {
        $t += 2 unless ($number % $i);

        $i += 1;
    }

    return $t;
}

while( divisors($total) <= 500)
{
    $index += 1;
    $total += $index;
}

print "$total\n";

Nothing really new or interesting to mention in this code. Here is the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#!/usr/bin/python

"""
solution for problem 12 in python.
"""
import math

def get_divisors(number):
    tlist = []
    for x in xrange(2, int(math.sqrt(number))):
        d,r = divmod(number,x)
        if r == 0:
            tlist.append(x)
            tlist.append(d)

    return len([1, number] + tlist)

def triangle_nums():
    iterator = 7
    num = 28

    while True:
        yield num
        iterator += 1
        num += iterator

if __name__ == "__main__":
    tn = triangle_nums()
    for t in tn:
        tl = get_divisors(t)
        if tl > 500:
            print "num: %d\ncount: %d" % (t,tl)
            break

Pretty standard stuff for the most part. I think the only non-standard thing worth mentioning is the infinite triangle number generator. This took a little finangling, but I got it to work in the end.

Here is the Haskell code:

1
2
3
4
5
6
7
8
9
module Main where

get_div_len number = foldl1 (+) [2 | x <- [1..x], number `mod` x == 0]
    where x = round . sqrt $ fromInteger number

main :: IO()
main = do
  print . head $ dropWhile (\x -> fst x <= 499) (map (\x -> (get_div_len x ,x)) xs)
  where xs = map (\y -> sum [1..y]) [7..]

After creating these solutions, I did my usual, highly accurate, testing method to determine the speed of the computation. I was surprised by my results:

Perl: 12.462s

Python: 17.783s

Haskell (compiled): 13.877s

Normally the Haskell solution would be significantly faster, and I have a theory as to why the Haskell times are so close. In Perl and Python I’m doing two additions – one for the increase of the index number and another to increase the total number. In Haskell I’m doing 1 + n additions; the first is to increase the index, and the remaining additions (n) are those used to calculate the sum of all the numbers between (and including) 1 and the index. As the index variable gets larger, that calculation takes more and more time to perform. I would write this up as suboptimal. After spending some time traveling “the tubes,” I discovered the State Monad, which is the reason why this blog post took me so long. I had to spend a week going through random blogs, skimming books, and beating my head against a wall (more than usual) to figure this out.

Quick diversion, for those of you who do not know what the State Monad is, let me take a moment to to try and explain what it is and why it’s important in this context. Those of us that come from an imperative language (I am one of you in this regard) are used to being able to do a simple addition such as (in pseudo code):

1
2
Variable = 2
Variable = variable + 3 or Variable += 3

We can’t do this in Haskell; instead we have to create a new variable name for each new variable assignment. We could also create a function that recursively goes forward, generating the next number in the sequence and bringing our needed variables with us before going deeper down the recursion rabbit hole. With the State Monad, however, we can write our function in such a way that the necessary variables are implicitly passed. Take a look at the new solution to see what I mean:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
{-# LANGUAGE BangPatterns, UnboxedTuples #-}
module Main where

import Control.Monad
import Control.Monad.State

type MyState = (Int, Int)
s0 = (7, 28)

tick = do
    (n,o) <- get
    let divs = getDivLen (n,o)
    if divs <= 500
        then do
            let n' = n + 1
            let o' = o + n'
            put (n', o')
            tick
        else
            return o

getDivLen :: MyState -> Int
getDivLen (!n, !o) = foldl1 (+) [2 | x <- [1..x], o `mod` x == 0]
    where x = round . sqrt $ fromIntegral o

main :: IO ()
main = print $ evalState tick s0

The tick function does not have any input parameters. All the information that the function needs comes from the “get” function call, which grabs the current state from the State Monad. If the tick function does not find a number of divisors greater than five hundred, it inserts new values back into the State Monad, and goes down to the next level of recursion.

It took me a long time to figure this out, mostly because of the lack of examples on the internet concerning the State Monad. If I wanted to create a random number generator I would have been set, but sadly I just wanted to create something that would hold a tuple of numbers and increment them accordingly. So I highly modified one of the “random number generator” examples.

My “highly accurate” speed test results for the new version is:

Haskell (compiled): 2.664s

which is a vast improvement (> 11s) over the previous implementation.

While a Project Euler problem may not have been the best way to learn about using the State Monad, I'm glad I stumbled upon it. I hope that it can be used as an example for others if they want to learn how to use the this particular monad to create things other than pseudo-random number generators.

One last thing – some of the brighter crayons in the box (which is most of you, based on the level of comments that I receive) might have noticed that I skipped problem 11. There is a simple response to that. I still haven’t solved it.

Comments !

social