# Is there a function that only generates primes?

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<y\to f(x)<f(y))]$$

and functions which involve calculating all previous numbers, i.e.

$$f(1)=2\wedge f(n)=\min\{f(n-1)<m\leq n!+1:(\forall r,s<m)[rs\neq m]\}.$$

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.

-
Perhaps you can review this Is there a formula that Generates Prime Numbers. Additionally, from MathWorld. Regards –  Amzoti Dec 16 '12 at 4:58
There are lots of them. Take a look at this wiki article. –  JSchlather Dec 16 '12 at 5:28
@DanBrumleve My question has a slightly different thrust than that one (and many of the links for prime generating functions). I am looking for a function which does not necessarily generate all primes, but generates no doubles and no "failed" values. It can't be the case that no polynomial-time function is known, since I mention an $O(n^3)$ algorithm in an answer below. (Unless you mean polynomial in $\log n$...) –  Mario Carneiro Dec 16 '12 at 6:14
@Yury, yes, but it's it's not an injective function of $n$. –  Dan Brumleve Dec 16 '12 at 7:15
@Yury Emphasis added. –  Mario Carneiro Dec 16 '12 at 7:22

I thought I'd give an overview of the prime-generating functions in Is there a formula that Generates Prime Numbers? and MathWorld: Prime Formulas, with attention to the constraints set above.

Wilson's Theorem (1770):

$$n\in\mathbb P\iff\frac{(n-1)!-1}n\in\mathbb Z$$

This one is possibly useful, but is only a prime indicator, not a formula.

Willans (1964):

$$f(n)=p_n=1+\sum_{k=1}^{2^n}\left\lfloor\sqrt[n]\frac n{1+\pi(k)}\right\rfloor$$

This one is plainly useless due to the presence of the prime-counting function $\pi(k)$. Since $f(n)$ depends on $\pi(k)$ up to $k=2^n$, this cannot even be defined recursively. However, Willans gives a non-recursive definition for $\pi(k)$, using Wilson's theorem:

$$\pi(k)=-1+\sum_{j=1}^k\left\lfloor\cos^2\bigg[\pi\frac{(j-1)!-1}j\bigg]\right\rfloor$$

In asymptotic-analysis terms, if we assume the $\cos^2x$ application is $O(1)$ (which is reasonable, because it is being abused here to act as an Iverson bracket), then the full formula for $f(n)$ is $O(\sum_{k=1}^{2^n}\sum_{j=1}^kj)=O(8^n)$. A better formula to get $f(n)$ from $\pi(k)$ (Martin-Ruiz & Sondow 2002) is

$$f(n)=p_n=1+\sum_{k=1}^{2(\lfloor n\log n\rfloor+1)}\left(1-\left\lfloor\frac{\pi(k)}n\right\rfloor\right)$$

which is $O((n\log n)^3)$, assuming $\pi(k)=O(k^2)$. A better formula for $\pi(k)$ also due to (Martin-Ruiz & Sondow 2002) is

$$\pi(k)=k-1+\sum_{j=1}^k\left\lfloor\frac2j\left(1+\sum_{s=1}^{\lfloor\sqrt j\rfloor} \left(\left\lfloor\frac{j-1}s\right\rfloor-\left\lfloor\frac js\right\rfloor\right) \right)\right\rfloor$$

which is only $O(k^{3/2})$, so that combining these gives $f(n)=O((n\log n)^{5/2})$.

By using a "real" primality test, $f^+(n)=\min(\mathbb P-{1,\dots,n})$ can be calculated in $O(n\log^{6+\varepsilon}n)$ (using AKS), so $f(n)=(f^+)^{(n-1)}(2)$ can be calculated, but the asymptotics of this depend on the distribution of primes. The best known (provable) upper bound is $p_n\leq2^n$, so $f(n)=O(2^n\log^{6+\varepsilon}n)$ this way.

-
The paper mentions a probabilistic algorithm that is $\log^{O(1)}n$. Anyone know (a) how the algorithm works and (b) what is the actual order of the method, i.e. $\log^{O(1)}n=O(\log^cn)$ for some $c$, but how high is $c$? –  Mario Carneiro Dec 16 '12 at 6:20
Also, is there a proof that no function exists to do this in $O(\mbox{something})$ $O(1)$ seems exceedingly unlikely, even letting arithmetic on arbitrary numbers be "free", but are there any proofs of lower bounds for this kind of thing? –  Mario Carneiro Dec 16 '12 at 6:44
Unfortunately, not really, because too little is known. If Cramér's conjecture is true then it can be done in polynomial time. It can't be done in $O(1)$ since we at least have to look at the input for it to be injective. –  Dan Brumleve Dec 16 '12 at 6:46
This is what I meant by letting arithmetic be free, i.e. $O(1)$. Perhaps a better approach is to say I am using $\widetilde O$ instead of $O$ notation. –  Mario Carneiro Dec 16 '12 at 7:06