2022-11-30 Composite Poly

In this exercise we will investigate the question of whether a quadratic function with integer coefficients that does not factor can always produce composite numbers.

Given integers a and b, the polynomial they correspond to is the quadratic:

$$f(x) = x^2 + a * x + b .$$

type Poly = (Int,Int)

1. The first question is whether this polynomial factors. The “factor theorem” … says that if we find a value $x=c$ so that $f(c)=0$ , then $(x-c)$ is a factor of $f(x)$ . In math class you probably learned that the possible integer zeros of $f(x)$ are the divisors of the constant term. That means we are going to check to see if any of the divisors k of b (positive or negative) make the function zero. If you find one, you’ve found a factorization.

   You should write two functions.

   • zero_search: Produce one value that makes the polynomial zero, if there is one. Otherwise Nothing.
   • factorable: True if the polynomial has a zero. False otherwise.

   The signatures of these two functions are:

    zero_search :: Poly -> Maybe Int
    factorable :: Poly -> Bool
   

2. Testing.

   • Make a check_zero_search variable showing that $x^2-11x+28$ , has a zero and so does $x^2-x-12$ .
   • Make a check_factorable variable that shows $x^2-5x+9$ is not factorable but the two polynomials mentioned above are. .

3. The second question is whether you can find a prime number output of a polynomial. You have written is_prime before; it determines of an integer is prime. The prime_search function takes a list of numbers and a polynomial, and outputs the list of all of those numbers that make the polynomial produce a prime number along with the prime output.

    is_prime :: Int -> Bool
    prime_search :: [Int] -> Poly -> [(Int,Int)]
   

4. Testing. Inputs of 7 and 9 to $f(x) = x^2+4x-10$ produce primes. Verify this.

    prime_search [5..10] (4,-10) == [(7,67),(9,107)]
   

5. Investigation 1a. For each Poly, find the first input in the list that gives a prime number.

    first_prime_output :: Poly -> [Int] -> Maybe Int
   

6. Investigation 1b. Produce a tuple: the coefficients used, a Boolean indicating if it is factorable or not, and either Nothing or Just the lowest integer value of $4\le x\le 100$ giving a prime output, and Just the resulting output, or Nothing if not applicable.

    type SummaryRow = (Poly, Bool, Maybe Int, Maybe Int)
    invest1 :: Poly -> SummaryRow
   

7. Investigation 1c. Make a single line string from a summary row. Use tabs to make a rough table. Include a newline at the end.

    output1 :: SummaryRow -> String
    output1 ((3,-10),True,Nothing,Nothing) == "(3,-10)\t\tTrue\t\tNothing\t\tNothing\n"
   

8. Investigation 2. Now try all of the quadratic functions with a and b in the range [(-10)..10]. Make a “table” applying invest1 to every one of these Poly.

    invest2 :: [Poly] -> [SummaryRow]
   

9. Output. Take a list of SummaryRow and produce a printable table with line breaks and spacing between each column. You can get it to look decent with not too much effort by putting a few tabs between each column instead of spaces.

   Example:

    output_table :: [SummaryRow] -> String
    demo = "Poly\t\tFactor\t\tRoot\t\t41\n(4,-10)\t\tTrue\t\tJust 7\t\tJust (67)\n(3,5)\t\tFalse\t\tNothing\t\tNothing\n"
    main = putStrLn demo
   

Sample Output

For this example, I made a grid variable with all of the ordered pairs as described in investigation 2 and then ran invest2 and output_table on it.

-- output_table $ invest2 grid
[...]
(7,7)      False      Just 5     Just 67
(7,8)      False      Nothing    Nothing
(7,9)      False      Just 4     Just 53
[...]

Notes

1. Usually in computer science you write the polynomials with the lowest degree term first, using [b,a,1] represents $b+ax+1x^2$ . I thought that would be confusing so I didn’t do it here.

2. A more sophisticated program would work for quadratics with leading coefficient not 1, and probably higher degree polynomials as well. Make changes to allow this.

   Represent polynomials by a list of coefficients, so index k in the polynomial represents the coefficient of $x^k$ . For example, [-5,-13,6] represents $f(x)=6x^2-13x-5$ .

        type BigPoly = [Int]
   

3. Question: Why don’t you make zero_search return a list of all of the zeros? Answer: In order to get you to practice using Maybe.