¿Hay alguna prueba matemática de que es imposible encontrar una ecuación (algoritmo) para generar todos los números primos?

Answer 1

Hay algoritmos que eventualmente generarán cualquier número primo posible, pero no hay algoritmos que puedan generar todos los números primos.

Sin embargo, esto parece una contradicción, pero se explica de la siguiente manera:

• No puedes generarlos todos, porque nunca has terminado. Como Euclides ya probó, hay infinitos números primos: el teorema de Euclides
• Sin embargo, puede nombrar cualquier número increíblemente alto, y luego hay un algoritmo que encontrará todos los números primos por debajo de ese número, por ejemplo, con el Tamiz de Eratóstenes.

El número de primos es tan infinito como el número de enteros positivos. Ambos conjuntos son infinitamente grandes, pero son contables. Por ejemplo, al continuar este patrón:

{1,2,3,4,…

eventualmente alcanzarás cada entero positivo elegido. Pero, por supuesto, nunca los generará a todos.

Answer 2

No, principalmente porque tenemos algoritmos para generar todos los números primos (hasta que se quede sin memoria de la computadora, de todos modos). El algoritmo más simple y estúpido que puedes hacer es usar la división de prueba en cada número entero mayor que 1. Esto es terriblemente ineficiente, pero hará el trabajo. Puede finalizar el programa después de que haya encontrado cualquier primo que desee.

Para algoritmos más eficientes, Rosetta Code tiene una buena página sobre el tamiz de Eratóstenes. A continuación se vincula un algoritmo escrito en python que utiliza una cola de prioridad para realizar un seguimiento de los próximos no primos. La misma página contiene código haskell que aprovecha la evaluación diferida.

Tamiz de Eratóstenes – generador infinito de Python

Answer 3

¡Si!

Puedo demostrar que es imposible encontrar un algoritmo para generar todos los números primos, demostrando que hay infinitos números primos (y, por lo tanto, es imposible generarlos todos).

Prueba: suponga lo contrario que hay muchos primos finitos.

Luego hay [math] n \ in \ mathbb {N} [/ math] tal que [math] n [/ math] es el primo más grande.

Deje que [math] P = \ {2, 3, 5, 7,…, n \} [/ math] sea el conjunto de todos los números primos desde [math] 2 [/ math] a [math] n [/ math]. Como [math] n [/ math] es el primo más grande, todos los números en [math] \ mathbb {N} [/ math] mayores que [math] n [/ math] deben ser divisibles por algunos [math] a \ in P [/ matemáticas].

Sin embargo, puedo construir un número [math] w [/ math] que no es divisible por nada en este conjunto con la ecuación [math] w = \ left (\ prod_ {i = 1} ^ {| P |} p_i \ derecha) + 1 [/ matemáticas]

Como [math] w [/ math] no es divisible por ningún elemento en [math] P [/ math], debe ser primo.

Y dado que [math] w-1 [/ math] es divisible por [math] n [/ math], eso significa [math] w> n [/ math].

¡Pero esto contradice nuestra afirmación de que [math] n [/ math] es el mejor primo!

[matemáticas] \ por lo tanto [/ matemáticas] Por contradicción, debe haber infinitos números primos.

[matemáticas] \ por lo tanto [/ matemáticas] No puede generar todos los números primos.

Ahora, si realmente quisiste preguntar “¿Podemos demostrar que es imposible generar todos los números primos de [matemática] 2 [/ matemática] a [matemática] n [/ matemática] para algunos [matemática] n \ in \ mathbb {N} [/ math] “, la respuesta sería no , ya que ya tenemos un algoritmo para eso. Se llama El tamiz de Eratóstenes.

La diferencia es que [math] n [/ math] puede ser arbitrariamente grande, pero no infinito.