Euler Problem 123 – Remainder of Primes

Here is another prime number problem. Again, I re-used my prime number sieve, which I called whenever a remainder was to be calculated. I suppose I could have sped things up a bit by pre-calculating the primes, but this routine still runs in only a few minutes and does the trick.

Haskell’s list manipulation capabilities are simply amazing. The one thing I wasn’t sure about was if asking for the list head in main was sufficient to end the routine. Note that the list comprehension is based on [1,3..] which is open ended. Obviously, it did end, otherwise you wouldn’t be reading this and I’d still be staring at the prompt.

import Data.List.Ordered

pri :: [Integer]
pri = 2 : sieve [3,5..] where
    sieve [] = []
    sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p..])

calcRem :: Integer -> Integer
calcRem n = (((pri!!(x-1))-1)^x + ((pri!!(x-1))+1)^x) `rem` (pri!!(x-1))^2
	where x = fromIntegral n
	
main = print $ head [x | x <- [1,3..], calcRem x > 10^10]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s