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 !)

4more comments