Yacoby's Wanderings | Problem 45

Project Euler - Problem 45

Problem 45 is defined as:

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

$T(t) = \frac{t(t+1)}{2}\\P(p) =\frac{p(3p-1)}{2}\\H(h) = h(2h-1)$

It can be verified that:

Find the next triangle number that is also pentagonal and hexagonal.

The first thing to notice is that H is a subset of T (proof):

$\frac{t(t + 1)}{2} = h(2h - 1)\\t_h = 2h - 1\\T(t_h) = T(\frac{h(h+1)}{2}) = (2h-1)\frac{(2h-1)+1}{2} = (2h-1)\frac{2h}{2} = h(2h-1) = H$

Which means that T can be ignored

As p has to be a natural number, all we need to do if find the first value of h for which p_his natural, subject to the constraint that h is also natural and h > 143

$\frac{p(3p - 1 )}{2} = h(2h - 1)\\p_h = (\frac{1}{6})( \sqrt{ 48h^2 - 24h + 1 } + 1 )$

Using the above, the solution in Haskell (Running time about 100ms) is as follows:

isInteger :: (RealFrac a) => a -> Bool
isInteger f = ( fromInteger $ round f ) == f

--Same as a triangle number
sumTo n = (n*(n + 1)) `div` 2


solution45 :: Integer
solution45 = sumTo $ round $ head [ hexToTri h | h <- [144..], isInteger ( hexToPen h ) ]
	where
		hexToPen :: Double -> Double
		hexToPen h = (1/6::Double) * ( sqrt( (48*(h^2)) - (24*h) + 1 ) + 1 )

		hexToTri :: (Num a) => a -> a
		hexToTri h = 2*h - 1

Although my solution worked fine, it wasn't a very good method of solving it. The best method I saw is at MathWorld, which was far more elegant.