# Euler Solution 146

### From ProgSoc Wiki

# Solutions for Problem 146

Find the sum of all *n* in the range 1..150000000 where *n ^{2}+1, n^{2}+3, n^{2}+7, n^{2}+9, n^{2}+13, n^{2}27* 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.