¿La función Eit(x) de Beimar W. López Subia puede calcular números primos de manera consecutiva?

Parte 0: ¿El para que cosa de quién?

Esta pregunta es más complicada de lo que me esperaba, busque un poco y encontré este artículo sobre la función Eit(x)Eit(x):

Es básicamente la función indicadora de NN en RR. O dicho de otro modo, es una máquina que te dice si el número ingresado es natural o no.

En este punto iba a responder: ¡Por supuesto que no! ¡Esta función no calcula números primos, no calcula absolutamente nada! Solamente verifica si el número ingresado es natural, y eso puedes hacerlo por tu propia cuenta el 9999% de los casos.

Pero luego seguí leyendo el artículo:

Este teorema nos da una fórmula exacta para la función π(x)π(x) (No debe confundirse con el número ππ). Esta función por si sola no calcula números primos, solo te dice cuántos números primos hay debajo de un cierto número.

π(10)=4π(10)=4 porque debajo del 1010 hay 44 números primos (2,3,5,72,3,5,7)..

Pero esta función tiene una enorme importancia en distintas ramas de las matemáticas, sin ir mas lejos, tiene relación con uno de los problemas de un millón de dólares: La hipótesis de Riemann.

El problema es que esta fórmula exacta es extremadamente complicada:

Solo para mostrarte cuán complicada es, intentaré hacer un código en Python con ella:

Parte 1: Programando ando 

Primero la función Eit(x)Eit(x), si no sabes nada de programación, solo confía en mí que esta función efectivamente devolverá 11 cuando el resultado sea un número natural y 00 en cualquier otro caso.

Luego la función A(x)A(x), por si se lo preguntan, ⌈x⌉⌈x⌉ se refiere al número entero más cercano por arriba de un número dado. Por ejemplo: ⌈π⌉=4⌈π⌉=4.

Al parecer esta función da problemas si xx no es un entero:

Ahora necesitamos m(x)m(x), este involucra una raíz cuadrada que es bastante costosa computacionalmente hablando… Como todo esto vaya.

m(x)m(x) parece solo dar valores bonitos para n≥2n≥2, donde nn tiene que ser un número natural.

Ahora necesitamos C(x)C(x), esto va a ser una pesadilla…

Para los entendidos en programación, esto:

Es exactamente lo mismo que esto

for(int i = 1; i <= m(x); i++){ 
} 

Así que aquí vamos…

Por cierto, como C(x)C(x) usa a m(x)m(x) en su funcionamiento interno, solamente se comporta bien con números naturales mayores que 11.

Y para finalizar la faena… Llegó la hora del pastel principal, la función π(x)π(x)

Para mi sorpresa completa, esta función no explota cuando intentas darle valores, de hecho, parece ser que da resultados que tienen sentido. ¿No?

¿Cómo chequeamos si pi(10000)pi(10000) es efectivamente 33023302? En serio hay exactamente 33023302 números primos menores que 1000010000. Bueno, este es un código estándar para buscar números primos:

Este código nos dará los números primos menores que xx, mientras que π(x)π(x) nos da la cantidad de números primos menores que xx. Intentemos comparar cuanto tarda el computador en hacer una cosa o la otra… ¿Hay forma de hacer eso?

No voy a definir π(x)π(x) otra vez… Ya pasamos por mucho. Que chingaos, lo haré manualmente.

Es hora de la verdad…

π(10000)π(10000) solo dice que hay 33023302 números primos (no nos dice cuales son) menores que 1000010000, y tardó 0.220.22 segundos (aprox) en hacer este cálculo.

En comparación, pri(10000)pri(10000) nos dio TODOS LOS NÚMEROS PRIMOS menores que 1000010000, y tardó 0.120.12 segundos (aprox) en hacer esto.

Ah, y podemos verificar el resultado de π(10000)π(10000) de forma sencilla:

Al principio daban los mismos valores… ¿Qué pasó?

Parte 2: Reflexiones y pensamientos finales.

Honestamente esperaba más de ti, formula horrible…

Venga, pero esto no puede ser verdad… Ahí dice TEOREMA, eso tiene que ser verdad, y de hecho en el resto del documento[1] realizan la demostración de este hecho. ¿Acaso hay un paso incorrecto?

Solo por jugar se me dio por ver cuándo π(x)π(x) fallaba para contar la cantidad de números primos…

Oficialmente 2626 es el primer número natural para el cual, el π(x)π(x) de este artículo falla miserablemente en contar la cantidad de números primos menores que 2626. Deberían añadirlo en la Wikipedia del número 2626[2].

No creo que estemos lidiando con un demente aquí, o que todo esto sea propaganda falsa, así que ¿Qué rayos está pasando?

• ¿Por que 2626 es el número más pequeño para el cuál la formula falla?
• ¿Qué quieren decir con que se ha chequeado hasta 10251025?
• ¿Este es un problema de memoria y mi computadora no es lo suficientemente potente para obtener los decimales de precisión necesarios? PERO SI HAY FUNCIONES QUE REDONDEAN EN TODAS PARTES, ¿¿PARA QUÉ NECESITARÍA DECIMALES??
• ¿Acaso hay un error entre todas las líneas de código que utilice? (esto es altamente probable).
• Si esta fórmula realmente funciona, ¿Estaremos un paso más cerca de resolver uno de los problemas del milenio?
• ¿Podría tiro al blanco cruzar el gran cañón a tiempo?

Muchas preguntas y pocas respuestas… Para los interesados en este problema en particular que quieran revisar el código utilizado, pueden encontrarlo en el siguiente GitHub:

Independientemente de si esta fórmula funciona, o si tuve un error en mi código, o quien sabe que cosa ocurrió, la respuesta a la pregunta que comenzó esta faena…

Es no, esa función no calcula números primos, cuenta números primos… Ah y no entiendo a que te refieres con consecutivos.

Chaitou :3

…

EDIT: Ahora si viene lo chido…

Oe… Psssst

¡OEEE!

Encontré algo chido, en los comentarios de este post, mire:

¡OEEE! Yo no sé programar ni usar paint, yo le hago a las mates y al anime. Necesito su ayuda pa verificar ese código.

¿Po favo?

Ud hágale no más, yo me encargo de las mates y las fuentes.

Parte 2.5: El código de Beimar vs Mi código.

Gracias. ¿Podría explicar que hacen esos códigos para los no programadores?

…

Bueno supongo que ese es un no. ¿Los vemos en acción entonces?

Espere, ¿qué? ¿No habíamos quedado en que la fórmula π(x)π(x) no servía? ¿Cómo es posible que ahora si sirva y además tarde menos que su método para hallar números primos? ¿Qué magia negra tiene este nuevo código?

¿Eh?, ¿¿¡¡Ehh!!??

…

Uh… Bueno, mientras busco la fuente del código, vamos a ver de una vez por todas si π(x)π(x) funciona o no. Pueden jugar con el nuevo código sin origen claro en el repositorio[3].

Para saber si π(x)π(x) funciona, me temo que tendremos que ir a los orígenes de esta fórmula… Estoy hablando del pdf que comenzó todo esto. Así que… Listos o no, ¡vamos con las mates!

Parte 3: ¿Cómo funciona la fórmula extraña? - El detector

Afortunadamente para nosotros, el documento explica de forma explícita cómo obtuvieron la fórmula final. Así que solo nos basta con echarle una leída…

Si… No… Este documento hace un trabajo horrible explicando sus términos… Aunque el razonamiento es claro (para alguien que mas o menos sabe de mates) la forma en la que intentan explicarlo es pésima… Así que creo que tendré que ensuciarme un poco las manos.

Imaginen que quisieran inventar una fórmula que, de algún modo, cuente cuantos números primos hay menores que un número xx. Lo que realmente queremos es un filtro para los números que no son primos… Una especie de detector que solo deje pasar a los números primos.

1,2,3,4,5,6,7, ...,x→2,3,5,7, ...1,2,3,4,5,6,7, ...,x→2,3,5,7, ...

¿Cómo conseguimos este detector?

Bueno. Una forma muy… Mala de hacerlo, es simplemente chequear para saber si cada número es primo o no. Y una de las formas de chequear si un número en particular es primo es: Ver que números lo dividen.

"Wao… Que método tan ingenioso" - Ustedes con tono sarcástico.

Pues si. Eso es lo que hace el código mas simple para saber si un número es primo o no:

¿Qué? Que no sepa programar no significa que no entienda la lógica de un lenguaje que es prácticamente inglés mezclado con mates.

Notemos que ii empieza desde el número 22 y va hasta xx. La línea que ven que dice:

if x % i == 0: 

Está agarrando el número xx y lo está dividiendo entre ii. (xx%ii) es el residuo de esa operación. (Si x=11x=11, i=4i=4 entonces xx%i=11i=11%4=34=3 porque 11=4×2+311=4×2+3, para los entendidos en mates. xx % ii es el número rr tal que x≡rx≡r (modi)(modi)).

Si intentas dividir un número primo por un número más pequeño, el residuo obviamente no será 00, así es como puedes estar seguro de que el número es primo. Ese código simplemente intenta con todos los números más pequeños que xx a ver si para alguno el residuo es 00. No es lo mejor que hay pero es una estrategia.

Este detector podría servir. Puesto que limpia todos los números que no son primos:

1, 2, 3, 4, … →primo(x)→→primo(x)→ 2, 3, 5, 7, …

Pero obviamente este detector es malísimo. Puesto que tendríamos que pasar por chequear el residuo muchas veces. Y cuando los primos son grandes (como el 333331333331) eso significa que tendremos que chequear muchísimas veces (333330333330) solo para saber si ese número en particular es primo o no. Ahora imagínate cuántas veces necesitamos chequear algo para saber cuantos números del 11 al 33333313333331 son primos.
Nosotros queremos un detector que sea rápido para poder probarlo en todos los números menores a xx. Aquí es donde viene la genialidad de la idea sugerida en el documento.

En ese triángulo rectángulo, pp es un número primo. Y por el teorema de Pitágoras tenemos que h2=p2−1h2=p2−1. Lo importante de esto es que ese hh NUNCA SERÁ UN NÚMERO PRIMO si pp es un número primo impar. Es también sencillo ver por qué:

Si pp es impar, p2p2 es impar.

impar−1=parimpar−1=par

h2=p2−1=parh2=p2−1=par

h2h2 es par, hh es par.

Aunque claro, si intentamos usar esto como filtro obtendríamos un filtro muy pobre:

1, 2, 3, 4, 5, 6, 7, 8, 9, … →→ h2h2 NO es primo →→ 1, 3, 4, 5, 6, 7, 8, 9…

Un filtro pésimo diría yo. El artículo dice: No te preocupes, Solamente mira la lista de valores que obtienes para los números primos, luego nos encargaremos del detector.

El artículo dice: Vamos a crear una nueva máquina que nos de estos valores para los números naturales, es decir:

5, 7, 11, 13, 17… →p2−1→→p2−1→ 24, 48, 120, 168, 228

Vamos a crear una nueva máquina que haga esto:

1, 2, 3, 4, 5, … →→ Nueva máquina →→ 24, 48, 120, 168, 228, …

Por el poder del guion, ellos dicen que la máquina es esta:

Aunque si las comparas, hay algunos errores:

¡Así que vamos a arreglarlos!

Vamos Google… Necesito la fuente pa que este we me colabore con sus dibujos chidos y el código…

################################

Parte 4: ¿Cómo funciona la fórmula extraña? - Arreglando la nueva máquina.

¿Para qué hicimos la nueva máquina en primer lugar? Bueno… Suponiendo que la nueva máquina y h2=p2−1h2=p2−1 dieran los mismos valores, ¡podríamos hallar una fórmula para el ii-ésimo número primo!

h2=e2h2=e2

p2−1=−(3+6i)(−1)i+18i2+18i+32p2−1=−(3+6i)(−1)i+18i2+18i+32

p=1+−(3+6i)(−1)i+18i2+18i+32−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√p=1+−(3+6i)(−1)i+18i2+18i+32

Lo del lado derecho es una expresión fea, pero si funcionara, nos daría tendríamos una máquina para obtener todos los números primos (excepto el 22 y el 33). Eso es mejor que un detector.

1, 2, 3, 4, 5, 6, … →1+−(3+6i)(−1)i+18i2+18i+32−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√→→1+−(3+6i)(−1)i+18i2+18i+32→ 5, 7, 11, 13, 17, 19, …

Pero… No sirve:

1, 2, 3, 4, 5, 6, 7, 8, 9 … →1+−(3+6i)(−1)i+18i2+18i+32−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√→→1+−(3+6i)(−1)i+18i2+18i+32→ 5, 7, 11, 13, 17, 19, 23, 25, 29…

No sé que magia negra usaron para simplificar esa expresión, pero bueno.

En la tabla de abajo podemos ver que para algunos valores, el resultado de la fórmula no es un número primo… Esto es bastante obvio porque supusimos que e2e2 y h2=p2−1h2=p2−1 siempre iban a dar los mismos resultados… Lo cual resultó no ser cierto al final.

Pero miren los resultados que nos lanza la función cuando no es un número primo. Hay algunos múltiplos de 55, hay un par de múltiplos de 77, ¿Acaso obtendremos múltiplos de todos los números primos mayores a 33? Si es así, ¿Podemos predecir de antemano que valores darán múltiplos de un número primo en lugar de un número primo? La respuesta (a todo) es que sí:

Notemos que aquí p2−1p2−1 es simplemente el h2h2 del triángulo de antes. ¿Siempre será divisible por 3? Sip, Y la demostración también es sencilla.

• pp es un número primo NO divisible por 3.
• Cada 3 números consecutivos, al menos uno de ellos es divisible por 33. (Ejemplo: 41,42,4341,42,43).

p2−1=(p−1)(p+1)p2−1=(p−1)(p+1)

p−1,p,p+1p−1,p,p+1 son 33 números consecutivos. Y pp NO es divisible por 3. Esto implica que p−1p−1 ó p+1p+1 es divisible por 33. (Ejemplo: 16,17,1816,17,18).

Como p−1p−1 o p+1p+1 es divisible por 33, (p−1)(p+1)(p−1)(p+1) es divisible por 33 (Ejemplo: Como 1616 o 1818 es divisible por 33, 16×1816×18 es obviamente divisible por 33). Lo que significa que p2−1=h2p2−1=h2 es divisible por 33.

Por esta razón es que excluimos al número primo 33. En fin, teniendo este valor inicial podemos calcular todos los valores que nos darán múltiplos del primo en el que estamos interesados. Solo necesitamos dos números correctores a los cuales llamaré AA y BB:

Uno supondría que esto solo es útil si pp es un número primo y que todo lo que hemos hecho hasta ahora es inútil porque no tenemos una fórmula para números primos… Perooooo.

Como tenemos una máquina MM que convierte los números de toda la vida en números primos (esta máquina tiene errores), podemos usar esta máquina para encontrar qué valores no nos darán números primos, y así evitar usar esos valores. Por ejemplo:

• Para el número primo 5, el número j1=8=52−13j1=8=52−13 nos dará un múltiplo de 55 cuando lo metamos a la máquina. Así que ya sabemos que M(8)M(8) NO es un número primo. Sin necesidad de calcularlo. Por el poder del guión podemos hallar los correctores A=3A=3 y B=7B=7 para encontrar todos los valores que darán un múltiplo de 55 al meterlos a la máquina:
• j2=j1+A=8+3=11j2=j1+A=8+3=11
• j3=j2+B=11+7=18j3=j2+B=11+7=18
• j4=j3+A=18+3=21j4=j3+A=18+3=21
• j5=j4+B=21+7=28j5=j4+B=21+7=28
• Esto nos da UN FILTRO para los números que podemos meter a la máquina generadora de primos.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … →→ Filtro del número primo 55 →→ 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, …

Así nos aseguramos de nunca obtener un múltiplo de 5 al pasar estos números por la máquina MM. Si repetimos esto con todos los números primos, obtendremos el filtro definitivo:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … →→ Filtro del número primo 55 →→ 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, …

1, 2, 3, 4, 5, 6, 7, 9, 10, 12 →→ Filtro del número primo 77 →→ 1, 2, 3, 4, 5, 6, 7, 9, 10, 12… Filtrados del 5 y del 7

Luego pasamos estos filtrados por el filtro del 1111, del 1313, etc. Y así obtendremos la lista definitiva: Los números generadores de primos.

1, 2, 3, 4, 5, 6, 7, 9, 10, 12, … →→ Máquina MM →→ 5,7,11,13,17,19,23,275,7,11,13,17,19,23,27 TODOS NÚMEROS PRIMOS.

Pero claro, para hacer esto necesitaríamos saber de antemano una fórmula para calcular todos los números primos, y así usarlos para el filtro… ¿No? ¡Pero ya tenemos una fórmula que nos da números primos! Solo tenemos que corregirla:

Podemos usar esta misma fórmula para hacer los filtros, así:

1, 2, 3, 4, 5, … →→ Maquina MM →→ 5, 7, 11, 13, … →→ Generador de filtros →→ Filtro del 55, Filtro del 77, Filtro del 1111, Filtro del 1313.

Teniendo los filtros, podemos volver a la lista original de números, y usar los filtros en la lista para obtener una lista refinada.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12… →→ Filtros de números primos →→ 1, 2, 3, 4, 5, 6, 7, 9, 10, 12…

Ahora repetimos el proceso pasando esta lista refinada por la máquina MM para obtener más números primos, con los cuales obtendremos más filtros con los que podremos refinar aún más la lista, etc.

Si me lo preguntan, es bastante astuto usar MM para corregir la lista que se le dará a MM. No es un enfoque tradicional pero es muy buena idea.

¿Podemos obtener una fórmula compacta para los filtros de los números primos? Sip:

No entraré mucho en detalles. Pero básicamente j(i,m)j(i,m) es el número jmjm del filtro del primo ii-ésimo… Es decir:

• j(1,1)=8j(1,1)=8 porque 88 es el primer número en el filtro del primo M(1)=5M(1)=5
• j(1,m)j(1,m) sería el número jmjm del filtro del primo M(1)=5M(1)=5, o sea que los valores de j(1,2),j(1,3),j(1,4),j(1,5)j(1,2),j(1,3),j(1,4),j(1,5) coinciden con estos:

Con esta nueva fórmula, tenemos una forma de generar todos los números que NO NOS SIRVEN, y así tirarlos a la basura para dejar solo los que si nos sirven.

Donde carajo estará esa fuente… Solo encontré una explicación[4] pero no aparece el código… Vamos necesito código e imágenes.

################################

Parte 5: ¿Cómo funciona la fórmula extraña? - Completando la fórmula para encontrar primos.

Ya casiiiiiii.

Recordemos que estábamos en la búsqueda de un filtro que de entre todos los números solo dejara los primos. Queríamos un filtro que fuera rápido para poder usarlo en todos los números menores que un xx fijo. Entre tanto y tanto llegamos a que, mejor que un filtro, podíamos tener una máquina MM que generara los números primos siempre y cuando corrijamos los números que se deben ingresar en MM.

Tenemos una fórmula j(i,m)j(i,m) para los números que NO NOS SIRVEN para la máquina MM, y queremos usar esto de algún modo para dejar solo los que si nos sirven.

Pueden tomar un descanso, irse por unas papas o maiz, tomar algo de agua y felicitarse si han llegado hasta aquí. Si es su primera leída pueden felicitarse aún más, porque no me imagino la cantidad de información que este post ya tiene (por eso quería que alguien hiciera otra pregunta sobre el tema, porque esta ya tiene mucha info xd). Una vez estén listos para continuar, podemos seguir con esto…

…

Yo esperaré, tranquilos…

…

…

..

.

¿Ya?

Okey. Vamos a terminar con esto de una vez por todas.

Si tu me das un número kk cualquiera, puede ser 3333, 101101, 88, 12832914101283291410, o lo que sea. Estamos completamente seguros de que ocurrirá una de estas dos cosas:

• M(k)M(k) es un número primo. En cuyo caso podemos dormir tranquilos.
• M(k)M(k) NO es un número primo, lo que significa que kk es un número que NO NOS SIRVE, pero eso significa que kk debe poderse obtener con la fórmula de números que no nos sirven. Es decir: k=j(i,m)k=j(i,m).

Recordemos que no queríamos una fórmula para todos los números primos. Solo una que cuente los números primos menores a xx. Digamos, menores a 100100 o 10001000 o lo que sea (nuestra π(x)π(x)). Esto significa que en lugar de mirar a los infinitos valores que NO NOS SIRVEN, podemos limitarnos a ver los valores que no nos sirven y que M(k)M(k) sea menor que xx. Esto hace que la lista de valores que no nos sirven sea finita. Y así no tengamos que refinar para siempre.

Esto significa que hay un valor que NO NOS SIRVE que es el mayor de todos (Este máximo se llama jfjf en el documento). (Al pasar este valor por la máquina MM, obtendremos algo menor a nuestro xx claro). Si quisiéramos filtrar todos los valores que NO NOS SIRVEN solo necesitamos chequear los números del 11 hasta este valor en la máquina MM, y así veremos rápidamente cuales no son primos y los descartaremos. Así, el total de números primos menores que xx será la cantidad de valores que SI NOS SIRVEN.

Y la cantidad de valores que SI NOS SIRVEN es igual a la cantidad de valores que nos podrían servir menos la cantidad de valores que NO NOS SIRVEN.

Pues bien, la C(x)C(x) del código de la pregunta debería contar los valores que NO NOS SIRVEN.

Y así, π(x)=jf−C(x)+2π(x)=jf−C(x)+2, porque if=jf+1if=jf+1 es la cantidad de valores que nos podrían servir (recordemos, jfjf es el máximo número que NO NOS SIRVE y que M(jf)M(jf) sigue siendo menor a nuestro xx). Y la lista de valores que nos sirve al pasarlos por la máquina MM nos dará todos los números primos desde el 55 hasta el xx. Como nos falta contar dos números primos, añadimos 22 al contador y badaboom badabang, ¡tenemos la fórmula final!

Donde C(x)C(x) es… Una barbaridad valla.

Así que en principio, esta formula debe servir, fue diseñada para servir. Me salté muchos detalles al final porque las cosas se empiezan a volver bastante feas, pero el punto es que, esta fórmula esta hecha para servir simplemente porque empieza con algo sencillo (el h2h2 del triángulo que empezó este tormento) y lo corrige hasta un punto donde solo los números primos pasan el filtro… El filtro utiliza la función Eit(x)Eit(x), la que te decía si un número era natural o no. Pueden imaginarse el proceso completo algo así:

Dado xx, primero calculamos el máximo que podría fallar y el máximo que podría servir, jfjf e ifif

Luego:

1, 2, 3, 4, …, ifif →→ Máquina MM →→ 5, 7, 11, 13, …, 25, …, jfjf

Habrán algunos errores en esta nueva lista, algunos números que no son primos. Debemos sacarlos con un filtro:

5, 7, 11, 13, …, 25, …, jfjf →→ MáquinaMisteriosaDelGuión →→ 304, 4171, 4819231, 1231, …, 148531.1283919, …

Este filtro siempre dará un número decimal para los errores. Los números que no son primos y vienen de la máquina MM. Eso significa que, cuando pasemos esta nueva lista por la función EitEit obtendremos un 11 por cada número primo entre 11 y xx:

304, 4171, 4819231, 1231, …, 148531.1283919, … →Eit(x)→→Eit(x)→ 1, 1, 1, 1, …, 0, …

Así que si sumamos todos estos unos. Obtendremos la cantidad de números primos entre 55 y el xx. Como nos comimos el número primo 2 y 3, debemos sumar 22 al resultado final y. Badaboom badabang, tenemos la cantidad de números primos menores que xx.

Pero si esta fórmula fue diseñada para funcionar. ¿Qué pasó con el código que la intentaba utilizar? ¿Por qué fallaba?

¿Hay algo en este nuevo código que no tiene fuente de origen que es distinto a lo que hemos visto aquí? ¿Tendremos el chance de que el we que dibuja y programa se despierte para explicarnos cómo funciona?

Quizá… Quizá no…

Una cosa es segura: Este edit no era necesario (porque la pregunta ya está resuelta) pero definitivamente había que hacerse tarde o temprano…

Chaitou :3?

Notas al pie