Diferencia entre revisiones de «Fórmula de los números primos»

En [[matemáticas]], la fórmula de los números primos es una fórmula que genera los números primos, exactamente y sin excepción alguna. Otro gran acuerdo a esto es qué se considera como una "fórmula" y que no. No existe ninguna fórmula polinómica para obtener todos los números primos. Tampoco existe alguna fórmula polinómica no constante que sólo obtenga valores primos. La mayoría de la gente puede objetar que el término "fórmula" se restringe solamente a los polinomios. ¿Podría uno usar sumatorias, factoriales y la función piso? Si así fuera, de hecho, sí existen fórmulas de los números primos. Una interpretación razonable de la palabra "fórmula" es "una máquina de Turing que se detiene bajo todas las entradas". Bajo esta interpretación ciertamente existen máquinas de Turing que se detienen las cuales computan el enésimo número primo. Aun así, nadie sabe cómo calcular el enésimo número primo en tiempo polinómico. Dicho de otra forma, no se conoce alguna fórmula fácilmente computable.

 

== Funciones polinómicas ==