¿Cuál es la expresión de forma cerrada más restrictiva que todavía genera los números primos?

Question

"El conjunto de $\{f(n)\}, n=1,2,\ldots$ incluye todos los números primos excepto un número finito de excepciones".

Esta declaración es verdadera para $$f(n)=\sqrt{1+24n},$$ para que las excepciones son 2 y 3. También genera la no-enteros y no prime enteros, sin embargo. (alerta de spoiler) La prueba utiliza el hecho de que los dos vecinos de todos los números primos (excepto 2 y 3) contienen los factores 2, 3 y 4 entre ellos (2*3*4=24).

Ya no hay más factores que 2^3 y 3 se pueden encontrar generalmente en los dos vecinos de los números primos, la expresión $f(n)=\sqrt{1+24n}$ es el más restrictivo de la expresión de esa particular forma funcional que todavía genera todos los números primos. Es decir, genera todos los números primos y el menor número de no-primos.

Otras expresiones que se ajustan a la declaración anterior se $f(n)=\sqrt{1+4n}$, $f(n)=2n-1$ y, por supuesto,$f(n)=n$, pero producen más no de los números primos.

Mi pregunta: Se sabe que de forma cerrada expresión $f(n)$ genera todos los números primos y el número más pequeño (en cierto sentido) de los no primos? Es quizás $f(n)=\sqrt{1+24n}$?

Answer 1

Un número es relativamente alto a $24$ si y sólo si es una raíz cuadrada de la unidad mod $24$. Así $f(n)$ genera los números enteros que no son divisibles por $2$ o $3$, incluyendo más de $3$ todos primos. Es posible hacerlo mejor: $g(x) = \sqrt{\frac{5 + 33 \cdot (-1)^n + 15 n}{2}}$ genera más de $5$ todos primos sin incluir cualquier enteros divisibles por $2$, $3$, $5$.

Answer 2

Escribí estas dos pequeños códigos fuente en madera de Arce:

$1)$

"n de 1 a 100 por 1 do

si isprime(2n-3), entonces

print(n);

end if;

fin de hacer;"

$2)$

"n de 1 a 100 por 1 do

si el tipo(sqrt(24n+1),prime), a continuación,

print(n);

end if;

fin de hacer;"

El primer código es dar a $44$ los valores de n cuando el resultado de la expresión es el primer número y el segundo código es dar sólo $13$ los valores de n.

Así que podemos concluir que la forma cerrada $f(n)=2n-3$ es "más rico" que forma cerrada $f(n)=\sqrt{24n+1}$

EDITAR :

En uno de mis posts anteriores he demostrado que :

$M_p \equiv 1 \pmod {6\cdot p}$ donde $M_p$ es de Mersenne número .

Así :

$2^{p}-1=6np+1 \Rightarrow 2^p=6np+2 \Rightarrow 2^{p-1}=3np+1$

Si podemos resolver esto de la igualdad de $p$, se obtendrá con la siguiente fórmula :

$$p=-\left(\frac{3n\cdot W\left(-\frac{2^{-1-\frac{1}{3n}}\cdot \ln 2}{3n}\right)+\ln 2}{n\cdot \ln 8}\right)$$

donde $W$ es la función W de Lambert

De esta forma cerrada de expresión genera todos los números primos mayores que $3$ y el reducido número (en el sentido de la densidad asintótica ) de la no-prime enteros .

Corrección :

En realidad esta cerrado expresión produce valores enteros para la rama inferior de la función W de Lambert, que se denota como $W_{-1}(x)$, por lo que la fórmula es :

$$p=-\left(\frac{3n\cdot W_{-1}\left(-\frac{2^{-1-\frac{1}{3n}}\cdot \ln 2}{3n}\right)+\ln 2}{n\cdot \ln 8}\right)$$

Answer 3

Fue demostrado en la respuesta en: ¿la fórmula $\sqrt{ 1 + 24n }$ ceda primer?

que la expresión no genera los números primos. Allí no es cualquier expresión algebraica conocida que genera un número infinito de números primos consecutivos. Por lo que no puede existir "más simple" tal expresión. Por supuesto hay expresiones que generan cadenas largas de números primos y luego fallaran.