Euler Solution 146

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 146

Find the sum of all n in the range 1..150000000 where n2+1, n2+3, n2+7, n2+9, n2+13, n227 are all prime.

Haskell by SanguineV

Runtime: long (see below)

{- A fairly naive test for primality of a list of numbers. -}
isPrimeL :: [Integer] -> Bool
isPrimeL l = inner 3
  where
    lim = floor (sqrt (fromIntegral (maximum l)))
    inner :: Integer -> Bool
    inner i | i > lim = True
    inner i = (and (map (\x -> gcd i x == 1) l)) && inner (i + 2)

{- Calculate the sum of all "n"s from 1 to the limit where:
 - n^2+1, n^2+3, n^2+7, n^2+9, n^2+13, n^2+27 are all prime.
 - A couple of optimisations:
 - 1. n^2 must be divisible by 10, thus n must be 10*k for some k
 - 2. n^2 cannot be divisible by 3, 7 or 13 -}
calcSum :: Integer -> Integer
calcSum lim = inner 0 pots
  where
    pots = map (\x -> x * 10) (filter (\z -> mod z 3 > 0 && mod z 7 > 0 && mod z 13 > 0)
                   [1..(div (lim - 1) 10)])
    inner :: Integer -> [Integer] -> Integer
    inner acc [] = acc
    inner acc (n:ns) | isPrimeL (map (\x -> x + (n * n)) [1,3,7,9,13,27]) = inner (acc + n) ns
    inner acc (n:ns) = inner acc ns

{- Calculate the sum up to 150,000,000 -}
main = print (calcSum 150000000)
--  main = print (calcSum 144000000)  -- correct answer

There are further optimisations that can be done but this was the first one that I ran and worked (took about 30 minutes). Also I discovered that the result from this solution run on niflheim is incorrect and I am not sure why. (Specifically 144774340 is apparently not valid yet seems to be from my code and wolframalpha...). Some further examination suggests it may be related to compiler optimisations, but am awaiting a much slower program to check.

Personal tools