Euler Problem 45 asks:
‘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.
‘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.
If we rearrange the Pentagonal formula, we can get P(n)=n(3n-1)/2 as
- 1.5*n^2 – 0.5n – P(n) = 0 with -P(n) = -T(n).
Similarly for the Hexagonal formula, we can get H(n)=n(2n-1) as
- 2*n^2 – 1*n – H(n) = 0 with -H(n) = -T(n).
Flashing back to high school algebra, all we need to do is determine the roots of those quadratic equations (Remember minus b plus or minus the square root of b squared minus 4ac, all over 2a?) If the two equations have integer roots, then we have found a number that is Triangular, Pentagonal, and Hexagonal. Here is my code. It tests for for pentagonal roots first, and only those that pass are tested for hexagonal roots. I didn’t know how far to test, so I picked to 100,000.
Sub Problem_045()
Dim Tn As Double ‘Triangular number
Dim n_p As Double ‘pentagonal “root”
Dim n_h As Double ‘hexagonal “root”
Dim n_t As Double ‘triangle “root”
Dim T As Single
Dim IsTest As Boolean
Dim Least As Double
Dim Most As Double
Dim Answer As Long
T = Timer
IsTest = False
If IsTest Then
Least = 284
Most = 287
Else
Least = 286
Most = 100000
End If
For n_t = Least To Most
Tn = n_t * (n_t + 1) / 2
n_p = QuadSoln(1.5, -0.5, -Tn)
If n_p = Int(n_p) Then
n_h = QuadSoln(2, -1, -Tn)
If n_h = Int(n_h) Then
Answer = Tn
Exit For
End If
End If
Next n_t
Debug.Print n_t; n_p; n_h
Debug.Print Answer; ” Time:”; Timer – T
End Sub
Function QuadSoln(A As Double, b As Double, c As Double) As Double
‘ Returns with positive square root
Dim X As Double
X = (-b + Sqr(b ^ 2 – (4 * A * c))) / (2 * A)
QuadSoln = X
End Function
Dim Tn As Double ‘Triangular number
Dim n_p As Double ‘pentagonal “root”
Dim n_h As Double ‘hexagonal “root”
Dim n_t As Double ‘triangle “root”
Dim T As Single
Dim IsTest As Boolean
Dim Least As Double
Dim Most As Double
Dim Answer As Long
T = Timer
IsTest = False
If IsTest Then
Least = 284
Most = 287
Else
Least = 286
Most = 100000
End If
For n_t = Least To Most
Tn = n_t * (n_t + 1) / 2
n_p = QuadSoln(1.5, -0.5, -Tn)
If n_p = Int(n_p) Then
n_h = QuadSoln(2, -1, -Tn)
If n_h = Int(n_h) Then
Answer = Tn
Exit For
End If
End If
Next n_t
Debug.Print n_t; n_p; n_h
Debug.Print Answer; ” Time:”; Timer – T
End Sub
Function QuadSoln(A As Double, b As Double, c As Double) As Double
‘ Returns with positive square root
Dim X As Double
X = (-b + Sqr(b ^ 2 – (4 * A * c))) / (2 * A)
QuadSoln = X
End Function
It runs in a few hundredths of a second.
…mrt
I used your quadratic hint, and set up an entirely spreadsheet based solution (also noting that all hexagonal numbers are triangular numbers, H(n) = T(2n-1))
The procedure was:
Enter 143 in cell C2
in D2: =+C2*(C2*2-1)
C4: 1.5
C5: -0.5
C:6 -D2
C:8 =(-C5+(C5^2-4*C4*C6)^0.5)/(2*C4) (the pentagonal number quadratic solution)
Go to calculation settings, and allow iterative formulas and set iterations to 1000
Then back to C2 and enter a circular reference:
=IF(C1=0,144,IF(INT(C8)=C8,0,1)+C2)
Enter 1 in cell C1 then press F9 until the value in C2 stops changing.
It takes 28 steps (29 to verify that you have reached a solution), so not quick, but quick to set up and verify.
The number in D2 is the answer.