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)

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
```
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. .
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)]
```
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)]
```
Investigation 1a. For each Poly, find the first input in the list that gives a prime number.
```
 first_prime_output :: Poly -> [Int] -> Maybe Int
```
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
```
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"
```
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]
```
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

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.
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]
```

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.

Last modified August 18, 2023: 2022-2023 End State (7352e87)