La siguiente fórmula es un testeador de primalidad:
[Update: no había aclarado que los corchetes simbolizan la función "parte entera de"]
Para j > 1, vale 1 si j es primo, y 0 si j es compuesto.
Vi la fórmula en A Passion for Mathematics, de Clifford A. Pickover, que a su vez lo cita de Mathematical Mysteries, de Calvin Clawson.
Clawson dijo sobre ella: «Es verdaderamente asombrosa. ¿Cómo sabe si su argumento es primo o compuesto?»
Y realmente es asombrosa. Lástima que no es fácil de evaluar para valores grandes de j…
Julio 31, 2008 a las 5:40 pm |
Es bastante asombrosa, pero en mi hoja de cálculo, tal vez por problemas de redondeos empieza a fallar con el 19, tampoco va nada bien con 23 ni 29.
He intentado encontrar algo más sobre ella y no hay apenas menciones, ni en Mathworld ni otros sitios, es extraño, porque es muy simpática.
Creo que es obvio que no puede funcionar, pero no sabría decir por qué.
Julio 31, 2008 a las 5:47 pm |
Justamente es difícil de evaluar sin tener software de precisión ilimitada; por eso es poco práctica aún si funcionara.
Julio 31, 2008 a las 6:42 pm |
Con Mathematica se podrían comprobar muchísimos números, tiene la precisión que quieras, pero la verdad es que no parece que llegue lejos, aunque está genial.
Había algunas más sencillas de Euler que funcionaban hasta 41, pero ahora no la encuentro.
Pero bueno, no existe una «fórmula para generar números primos» como tal, ni para comprobar su primalidad, aunque esa es muy bonita.
Julio 31, 2008 a las 7:56 pm |
Pues no la conocía, pero me parece muy interesante. Permíteme que intente explicar cómo funciona:
Bueno, básicamente se trata de mirar cuando la fórmula da 0 o 1. Esto último pasará siempre que hagamos el cos² de un múltiplo de Pi. Lo cual es equivalente a que [(j-1)! + 1] / j sea un entero.
Así pues tenemos que si j divide (j-1)! + 1 la fórmula da 1 y esto equivale a que j sea primo porque (j-1)! + 1 no es divisible por ningún número menor que j y sin embargo es divisible por j. Si j fuese divisible por algún número menor que él (es decir, no fuese primo) ese divisor también lo sería de (j-1)! + 1, lo cual ya hemos visto que es absurdo.
Por otro lado no veo porqué debe dar exactamente 0 si j no es primo. Yo diría que en realidad da un número entre 0 y 1. ¿Puedes revisar este dato, por favor?
A nivel técnico basta con decir que la fórmula es elegante, pero calcular (j-1)! es tanto o más difícil que factorizar j para valores grandes de j. Maple o Mathematica pueden ser de utilidad para hacer cálculos de precisión arbitraria.
Julio 31, 2008 a las 9:50 pm |
Carlos: no aclaré que los corchetes simbolizan “parte entera”, y por eso la fórmula funciona.
¡Gracias por la explicación!
Julio 31, 2008 a las 11:17 pm |
Con razón me sonaba tanto el cociente. Proviene del teorema de Wilson.
Agosto 1, 2008 a las 12:03 am |
En Wikipedia se pueden ver más fórmulas que producen primos. Entre ellas figura la que comentamos.
Claro, no se conoce ninguna que sea eficiente, pero bueno, algo es algo
Agosto 1, 2008 a las 5:18 am |
Carlos: sí, como han dicho arriba los corchetes redondea hacia abajo (la función INT o FLOOR en las hojas de cálculo). Estos son los 38 primeros números según mi hoja de cálculo (Numbers) que pueden tener problemas de precisión
1 1,00000000
2 1,00000000
3 1,00000000
4 0,50000000
5 1,00000000
6 0,75000000
7 1,00000000
8 0,85355339
9 0,88302222
10 0,90450850
11 1,00000000
12 0,93301270
13 1,00000000
14 0,95048444
15 0,95677237
16 0,96194478
17 0,99999996
18 0,97242228
19 0,99948855
20 0,93329875
21 0,08760540
22 0,40878488
23 0,00291023
24 0,01575514
25 0,97156321
26 0,84190190
27 0,25277687
28 0,88056184
29 0,58641096
30 0,02950141
31 0,09459787
32 0,36778865
33 0,51342620
34 0,86507832
35 0,99943417
36 0,83809606
37 0,92329704
38 0,97150235
Por ej. el 6 (0,75) redondeado hacia abajo es correcto (no-primo), pero con 17 es mejor redondear el 0,999996 a 1 porque es primo. A partir de números como 19 es cuando la cosa no está tan clara, y mira 35 que es justo lo contrario (0,99943) a pesar de ser compuesto.
Agosto 1, 2008 a las 10:53 am |
Alvy: con el Mathematica funciona bien; claro que deja de ser práctica bastante rápido. Como dicen en wikipedia, hay algoritmos mucho más rápidos que testean primalidad.
Septiembre 3, 2008 a las 10:12 am |
Me encanta este blog, es muy interesante, pero ¿de donde coño habéis salido?
son todos ustedes geniales.
salu2 de un hombre de letras no numéricas.
Septiembre 3, 2008 a las 11:15 am |
Rafa: el autor de este blog es uno solo (por ahora). O sea yo, Marcos
¡Gracias por visitar!
Noviembre 27, 2008 a las 2:53 am |
Jaja, muy buena la fórmula! Como detalle a notar, para 23 y 31 también falla notoriamente (confiando en la tabla expuesta por Alvy), entre otros. Es una linda curiosidad. Para el que está interesado y aún no lo sabía, en el año 2004 se ha demostrado que el problema de decisión sobre la primalidad de un número pertenece a los problemas P (extendiendo: los problemas de complejidad polinomial en la longitud de la entrada, que en este caso se considera como la cantidad de dígitos del número ingresado). El algoritmo que lo muestra es el AKS, y pueden encontrarlo programado en C por lo pronto. Una de las páginas donde aparece es la siguiente:
islab.oregonstate.edu/koc/ece575/04Project2/Halim-Chanleudfa/Report.pdf
Saludos!
Noviembre 27, 2008 a las 8:37 am |
Gracias Gisela por el dato! Respecto a los valores de la tabla, están calculados con una herramienta de precisión fija, por eso son incorrectos. Matemáticamente la fórmula funciona perfectamente (aunque no es útil en sentido práctico).
Diciembre 1, 2008 a las 3:57 am |
Ya que estoy agrego mas datos respecto a lo que dijo Gisela. Lo interesante del caso es que el algoritmo fue descubierto por un grupo de ingenieros de la india, y no por matematicos. De hecho la matematica que se usa es relativamente elemental.
El resultado tiene interes teorico principalmente. En la practica se pueden hacer algoritmos probabilisticos mucho mas rapidos. Son mas o menos como el metodo de la moneda . En estos algoritmos se realizan ciertos calculos medio al azar que declaran al numero “probablemente primo” si no aciertan a encontrar un divisor. Aunque parezca mentira, si el algoritmo esta bien pensado le acierta casi siempre y es muy rapido. Y si quedan dudas, se puede repetir el proceso todas las veces que uno quiera hasta estar suficientemente seguro.