## 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:

$\displaystyle 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.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
```

Questions? Comments? Send me an email: [email protected]