The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$?
I'm having difficulty specifying exactly what I want "nice" to mean, and perhaps respondents can help me crystallize this notion. Basically, I want to eliminate non-constructive functions, i.e.
$\mathbb P\subseteq\omega\Rightarrow\mathbb P\mbox{ is well-ordered}\Rightarrow(\exists f)[f(\mathbb N)=\mathbb P\wedge (x
and functions which involve calculating all previous numbers, i.e.
$f(1)=2\wedge f(n)=\min\{f(n-1)
Now both of those functions construct bijections from $\mathbb N$ to $\mathbb P$, and the second one is even computable in a finite time for any $n$, but these are clearly not "useful", since they just restate the definitions. Maybe "computable" or "primitive recursive" will do the trick for this definition, but I'm not sure. I know there are several functions used for this purpose, like $f(n)=2^{2^n}+1$ (Fermat primes) and $f(n)=2^n-1$ (Mersenne primes), but neither one produces primes exclusively. Are there any functions that do? Perhaps a workable definition is that calculation of $f(n)$ is $O(1)$, assuming that $+$, $\cdot$, and exponentiation are $O(1)$ to compute. (My second function description is $O(n!^3)$, I believe, due to the triple quantification.)
(Another possible relaxation of the constraints: does there exist a function such that $d(\{n:f(n)\notin\mathbb P\})=0$, i.e. eventually almost all of the values of the function are primes? Here $d(A)$ is set density.) Edit: I originally had here $|f(\mathbb N)-\mathbb P|<\infty$ to represent this concept, but given such a function, one can easily modify it to produce a function such that $f(\mathbb N)\subseteq\mathbb P$, by just shifting off the "bad" values.