Fórmula de los números primos

Carta Común · N.º 266953

En matemáticas, una fórmula de los números primos es aquella que genera los números primos, exactamente y sin excepción alguna. Otra gran cuestión es qué se considera como una «fórmula» y lo 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 solo genere valores primos. La mayoría de la gente puede objetar que el término «fórmula» se restringe solamente a los polinomios. ¿Podrían usarse sumatorias, factoriales y la función piso? Si así fuera, de hecho, sí existen fórmulas para obtener 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, capaces de computar 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.

Leer en Wikipedia