Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
22 lines (16 sloc) 866 Bytes
{-
- Solution to Project Euler problem 123
- Copyright (c) Project Nayuki. All rights reserved.
-
- https://www.nayuki.io/page/project-euler-solutions
- https://github.com/nayuki/Project-Euler-solutions
-}
import Data.Numbers.Primes (primes) -- From https://hackage.haskell.org/package/primes
-- Using the result from Project Euler #120, we know that (a-1)^n + (a+1)^n mod a^2 = if n is even then 2 else 2an. Since 2 is tiny, we can skip the n is even case.
-- a is the n'th (1-based) prime number, so a > n. In fact for n >= 5, we have a > 2n, so we can take 2an directly without moduloing it by a^2.
main = putStrLn (show ans)
-- Equivalent to this slower code: head $ dropWhile (\n -> n * 2 * (primes !! (n - 1)) <= 10^10) [5, 7 ..]
ans = findFirst 5 (drop 4 primes)
findFirst n (p:_:ps)
| n * 2 * p > 10^10 = n
| otherwise = findFirst (n + 2) ps