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.

  • 2
    $\begingroup$ Perhaps you can review this Is there a formula that Generates Prime Numbers. Additionally, from MathWorld. Regards $\endgroup$ – Amzoti Dec 16 '12 at 4:58
  • $\begingroup$ There are lots of them. Take a look at this wiki article. $\endgroup$ – JSchlather Dec 16 '12 at 5:28
  • 1
    $\begingroup$ @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$...) $\endgroup$ – Mario Carneiro Dec 16 '12 at 6:14
  • 1
    $\begingroup$ @Yury, yes, but it's it's not an injective function of $n$. $\endgroup$ – Dan Brumleve Dec 16 '12 at 7:15
  • 1
    $\begingroup$ @Yury Emphasis added. $\endgroup$ – 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:


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\setminus\{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.


No prime-generating function is known to be computable in polynomial time. However, maybe there is a solution to the "almost-all" case.

  • 1
    $\begingroup$ 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$? $\endgroup$ – Mario Carneiro Dec 16 '12 at 6:20
  • $\begingroup$ 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? $\endgroup$ – Mario Carneiro Dec 16 '12 at 6:44
  • $\begingroup$ 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. $\endgroup$ – Dan Brumleve Dec 16 '12 at 6:46
  • $\begingroup$ 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. $\endgroup$ – Mario Carneiro Dec 16 '12 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.