# Al Zimmermann's Programming Contests

## Prime Generating Polynomials

*by Ed Pegg Jr*

**Introduction**

Find the best prime generating polynomials for orders 1 to 10.

Note: this is a computational problem, not a mathematical one.
**Description**

For every order 1 to 10, you should submit three polynomials that generate prime numbers.

An order 1 polynomial is of the form: **a*x + b**

An order 2 polynomial is of the form: **a*x**^{2} + b*x + c

An order 3 polynomial is of the form: **a*x**^{3} + b*x^{2} + c*x + d

etc...

The three polynomials are:

- a polynomial f(x), such that f(x) generates the most distinct prime numbers in a row.

The scorer will start computing f(x) with x=0, then increment x until f(x) is negative or not prime.

If a prime number appears several times, it will be only counted once.

- a polynomial f(x), such that abs(f(x)) generates the most distinct prime numbers in a row (abs(x) is the absolute value of x).

The scorer will start computing f(x) with x=0, then increment x until abs(f(x)) is not prime.

If a prime number appears several times, it will be only counted once.

- a polynomial f(x), such that abs(f(x)) generates the most distinct prime numbers from x = 0 to x = bound(order) inclusive.

The scorer will compute f(x) with x=0 to bound(order), counting the number of distinct primes of abs(f(x)).

bound(order) is defined as follows (note: these bounds have been computed so that bound(order)^{order} is below 2^{64}):
order |
bound(order) |

1 | 1000 |

2 | 1000 |

3 | 1000 |

4 | 1000 |

5 | 1000 |

6 | 1000 |

7 | 500 |

8 | 250 |

9 | 120 |

10 | 60 |

**The Task**

The contest is held in **two** parts:

- In the first part, you can submit either the integer coefficients of the polynomials
**or** first terms of the sequences.
- In the second part, you can submit
**only** integer coefficients of the polynomials.

All the inputs must be integers (positive or negative) separated by a single space.

If you submit n coefficients then the scorer will compute its score as a polynomial of order n-1.

The first coefficient corresponds to x^{(n-1)}, the second to x^{(n-2)} and so on until the last coefficient is the constant.

Note that the first coefficient cannot be 0.

If you submit n terms of a sequence then the scorer will compute its order by using finite differences and will deduce the other terms.

**The Scoring System**

The score for a polynomial f(x) of order n is equal to:

**(number of desired primes that f(x) produces) + (1/log(10+absolute(f(0)*f(1)*..*f(n))))**

The zero numbers are not taken into account.
For example:

x^{2}+x+41 gives 40 primes with f(0)=41, f(1)=43 and f(2)=47, so its score for category 1 is 40+1/log(10+absolute(41*43*47))=40.203318045613

x^{2}-79x+1601 gives 40 primes with f(0)=1601, f(1)=1523 and f(2)=1447, so its score for category 1 is 40+1/log(10+absolute(1601*1523*1447))=40.104738804924

**Total Scoring**

Your total score is the sum of all your 30 polynomial scores, where the polynomial score is:

**Q=(your best score)/(the best submitted score for that polynomial)**

polynomial score = (0.7 * Q) + (0.1 * Q^{16}) + (0.1 * Q^{128}) + (0.1 * Q^{1024})

If you do not submit a polynomial for a particular order of n, you will receive a score of 0 for all categories of polynomials of order n.

When you submit a polynomial, it is automatically scored for all the categories, and if it improves one of your results, your total score is changed accordingly.

The best possible score is 30.

**Prizes**

The first prize for part 1 is **$200**, the second prize is **$100**. The only prize for part 2 is **$100**.

There are three special prizes:

**$30** for the best polynomial generating the the largest number of consecutive distinct primes (either negative or positive).
**$20** for the best polynomial generating the the largest number of consecutive distinct primes (either negative or positive) **with integer coefficients**.
**$50** for improving N=1 or N=2.

In case of a tie, the entrant who reached the tied score first wins.

At the end of every week for the first **10** weeks, the score leader of part 1 will win **$10**.

All prizes will be paid via Paypal.
**Organization**

As the organizers, we may change the rules during this contest.
**Thanks**

Thanks to Dmitry Kamenetsky, Eric Bainville, Juha Saukkola, Steve Trevorrow and François Glineur for helping to define the rules, and to Hugo Pfoertner for helping to design the scoring formula.