The problem itself:
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:| Triangle | Tn=n(n+1)/2 | 1, 3, 6, 10, 15, ... |
| Pentagonal | Pn=n(3n-1)/2 | 1, 5, 12, 22, 35, ... |
| Hexagonal | Hn=n(2n-1) | 1, 6, 15, 28, 45, ... |
Find the next triangle number that is also pentagonal and hexagonal.
Note: link to the problem @ ProjectEuler.net
How to solve the problem:
Brute-forcing the solution isn't fast, in fact it's incredibely slow, even with the some loop-optimizations. I speak from personal experience. :)However, if we read about these numbers (triangle, pentagonal and hexagonal) we see some interesting properties that we can exploit.
We see that triangle numbers are super-set of the hexagonal numbers. Or put simply - every hexagonal is triangle number, even more, every odd triangle number is a hexagonal number. With this conslusion, we should only test if pentagonal number match given hexagonal number, because we already know that hexagonal number is also a triangle one.
We can easily see the connection between the indices of the triangle and hexagonal numbers - T(i) = H(i/2 + 1) or H(i) = T(2i - 1), where "i" is the index.
Because we need the next number that is triangle, pentagonal and hexagonal we could start from the index 144, because we don't care about previous solutions.
So now we want to start from the index 144, again brute-forcing the solution, but this time we have linear complexity - O(n).
The solution itself:
We have a function that calculates the hexagonal number for given index (nothing fancy here):static public long CalculateHexagonalNumber(int index)
{
long result = 2 * index * index - index;
return result;
}
Now we need to test if a given hexagonal number is also pentagonal (well, more info @ Wikipedia how we can do that.
Here is the C# implmentation:
static public bool IsPentagonalNumber(int number)
{
double pentagonalNumberTest = (Math.Sqrt((double)24 * number + 1) + 1) / 6;
return pentagonalNumberTest == ((int)pentagonalNumberTest);
}
Here is the Main() function, which prints the next number that satisfy our condition and breaks:
static void Main(string[] args)
{
int i = 144;
while(true)
{
int hexagonalNumber = CalculateHexagonalNumber(i);
if(IsPentagonalNumber(hexagonalNumber))
{
Console.WriteLine(hexagonalNumber);
break;
}
i++;
}
}
