Given a positive integer $N$ does there exist a polynomial $P$ with non-negative integer coefficients such that $P(n)$ is a prime number for $1\leq n <N$ and $P(N)$ is a composite number? Also, if for given $N$ we know that such a polynomial exists can we algorithmically find an example?
Examples
- $N=1: P(n)=4$
- $N=2: P(n)=n+2$
- $N=3: P(n)=n+1$
- $N=4: P(n)=n^2+n+1$
- $N=40:P(n)=n^2+n+41.$
Best Answer
Let $p_1,p_2, ... , p_k$ be a sequence of at least N-1 primes in AP with common difference $d$. The sequence cannot continue generating primes for ever since $p_1+dp_1$ is not prime.
Therefore we can change our starting position in the sequence so there are precisely $N-1$ primes before a composite number is reached. Let $p$ be the first prime in this sequence then the required function is $$P(n)=p-d+dn.$$