Project Euler

One of my new favorite hobbies / time sinks is Project Euler. Simply stated: a few hundred programming problems that are somewhat math-related. They are sort of like brain teasers for programming nerds.

One of my favorite features is that most of the problems have many ways to approach it. Usually there is a terrible way, such as brute force, and then there is some elegant way. Or, maybe, the elegant way is just clever uses of data structures.

For example, here is problem 45:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae: Triangle: T(n)=n(n+1)/2    1, 3, 6, 10, 15, ... Pentagonal: P(n)=n(3n−1)/2    1, 5, 12, 22, 35, ... Hexagonal: H(n)=n(2n−1)    1, 6, 15, 28, 45, ... It can be verified that T(285) = P(165) = H(143) = 40755. Find the next triangle number that is also pentagonal and hexagonal.

When I first wrote this up in Python, I did it in a naive manner: simply constructing giant lists of each of the numbers and checking intersections.

Let's put it this way. The next intersection does not happen for a long, long time. Doing it this way takes about 6.5 minutes to run on my machine. You can just feel the quadratic nature of the running time.

There is actually a slightly more clever way to do it in linear time, which lowers this to about 0.1 seconds to run. See if you can find it.