# Is there a polynomial that generates only primes or semi-primes?

I know that no non-constant polynomial function $P(n)$ with integer coefficients exists that evaluates to a prime for every integer value of $n$.

My question is - does there exist a non-constant polynomial function $P(n)$ with integer coefficients that evaluates to either a prime or a semi-prime for every integer value of $n$?

More generally - does there exist a non-constant polynomial function $P(n)$ with integer coefficients such that for every integer value of $n$, the number of prime factors with multiplication of $P(n)$ is bounded?

I assume that the answer is no, but has this been proved?

Thanks

## migrated from mathoverflow.netFeb 16 '15 at 23:18

This question came from our site for professional mathematicians.

• Use the chinese remainder theorem. Voting to migrate to MSE. – Lucia Feb 16 '15 at 15:53
• en.wikipedia.org/wiki/… – bmurph Feb 16 '15 at 15:56

Suppose $f(x)$ is a nonconstant integer-valued polynomial such that $\Omega(f(n))\le B$ for all integers $n$ (for some positive integer $B$). Then there is some $m$ such that $|f(m)|>1$ (else the polynomial is constant). Define $g(x)=f(x+m)$ so that $|g(0)|>1$ and note that $g(x)$ is a nonconstant integer-valued polynomial. Now let $p$ be a prime dividing $g(0)$ and define $h(x)=g(px)/p$. Note that $h(x)$ is a nonconstant integer-valued polynomial and $\Omega(h(n))\le B-1$ for all integers $n$. This creates an infinite descending chain, showing that no such $B$ can exist.
• @TheMaskedAvenger: I believe the proof can be extended to that case as well. Instead of looking for a case where $|f(m)|>1$ you look for $f(m)$ not $p_1,\ldots,p_k$-smooth. The smooth numbers grow too quickly to be a polynomial so such an $m$ exists. – Charles Feb 16 '15 at 21:53
• @TheMaskedAvenger: At the n-th step in my modified process, you've found an arithmetic progression of terms in the original polynomial which are divisible by $n$ distinct primes. To get to the (n+1)-th step it suffices to find a sub-progression divisible by a number > 1 relatively prime to the $n$ primes. If no such term existed then all terms in this polynomial would be products of those $n$ primes, but there aren't enough primes to let the sequence grow polynomially. – Charles Feb 16 '15 at 22:04