¿Cuál es el de más rápido crecimiento de la función que se sabe que contienen una infinidad de números primos?

Question

Sé que Dirichlet del Teorema dice que por cada $a,b\in\mathbb{N}$ $\gcd(a,b)=1$ $a\ge 1$ la función \begin{align*} f:\mathbb{N}&\to\mathbb{N}\\ n&\mapsto an+b \end{align*} evalúa a un número primo para infinidad de $n\in\mathbb{N}$. Sin embargo, no sabemos si existen polinomios cuadráticos contiene infinitos números primos. Esto me hizo preguntarme:

¿Qué es el crecimiento más rápido de la función $f:\mathbb{N}\to\mathbb{N}$, por lo que $f(n)$ es computable en $O(\log n)$ $\{f(n):n\in\mathbb{N}\}$ se sabe que contiene una infinidad de números primos?

Answer 1

Estoy seguro de que este no es el más rápido, pero es super lineal. Es conocido por $k$ suficientemente grande, siempre hay un primer entre el$k^3$$(k+1)^3$. Ahora considere la siguiente función. Si $n = 2^{2m+1}+j$, $0 \le j < 3 \cdot 2^{2m+1}$, entonces $f(n) = 2^{3m}+j$. Tenga en cuenta que$2^{3m} + 3 \cdot 2^{2m+1} > (2^m+1)^3$$m \ge 1$. Por tanto, para cada suficientemente grande $m$, siempre va a ser $0 \le j < 3 \cdot 2^{2m+1}$ que $f(2^{2m+1}+j)$ es primo.

Answer 2

Será difícil encontrar algo que crece más rápido que este.

En el finales de los años cuarenta Molinos pruebe que existe un número real $A>1$ que $\lfloor{A^{3^n}}\rfloor$ es siempre un primer $(n = 1,2,3,...)$.

Answer 3

Mapa de $\mathbb{N}$ a $\mathbb{N}^2$ (por ejemplo, mediante la separación de par o impar de dígitos de una base estándar $b$ de representación). A continuación, utilice el Friedlander-Iwaniec teorema (asignando el resultado de la primera asignación $(n_1,n_2)$ a $n_1^2 + n_2^4$). Esto parece dar una función que es $O(n^2)$ que se cumple la "infinidad de números primos" criterio.

La complejidad criterio de falla, AFAICS, sin embargo, pero no por mucho (parece ser $O(\log n \log \log n\;2^{O(\log^* n)})$ usando Furer del algoritmo).