Project Euler

Project Euler #12

Project Euler # 12 – Highly divisible triangular numbers

I am taking a bit of a jump here and moving right on to # 12. The reason is that this question came up on Stackoverflow, and so I was playing with it anyways and it got me really interested in testing out the performance of generators vs. a simple calculation

In this Project Euler Challenge we have to consider the factors of triangular numbers. Triangular numbers are the sum of a subset of natural numbers. For example, the first 6 triangular numbers are:

triangular number : {1, 3, 6, 10, 15, 21, ...}
{1} => 1
{1 + 2} => 3
{1 + 2 + 3} => 6
{1 + 2 + 3 + 4} => 10
{1 + 2 + 3 + 4 + 5} = 15
{ 1 + 2 + 3 + 4 + 5 + 6} = 21
... and so on

My first thought was to take a recursive approach. But then, we have discussed the limitations of recursion in Python. So I thought, “great opportunity to use generators!”. The basic algorithm is laid out below:

1: generator function to create the sequence of triangular numbers with a suitably high limit.
2: get_factors() function to find all the factors of any given (triangular) number
3: return the total number of factors

The nice thing is that this ran, and ran relatively quickly (< 10 secs) to give the correct answer. But I was intrigued, could I do better with a direct calculation for any given triangular number?

For anyone who likes kakuro puzzles, this will be a very familiar pattern 🙂 It is known as the ‘sum-of-all-integers’ and is defined as:

\sum_{n=0}^{i }\frac{n(n + 1)}{2}

So I substituted this in place of the generator function in step 1 to test its performance. Turns out, that the direct calculation is approx. 30 % faster on average (for both a small order of factors, or a high order of factors). The results from a profile test are below:

Using a generator function:

$ python3 -m cProfile euler12.py
842161320
         1423265 function calls in 116.281 seconds

Using a direct calculation:

$ python3 -m cProfile euler12.py
842161320
         1382224 function calls in 90.209 seconds

I’m intrigued. Instinctively, I thought that they would have been roughly the same speed. My reasoning being that a generator takes full advantage of lazy evaluation, so there should be little additional overhead. Of course, this made me look closer at implementation of the generator. I had implemented this to explicitly sum from 1..n and I reason that this calculation becomes quite intensive for large values of n. Contrast this to the sum of all integers, and it avoids the need to explicitly sum over a range. Well that explains the improvement!

I wonder, if I memoized the previous triangular number could I make the generator equally as fast (or faster!) than the calculation for sum of all integers? I will experiment with this one day.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s