A student of mine keeps coming again and again and telling *"I've found a formula $n\mapsto f(n)$ giving all primes"* or sometimes *"infinitely many primes"*, where $f$ is a classical function (I mean made of exponentials and polynomials, just like Mersenne primes). Then follows a long discussion, me saying *"nice try, but it doesn't work because ..."*, and him argumenting ... and trying to restrict $f$ to the primes ...


Today I told him something like: *"you know, many great mathematicians tried to find such formulas, but never succeeded"* and he answered: *"maybe they didn't see something elementary, and I can find it"*.


Now the questions: let $\mathcal S$ be the algebra of sequences of integers (under $+$, $\times$ and $\circ$). Let $\mathcal S\_0$ be the smallest subalgebra containing all polynomial sequences $n\mapsto P(n)$ for $P\in \mathbf Z[X]$, and all exponentials $n\mapsto a^n$ for $a\in\mathbf Z$. Let $\mathcal S\_1$ be the subset of $\mathcal S\_0$ made of sequences $n\mapsto f(n)$ satisfying $f(n)>n$ for any integer $n$.


Q1) Is there any result saying that no element of $\mathcal S\_1$ can have an infinite subset of the set of primes as its image?


Or even better :


Q2) Is there any result saying that the image by an element $f$ of $\mathcal S\_1$ of the set of prime numbers must contain infinitely many composite numbers?


And finally :


Q3) Is there any result saying that if $f$ is an element of $\mathcal S\_0$ satisfying $f(n)>n$ for all $n$, and $u\_n$ is the sequence obtained by choosing an initial value $u\_0$ and by setting $u\_{n+1}=f(u\_n)$, then $(u\_n)\_n$ must contain at least one composite numbers?


(Ok, this is not exactly a research question, but answers would help research since it would enable me to reject his proposals directly, without the need of finding counter-examples). From this point of view, negative answers wouldn't be welcome !)



Elementary prime-generating sequences
Do a web search for Diophantine Representation of prime numbers. You will find an article of that title containing a polynomial of degree 25 in 26 variables whose range intersected with the positive integers is exactly the prime numbers.


There are general results for polynomials of one variable which extend to several variables which show that the range (both positive and negative) cannot be exclusively primes. Also the Prime Pages online, and books by Ribenboim, contain essays on the subject addressing your question, references on such are easily found by web searches.


In short, he is right, there could be something elementary that others might have overlooked. If he can derive the degree 25 polynomial above on his own, I say have him keep looking, AFTER he reads and understands the essays.


Gerhard "Don't Spoil His Prime Fun" Paseman, 2016.02.04.


