REVISED: Thursday, February 8, 2024
1. INTRODUCTION
1.1 GIVEN
1.1.1 Consider the following proposition:
For all n in the set of positive Natural numbers, the function f n = n ^ 2 + n + 41 is a prime number is True.
1.1.2 Definition
A Prime Number is a whole number greater than or equal to 2 which has two and only two factors; for example, it can be divided without a remainder only by 1 and itself.
2. HASKELL PROGRAM
2.1 TO BE PROVED
We will use a proof by contradiction.
Therefore, we assume that the statement of the proposition that for all n in the set of positive Natural numbers, the function f n = n ^ 2 + n + 41 is a prime number is False.
2.2 PROOF
The Haskell program used for the proof is as follows:
-- C:\Users\Tinnel\Haskell2024\proof1.hs
import Data.Char
import Data.List
import Data.List (elemIndex)
import Data.Map
import Data.Maybe
import Data.Set
import System.IO
--
--
main :: IO () -- Has type I/O action.
main = do { putStrLn "" -- putStrLn Has type I/O action.
; putStrLn "======================================================"
; putStrLn ""
; putStrLn "Prove the proposition that for all n in the set of positive Natural numbers, the function"
; putStrLn ""
; putStrLn "f n = n ^ 2 + n + 41"
; putStrLn ""
; putStrLn "is a prime number is False."
; putStrLn ""
; putStrLn "======================================================"
; putStrLn ""
; putStrLn "Type a positive integer value for n then press Enter."
; s <- getLine -- getLine is a function, getLine :: IO String
; putStrLn ""
; putStrLn "======================================================"
; putStrLn ""
; putStrLn ("Computing the function with n equal to " ++ s ++ ".")
; putStrLn ""
; let n = (read s)::Integer -- Type converted from IO String s to Integer n.
; let z = f n -- z is the integer prime number computed by n.
; let zS = show z -- Type converted from Integer z to String z.
; putStrLn ("f n = n ^ 2 + n + 41 equals " ++ zS ++ ".")
; putStrLn ""
; putStrLn "======================================================"
; putStrLn ""
; putStrLn "The list of the first 300 prime numbers starting with 2 is as follows:"
; putStrLn ""
; print p -- The list of prime numbers.
; putStrLn ""
; putStrLn "======================================================"
; putStrLn ""
; putStrLn ("QUESTION: True or False is " ++ zS ++ " a prime number?")
; putStrLn ""
; let i = if elem z p == True then "True" else "False"
; putStrLn ("ANSWER: " ++ i ++ ".")
; putStrLn ""
; putStrLn ""
; putStrLn ""
}
--
--
-- t computes prime numbers.
t :: Integral a => [a] -> [a]
t (p : xs) = p : t [x | x <- xs, x `mod` p /= 0]
-- primes is a list of prime numbers computed by t.
primes :: [Integer]
primes = t [2..] -- Starting with 2 because zero and 1 are not prime numbers.
-- However, main can compute n = 0, and n = 1.
-- p is a list of prime numbers taken from those computed by t.
p :: [Integer]
p = take 300 primes
-- f n computes each number compared to the list p for prime.
f :: Num a => a -> a
f n = n ^ 2 + n + 41
-- read :: Read a => String -> a
-- (==) :: (Eq a) => a -> a -> Bool
3. GHCi RUN
GHCi, version 9.8.1: http://www.haskell.org/ghc/ :? for help
Prelude> :l proof1
[1 of 1] Compiling Main ( proof1.hs, interpreted )
Ok, modules loaded: Main.
*Main> main
=========================================================================
Prove the proposition that for all n in the set of positive Natural numbers, the function
f n = n ^ 2 + n + 41
is a prime number is False.
=========================================================================
Type a positive integer value for n then press Enter.
5
=========================================================================
Computing the function with n equal to 5.
f n = n ^ 2 + n + 41 equals 71.
=========================================================================
The list of the first 300 prime numbers starting with 2 is as follows:
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987]
=========================================================================
QUESTION: True or False is 71 a prime number?
ANSWER: True.
4. TRUTH TABLE
Running the Haskell program for each element of n we obtain the truth table shown below:
n f n = n^2 + n + 41 Prime
---- ------------------------ -------
0 41 True
1 43 True
2 47 True
3 53 True
4 61 True
5 71 True
6 83 True
7 97 True
8 113 True
9 131 True
10 151 True
11 173 True
12 197 True
13 223 True
14 251 True
15 281 True
16 313 True
17 347 True
18 383 True
19 421 True
20 461 True
21 503 True
22 547 True
23 593 True
24 641 True
25 691 True
26 743 True
27 797 True
28 853 True
29 911 True
30 971 True
31 1033 True
32 1097 True
33 1163 True
34 1231 True
35 1301 True
36 1373 True
37 1447 True
38 1523 True
39 1601 True
40 1681 False Q.E.D.
41 1763 False
42 1847 True
43 1933 True
44 2021 Outside of the first 300 prime number range.
5. CONCLUSION
The proposition that for all n in the set of positive Natural numbers, the function f n = n ^ 2 + n + 41 is a prime number is False.
As shown above you have to be very careful when concluding a proof is True or False. The first 39 tests would lead most people to assume f n = n^2 + n + 41 could be used to compute prime numbers. However test 40 and 41 show the proposition is not True, it is False.
6. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
