M
M
Markiv072021-11-28 22:57:54
Haskell
Markiv07, 2021-11-28 22:57:54

How to do a Goldbach Conjecture Test in Haskell?

Here I am learning Haskell, there is a code that tests the Goldbach hypothesis (That all even numbers after 4 can be given by the sum of 2 primes)
Here is the code

func1 :: [a] -> a
func1 (x:xs) = x

hipo :: Int -> (Int, Int)
hipo a = func1 $
                    filter (\(x,y) -> isPr x && isPr y) $
                    map (\c -> (c, a - c)) [3,5..a `div` 2]
  where
  factors a = filter (isFactor a) [2..a-1]
  isFactor a b = a `mod` b == 0
  isPr 1 = False
  isPr a = null $ factors a

mainFunc :: [Int] -> [(Int, Int)]
mainFunc [] = []
mainFunc (x:xs) = hipo x : mainFunc xs

main :: IO ()
main =  do
print(mainFunc [6,10..17])


I don't understand how this piece of code works.
hipo :: Int -> (Int, Int)
hipo a = func1 $
                    filter (\(x,y) -> isPr x && isPr y) $
                    map (\c -> (c, a - c)) [3,5..a `div` 2]
  where
  factors a = filter (isFactor a) [2..a-1]
  isFactor a b = a `mod` b == 0
  isPr 1 = False
  isPr a = null $ factors a


If someone understands, can you please explain what is happening there?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
A
Alexander Skusnov, 2021-11-29
@Markiv07

Repeat from the previous question:
Everything is clear here:
Hypothesis: any even (> 2) can be represented as the sum of two primes.
We take a list of odd ones (primes are always odd, except for 2): [ 3, 5 ..]. This will be the first term. If the desired number is a, then the second term is ac (c is the first term). It is clear that the list of the first term can be limited to a `div` 2, i.e. we get [3,5..a `div` 2].
Further, the map function, receiving each element of the list (c), forms a pair of terms: c - the first, ac - the second.
This is what we described map (\c -> (c, a - c)) [3,5..a `div` 2]
For example, for 10 we get the list [(3,7), (5,5)].
From this list, you need to throw out pairs where there are non-simple (composite) numbers. For example, for 12 the list [(3,9), (5,7)] will discard the first pair (by the filter), because 9 - composite (divided by 3).
If there are several pairs in the resulting list, then func1 simply takes the first one (for example, for 10 there will be a pair (3,7)). func1 is the standard head function.
Well, auxiliary functions: isPr - check for a prime number, isFactor - for a composite number.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question