Project Euler Problem 45 Solution

Question

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

\begin{aligned} \text{Triangle} & T_n=\frac{n(n+1)}{2} & 1, 3, 6, 10, 15, ... \\ \text{Pentagonal} & P_n=\frac{n(3n-1)}{2} & 1, 5, 12, 22, 35, ... \\ \text{Hexagonal} & H_n=n(2n-1) & 1, 6, 15, 28, 45, ... \end{aligned}

It can be verified that T_{285} = P_{165} = H_{143} = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Haskell

import qualified Data.Set as Set

triangles :: [Int]
triangles = [(n*(n + 1)) `quot` 2 | n <- [1..]]

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

hexagonals :: [Int]
hexagonals = [n*(2*n - 1) | n <- [1..100000]]

candidates :: [Int]
candidates = dropWhile (<= 40755) [t | t <- triangles, isPentagonal t, isHexagonal t]
    where isPentagonal = (`Set.member` Set.fromList pentagonals)
          isHexagonal = (`Set.member` Set.fromList hexagonals)

main :: IO ()
main = print $ head candidates

$ ghc -O2 -o tri-pen-hex tri-pen-hex.hs
$ time ./tri-pen-hex
real   0m0.036s
user   0m0.036s
sys    0m0.000s

Python

#!/usr/bin/env python
def triangle(n):
    return n*(n+1)//2

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

def hexagonal(n):
    return n*(2*n-1)

def main():
    p = set(pentagonal(n) for n in range(100000))
    h = set(hexagonal(n) for n in range(100000))
    for n in range(100000):
        t = triangle(n)
        if t in p and t in h and t > 40755:
            print(t)

if __name__ == "__main__":
    main()

$ time python3 tri-pen-hex.py
real   0m0.123s
user   0m0.123s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
require 'set'
p = (1..100000).map { |n| n*(3*n-1)/2 }.to_set
h = (1..100000).map { |n| n*(2*n-1) }.to_set
puts (286..100000).map { |n| n*(n+1)/2 }.detect { |t|
  p.include?(t) and h.include?(t)
}

$ time ruby tri-pen-hex.rb
real   0m0.110s
user   0m0.102s
sys    0m0.008s