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$?

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