¿Hay una función que sólo genera números primos?

Question

El título lo resume todo: ¿existe una "buena" inyectiva función de $f(n)$ tal que $f(n)\in\mathbb P$ todos los $n\in\mathbb N$?

Estoy teniendo dificultad para especificar exactamente lo que quiero "bonito", que significa, y que tal vez los encuestados me puede ayudar a cristalizar esta idea. Básicamente, quiero eliminar la no-constructiva de las funciones, es decir,

$$\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))]$$

y funciones que implican el cálculo de todos los números anteriores, es decir,

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

Ahora ambas funciones construir bijections de$\mathbb N$$\mathbb P$, y la segunda es incluso computable en un tiempo finito para cualquier $n$, pero claramente no son "útiles", ya que sólo tienes que repetir las definiciones. Tal vez "computable" o "primitivas recursivas" hará el truco para esta definición, pero no estoy seguro. Sé que hay varias funciones que se usan para este fin, por ejemplo, $f(n)=2^{2^n}+1$ (de los números primos de Fermat) y $f(n)=2^n-1$ (primos Mersenne), pero ninguno de ellos produce primos exclusivamente. Hay funciones que hacer? Tal vez una definición operativa es que el cálculo de $f(n)$$O(1)$, suponiendo que $+$, $\cdot$, y exponenciación se $O(1)$ a calcular. (Mi segunda descripción de la función es $O(n!^3)$, creo que, debido a la triple cuantificación.)

(Otra posible relajación de las restricciones: ¿existe una función tal que $d(\{n:f(n)\notin\mathbb P\})=0$, es decir , finalmente, casi todos de los valores de la función son los números primos? Aquí $d(A)$ es la densidad del conjunto.) Edit: que originalmente se había aquí $|f(\mathbb N)-\mathbb P|<\infty$ a representar este concepto, pero, dada una función, se puede modificar fácilmente para producir una función tal que $f(\mathbb N)\subseteq\mathbb P$, por sólo cambiando el "malo" de los valores.

Answer 1

Pensé en darle una visión general de la prime-funciones de generación en ¿hay una fórmula que Genera Números Primos? y MathWorld: Primer Fórmulas, con especial atención a las restricciones establecidas anteriormente.

Wilson del Teorema (1770):

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

Este es posiblemente útil, pero es sólo un primer indicador, no es una fórmula.

Willans (1964):

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

Este es claramente inútil debido a la presencia de la primer función de recuento $\pi(k)$. Desde $f(n)$ depende de $\pi(k)$$k=2^n$, este puede ser definido de forma recursiva. Sin embargo, Willans da un no-definición recursiva para $\pi(k)$, el uso del teorema de Wilson:

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

En asintótica-análisis de términos, si suponemos que el $\cos^2x$ aplicación $O(1)$ (lo cual es razonable, porque está siendo abusado aquí para actuar como Iverson soporte), entonces la fórmula completa para$f(n)$$O(\sum_{k=1}^{2^n}\sum_{j=1}^kj)=O(8^n)$. La mejor fórmula para conseguir $f(n)$ $\pi(k)$ (Martín-Ruiz & Sondow 2002) es

$$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)$$

que es $O((n\log n)^3)$, asumiendo $\pi(k)=O(k^2)$. La mejor fórmula para $\pi(k)$ también debido a (Martín-Ruiz & Sondow 2002) es

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

que sólo es $O(k^{3/2})$, por lo que la combinación de estas da $f(n)=O((n\log n)^{5/2})$.

Mediante el uso de una "verdadera" prueba de primalidad, $f^+(n)=\min(\mathbb P\setminus\{1,\dots,n\})$ puede ser calculado en $O(n\log^{6+\varepsilon}n)$ (con AKS), por lo $f(n)=(f^+)^{(n-1)}(2)$ puede ser calculado, pero el asymptotics de este dependen de la distribución de los números primos. Los más conocidos (comprobable) límite superior es $p_n\leq2^n$, lo $f(n)=O(2^n\log^{6+\varepsilon}n)$ de esta forma.

Answer 2

No se sabe que ninguna función de generación de primos es computable en tiempo polinomial . Sin embargo, tal vez hay una solución para el caso "casi todo".