Problem 40

Goldbach's conjecture says that every positive even integer greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It has been numerically confirmed up to very large numbers but remains unproven.

Return two prime numbers that sum up to a given even integer.

Example

goldbach 100 == (29, 71)

Unit Test

import Html
import List
import Maybe


goldbach : Int -> Maybe (Int, Int)
goldbach n =
    -- your implementation here
    Nothing


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         else
            "Your implementation failed at least one test."
        )


test : Bool
test =
    List.all (\n -> testGoldbach n <| goldbach n)
        [ 4, 10, 12, 14, 16, 18, 20, 100, 222, 120, 2444, 24444, 33336, 71000 ]
        && List.all (\n -> (goldbach n) == Nothing) [-99999, -1, 0, 1, 99, 9999]


testGoldbach : Int -> Maybe (Int, Int) -> Bool
testGoldbach n result =
    case result of
        Nothing -> False

        Just (p1, p2) ->
            if n < 3 && result /= Nothing then
                False
            else if isOdd n then
                False
            else if p1 + p2 /= n then
                False
            else if not (isPrime p1) || not (isPrime p2) then
                False
            else 
                True


-- The core library function Arithmetic.isOdd is not available
-- on elm-lang.org/try, so we'll recreate it here
isOdd : Int -> Bool
isOdd n =
    n % 2 /= 0


isPrime : Int -> Bool
isPrime n = 
    if n < 2 then
      False
    else
      List.member n <| primesInRange 2 n

Solutions

Solutions