{- |
Description: Goldbach's conjecture
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P40" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P40 (goldbach) where

import           Problems.P31
import           Solutions.Arithmetic

-- | Find two prime numbers that sum up to a given even integer.
goldbach :: Integral a => a -> (a,a)
goldbach :: forall a. Integral a => a -> (a, a)
goldbach a
n = a -> [a] -> (a, a)
forall a. Integral a => a -> [a] -> (a, a)
search a
n [a]
forall a. Integral a => [a]
primes

search :: Integral a => a -> [a] -> (a, a)
search :: forall a. Integral a => a -> [a] -> (a, a)
search a
n (a
p:[a]
ps)
  | a
p a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
n    = (a, a)
forall a. HasCallStack => a
undefined
  | a -> Bool
forall a. Integral a => a -> Bool
isPrime a
q = (a
p, a
q)
  | Bool
otherwise = a -> [a] -> (a, a)
forall a. Integral a => a -> [a] -> (a, a)
search a
n [a]
ps
  where q :: a
q = a
na -> a -> a
forall a. Num a => a -> a -> a
-a
p
search a
_ [a]
_ = (a, a)
forall a. HasCallStack => a
undefined