Project Euler Problem 44 Solution

Question

Pentagonal numbers are generated by the formula, Pn=n(3n1)2P_n=\frac{n(3n-1)}{2}. The first ten pentagonal numbers are:

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

It can be seen that P4+P7=22+70=92=P8P_4 + P_7 = 22 + 70 = 92 = P_8. However, their difference, 7022=4870 - 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, PjP_j and PkP_k, for which their sum and difference is pentagonal and D=PkPjD = |P_k - P_j| is minimised; what is the value of DD?

Haskell

import qualified Data.Set as Set

pentagonals :: [Int]
pentagonals = [(n*(3*n - 1)) `quot` 2 | n <- [1..3000]]

isPentagonal :: Int -> Bool
isPentagonal n = Set.member n (Set.fromList pentagonals)

candidates :: [Int]
candidates = [j - k | j <- pentagonals, k <- takeWhile (< j) pentagonals,
                      isPentagonal (j - k), isPentagonal (j + k)]

main :: IO ()
main = print $ head candidates
$ ghc -O2 -o pentagonal-nums pentagonal-nums.hs
$ time ./pentagonal-nums
real   0m0.156s
user   0m0.140s
sys    0m0.000s

Python

#!/usr/bin/env python
from itertools import *
from math import *
from operator import *

def pentagonal(n):
    return n*(3*n-1)//2

def main():
    pentagonals = set(pentagonal(n) for n in range(1, 3000))
    c = combinations(pentagonals, 2)
    for p in c:
        if add(*p) in pentagonals and abs(sub(*p)) in pentagonals:
            print(abs(sub(*p)))

if __name__ == "__main__":
    main()
$ time python3 pentagonal-nums.py
real   0m0.694s
user   0m0.680s
sys    0m0.004s

Ruby

#!/usr/bin/env ruby
require 'set'
pentagonals = (1..3000).map { |n| n*(3*n-1)/2 }.to_set
puts pentagonals.to_a.combination(2).select { |a,b|
  pentagonals.include?(a+b) && pentagonals.include?((a-b).abs)
}.map { |a,b| (a-b).abs }.min
$ time ruby pentagonal-nums.rb
real   0m0.821s
user   0m0.816s
sys    0m0.004s