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