Euler Solution 44

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 44

Find the pair of pentagonal numbers whose sum and difference is pentagonal.

Haskell by SanguineV

{- Generate the pentagonal numbers lazily. -}
pents :: [Integer]
pents = 1:pents'
  where
    pents' = zipWith (+) pents [4,7..]

{- Determine if an element is in a sorted list. -}
elem' :: Integer -> [Integer] -> Bool
elem' n [] = False
elem' n (x:xs) | n == x = True
elem' n (x:xs) | x > n = False
elem' n (x:xs) = elem' n xs

{- Given two elements see if they both occur in a sorted list -}
elem2 :: Integer -> Integer -> [Integer] -> Bool
elem2 n m [] = False
elem2 n m (x:xs) | n == x = elem' m (x:xs)
elem2 n m (x:xs) | x > n = False
elem2 n m (x:xs) = elem2 n m xs

{- Given a number, find if it can be paired with a pentagonal so that
 - their sum and difference is also pentagonal. -}
check :: Integer -> Integer
check n = inner pents
  where
    inner :: [Integer] -> Integer
    inner (x:xs) | x == n = -1
    inner (x:xs) | elem2 (n - x) (n + x) pents = x
    inner (x:xs) = inner xs

{- Find pairs of pentagonals whose sum and difference is pentagonal -}
findPairs :: [(Integer,Integer)]
findPairs = filter (\(x,y) -> y > 0) (map (\x -> (x,check x)) pents)

{- Find the first pair. -}
main = print (head findPairs)


Python by Althalus

Runtime: 350 Seconds

import time
start_time = time.time()

pentagonals = [n*(3*n-1)/2 for n in range(1,4001)]
p_min=None

for i in xrange(1,4000):
        p1 = pentagonals[i]
        for j in xrange(1,i):
                p2 = pentagonals[j]
                if (p1+p2) in pentagonals and abs(p1-p2) in pentagonals:
                        p_min = abs(p1-p2)
                        print p_min
                        break
        if p_min != None:
                break
run_time = time.time() - start_time
print run_time
Personal tools