6
$\begingroup$

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.

  • 0
    I missed that. Thanks!2012-12-16

2 Answers 2

10

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

3

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

  • 0
    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.2012-12-16