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.

  • 2
    Perhaps you can review this [**Is there a formula that Generates Prime Numbers**](http://www.sonoma.edu/math/colloq/primes_sonoma_state_9_24_08.pdf). Additionally, from [**MathWorld**](http://mathworld.wolfram.com/PrimeFormulas.html). Regards2012-12-16
  • 0
    There are lots of them. Take a look at [this](http://en.wikipedia.org/wiki/Formula_for_primes) wiki article.2012-12-16
  • 0
    Possible duplicate: http://math.stackexchange.com/questions/226434/some-ways-to-get-a-set-of-primes/2012-12-16
  • 1
    @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$...)2012-12-16
  • 0
    @Mario, yes, "polynomial-time" means $O((\log{n})^k)$ in this context. Indeed, this is a much better question than the one I linked to, but the answers to that one include many examples. The paper I linked to in my answer was offered as a comment to [a similar question](http://math.stackexchange.com/questions/227363/is-there-a-polynomial-time-algorithm-to-find-a-prime-larger-than-n) of my own.2012-12-16
  • 0
    Also, using the AKS primality test we can always find the next prime greater than $n$ in $O(n \cdot (\log{n})^6)$.2012-12-16
  • 0
    How about “the largest prime factor of $\lceil \ln (n+3)\rceil$”? This function is computable in polynomial time.2012-12-16
  • 1
    @Yury, yes, but it's it's not an injective function of $n$.2012-12-16
  • 1
    @Yury Emphasis added.2012-12-16
  • 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.

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