Project Euler Problem #45

Problem #45 is yet another problem that involves figurate numbers. The problem reads:

Project Euler Problem 45: Triangular, pentagonal, and hexagonal
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, ...

It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.

My solution for this problem still probably falls into the category of brute force. However, it is slightly optimized over the naive interpretation of this problem. Here is my solution:

Solution #1: Brute Force Approach

We can observe that the nth Hexagonal number H_n = n(2n-1) can be rewritten as H_n = n(2n-1) = ((2n-1)(2n-1+1))/2 = T_(2n-1). Thus, every hexagonal number is also a triangular number. Therefore, it satisfies to find the next hexagonal number which is also a pentagonal number.

Thus, we iterate through the hexagonal numbers after H_143 and check each one for being a pentagonal number. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #45
 '''
 
 import time
 from math import sqrt
 from math import ceil
 
 def isPentagon(p):
     if(p==1):
         return True
     n = int(ceil(sqrt(2*p/3)))
     if(n*(3*n-1)/2 == p):
         return True
     return False
 
 def projectEulerProblemFortyFive(n):
     c = n+1
     while(True):
         if(isPentagon(c*(2*c-1))):
             return c*(2*c-1)
         c+=1
     return "HOW"
 
 start = time.time()
 print projectEulerProblemFortyFive(143)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1533776805
 --- 0.0135638713837 seconds ---
 
 for input of n = 143
 ''' 

While this solution is plenty efficient for this problem, I am sure that there must be a faster way to solve this problem. Many similar questions can be reduced to finding the solutions to a Pell Equation which can be done recursively. For instance, there is another Project Euler Problem which involves finding triangular numbers that are also square numbers, and that problem can be reduced to solving a Pell Equation. Because the formulas for pentagonal and hexagonal numbers are similar, it is likely that this problem can also be reduced to a Pell Equation. Alas, I am too lazy to solve this diophantine equation at the moment. I may come back to look for a more efficient solution at some point.

Thanks for reading! See you tomorrow.