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*x2 + b*x + c
An order 3 polynomial is of the form: a*x3 + b*x2 + c*x + d
etc...

The three polynomials are:
  1. 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.

  2. 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.

  3. 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 264):
order bound(order)
11000
21000
31000
41000
51000
61000
7500
8250
9120
1060

The Task

The contest is held in two parts:
  1. In the first part, you can submit either the integer coefficients of the polynomials or first terms of the sequences.
  2. 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:

x2+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
x2-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 * Q16) + (0.1 * Q128) + (0.1 * Q1024)
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:

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.

Questions ?
Return to the index