Hay una función de $f : \mathbb N \rightarrow \mathbb P$ donde $\mathbb P = \{p \in \mathbb N \mid \ p$ primer$\}$, de tal manera que $f$ es inyectiva? Se sabe que no hay tal función polinómica existe. También, yo quiero excluir a las funciones definidas como $f(n) = \text{the $n$th prime}$, que requiere uno para encontrar los números primos por adelantado.
Respuestas
¿Demasiados anuncios?
user184794
Puntos
306
¿Has oído hablar de los Molinos constante? La función se define a continuación, con $A$ siendo los Molinos constante, siempre da un prime:
$$f(n)=\left\lfloor A^{3^n}\right\rfloor$$
Sasho Nikolov
Puntos
451
Viniendo de la informática teórica, me gustaría formalizar su pregunta como
Hay un bijection $f: \mathbb{N} \to P$, de modo que $f(n)$ puede ser calculado en tiempo polinomial en $\lceil \log_2 n\rceil$ (el número de bits de $n$)?
Esta es una forma estándar para formular tales "explícito de indexación preguntas. El requisito de que $f$ ser eficientemente computable es una versión fuerte de exigir que $f$ es "explícito". También excluye las cosas como la informática de todos los números primos hasta el $n$.
La pregunta arriba mencionada es ciertamente abierto! El resultado más cercano que yo sé que es un trabajo reciente que muestra cómo explícitamente índice de polinomios irreducibles de un determinado grado de licenciatura en un campo finito. Dichos polinomios son los "primos" en el anillo de polinomios, pero tienen mucho más la estructura de los números primos en el anillo de los números enteros.
barak manos
Puntos
17078
Aquí es algo que he establecido hace mucho tiempo.
La respuesta a tu pregunta es $P_n$, pero por favor tenga en cuenta que se trata de "cómputo de valor".
Es $n$ primer:
$$F_n=\left\lfloor\frac{\left(\sum\limits_{k=2}^{n-1}\left\lceil\frac{{n}\bmod{k}}{n}\right\rceil\right)+2\cdot\left\lceil\frac{n-1}{n}\right\rceil}{n}\right\rfloor$$
Cuántos números primos hasta $n$:
$$G_n=\sum\limits_{k=2}^{n}F_k$$
¿Cuál es el $n$th el primer número:
$$P_n=\sum\limits_{k=n}^{n^2+1}{k}\cdot{F_k}\cdot\left(1-\left\lceil\frac{(G_k-n)^2}{(G_k+n)^2}\right\rceil\right)$$
Kendall
Puntos
768
No podemos descartar completamente la posibilidad de que un "simple" y "natural" existe una función que muy rápidamente se enumera una (posiblemente muy delgada) infinito subconjunto de los números primos.
Por ejemplo, no se sabe si en catalán de los números de Mersenne son todos los números primos, 2, 3, 7, 127, 170141183460469231731687303715884105727, ... (OEIS A007013). Sería una tremenda sorpresa si lo fueran.
La práctica de una competencia para encontrar la más grande que se conoce el primer, y premios como el FEP Cooperativa Premios Computing, perdería todo sentido si alguien pudiera probar que todos los catalanes–los números de Mersenne son los principales.
No he oído hablar de cualquier matemático creer que los grandes números primos se puede encontrar fácilmente.
DRF
Puntos
2587
La reformulación por Sasho Nikolov parece tener más sentido. Aunque usted probablemente puede caer el bijection requisito.
De lo contrario, la respuesta a la pregunta original, como se dijo, es que sí. Hay al $\mathfrak{c}$-muchos inyectiva funciones de $\mathbb{N}$ $\mathbb{P}$puesto que ambos conjuntos en cuestión tiene el tamaño de $\aleph_0$.
Incluso hay computable tales funciones (desde decidir si un número es primo no sólo es computable, pero en realidad en P).
Mientras escribo esto me pregunto si un poco de trabajo, utilizando un poco de conocimiento sobre el primer densidad y la poli tiempo determinista primalidad armario no se podía casi P algoritmo acaba por encontrar el más cercano prime a un seleccionados adecuadamente el poder de $n$.
El siguiente viene a la mente; calcular $n^{2}$, el uso de poli tiempo de primalidad armario para comprobar $n^2+i$ de primalidad para $i>1$. Para cada una de las $i$ este es entonces el polinomio en $\log_2(n)$, y dado que $$\lim_{x\rightarrow\infty}\frac{\pi(x)}{x/\ln(x)}=1$$ assymptotically the number of $i$'s de la prueba también será polinomio .
Tan lejos como puedo decir esto para dar un inyectiva polinomio de la función de hora de$\mathbb{N}$$\mathbb{P}$. Si alguien ve un problema por favor comente.
