Euler Problem 45

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.

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

It runs in a few hundredths of a second.

…mrt

Posted in Uncategorized

One thought on “Euler Problem 45

  1. 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.


Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.