Project Euler Problem 44 Solution

Question

Pentagonal numbers are generated by the formula, P_n=\frac{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 is pentagonal and D = |P_k - P_j| is minimised; what is the value of D?

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.164s
user   0m0.156s
sys    0m0.008s

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.772s
user   0m0.771s
sys    0m0.000s

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.784s
user   0m0.784s
sys    0m0.000s