044-pentagon-numbers.hs

#!/usr/bin/env runhaskell
{- https://projecteuler.net/problem=44
Problem 44
Pentagon numbers

Pentagonal numbers are generated by the formula, P_n=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P_4 + P_7 = 22 + 70 = 92 = P_8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference are pentagonal and D = |P_k − P_j| is minimised; what is the value of D?
-}

import qualified Data.Set as DS

-- This was a guess.  Turned out to be spot on.
upperBound :: Int
upperBound = 10000

pentagonals :: [Int]
pentagonals = map (\n -> n * (3 * n - 1) `quot` 2) [1..upperBound]

pentagonals' :: DS.Set Int
pentagonals' = DS.fromList pentagonals

main :: IO ()
main = print . head $ [q - p | p <- pentagonals, q <- filter (> p) pentagonals, DS.member (q - p) pentagonals', DS.member (q + p) pentagonals']