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

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.