One of the more semi-interesting things I’ve found about Project Euler is the odd spikes in difficulty. When doing problems sequentially is can be hard to determine at a glance whether the next problem will even be comperable to the one prior. That being said problem 45 is not one of these peaks.

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle $$T_n=n(n+1)/2 \quad 1, 3, 6, 10, 15, ... $$
Pentagonal $$P_n=n(3\cdot n−1)/2 \quad 1, 5, 12, 22, 35, ...$$
Hexagonal $$H_n=n(2\cdot n−1) \quad 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.

This is a simple problem, a very simple problem. Even the most naive solutions should finish well under the prescribed 1 minute limit for Project Euler problems ( so long as the writer is not acting deliberately obtuse ). However the optimization are interesting enough to begin a blog over so let’s begin.

At first it seems as though the only way to find integers solutions is to simply generate triangular, pentagonal and hexagonal numbers and then wait untill the three of them match. While this resembles the eventual solution one oberservation will save your poor computer some cycles.

Notice, that the lists Triangle and Hexagonal numbers above are similar. In fact it appears that every other Triangle number appears in the Hexagonal list. Is this just a mathematical coinsidence? My favorite way to find out is using induction. Induction can be used to prove that in some sets of numbers if you find a relation that works in a few cases it will work for the entire rest of the set. Integers happens to be one of these sets, and spoilers this happens to be one of those relations.

The first step of induction is to prove that our relationship is valid anywhere which we have already achived by observation. We then state the relation in the form of an equation and show that if the relation holds for $$n$$ it will hold for $$n + 1$$. We begin this process thusly,

$$ \frac{m ( m + 1 ) }{2} = n(2\cdot n−1)$$

With $$n$$ being related to $$m$$ in some way. This relationship is important so it deserves an explanation. While terms like “every other” make good intutitive sense to humans it can be difficult to translate that sort of term into something that can expressed mathematically. Instead try to see $$m$$ and $$n$$’s own relationship for it is just as important as the one stated previously. If we were to line up the Triangle and Hexagonal numbers with similar numbers together and non-matching ones between.

$$ 1,\>\>\>\>\>3, \>\>\>\>\>\>\>5,\>\>\>\>\>\>\>\>\>7, ...$$
$$ 1, 3, 6, 10, 15, 21, 28, ... $$
$$ 1,\>\>\>\>\>6, \>\>\>\>\>\>\>15,\>\>\>\>\>\>\>28, ...$$

It is now easy to state that the relation is, “Every odd numbered Triangluar number, is a Hexagonal number”. And the way to represent that in our case is $$ 2n + 1 = m $$. From here a simple algebraic transformation will suffice.

$$ \frac{m ( m + 1 ) }{2} \rightarrow \frac{ (2n + 1) ( (2n + 1) + 1 ) }{2} \rightarrow 2n^2 + 3n + 1 ?$$

Well that doesn’t look right… Let us reexamine the odd number relation. Notice that the first number in our counting scheme is ill defined or at least poorly matched up. And that the smallest odd number ( $$1$$ ) does not match with our definition of the smallest input to that equation ( $$0$$ ). This can be easily fixed however by sliding ourselves over by 1.

$$ 2(n-1)^2 + 3(n - 1) + 1 \rightarrow 2n^2 - n = n(2\cdot n−1)$$

Using this bit of information we can just skip checking Triangle numbers since every Hexagonal number is one. This simplification cleans up the code a bit and makes an easy problem just a bit easier.

To view my solution on github click here