Esta entrada se dedica a
explicar los procedimientos para estudiar las cadenas de Cunningham con ayuda
de la hoja de cálculo y del lenguaje PARI. Su definición y propiedades las
puedes consultar en
Para comenzar nuestro
trabajo, solo necesitamos conocer la generación de una cadena de este tipo:
* Elegimos un número primo cualquiera.
* Lo sometemos a la recurrencia pi+1 = 2 pi + 1 (cadena de
Cunnigham de primera especie) o bien a la recurrencia pi+1 = 2 pi - 1 (cadena de Cunningham de segunda especie) .
* Interrumpimos
la recurrencia cuando el resultado no sea primo.
Aquí solo estudiaremos las cadenas de primera especie, porque contienen
las propiedades más interesantes.
Todos los elementos de una de estas cadenas serán primos de
Sophie Germain salvo el último y todos serán primos seguros salvo el primero.
Una cadena de este tipo se llama completa si no se puede
prolongar más, tanto con términos mayores como menores. Esas son las que
estudiaremos aquí. Es fácil ver que el primer término no ha de ser “primo
seguro”, pues (p-1)/2 no pertenece a la cadena y no es primo. Igualmente, el
último no puede ser de Sophie Germain, porque 2p+1 no será primo.
En primer lugar crearemos una función que nos devuelva la cadena
de Cunningham que se puede generar a partir un número primo, aunque este no sea
el origen de una cadena completa, por ser a su vez generado por otro primo
anterior. La función posee este código:
Function cunningham$(p)
Dim s$
Dim m
s$ = "" ‘Esta variable recibirá la cadena en modo texto
If esprimo(p) Then ‘Solo se trabaja con primos
m = 2 * p + 1 ‘Primer paso en la iteración
While esprimo(m) ‘Mientras sea primo, se continua
s$ = s$ + Str$(m) ‘Se recogen los elementos de la cadena
m = 2 * m + 1
Wend
End If
cunningham = s
End Function
Con esta función es fácil ver si un número primo produce una
cadena de al menos dos elementos. Los primeros resultados son:
En esta tabla observamos algún detalle interesante:
Los inicios 2, 3, 5, 11, 23,…, como era de esperar, son primos
de Sophie Germain, en los que si p es primo, 2p+1 también lo es. Los tienes en http://oeis.org/A005384.
Los finales de cadena son primos que no pertenecen a ese tipo,
como el 7 y el 47. Vemos en la tabla cierres con 47, 107 o 167.
Las cadenas se solapan, porque 11 pertenece a una y genera otra.
Para evitar esto, la condición de que el número inicial sea primo habrá de ser
completada con la de que (p-1)/2 no lo sea (And
Not esprimo((p - 1) / 2)). De esa forma crearemos cadenas completas, sin
solapamientos. Añadimos esa condición a la función y obtenemos:
Ahora ya sí tenemos cadenas completas, en las que según la
teoría, los inicios son primos de Sophie Germain pero no primos seguros, que es
la condición que habrás leído en la teoría.
Estos inicios de cadenas los tienes en http://oeis.org/A059453.
Llama la atención que muchas cadenas solo tienen dos elementos.
Para estudiar sus longitudes bastará cambiar el código de la función, de forma
que devuelva esa variable. Podemos asignar un 0 a los números que no son
posibles inicios y después, con el mismo algoritmo, devolver las longitudes de
las cadenas en lugar de su contenido.
El nuevo código sería:
Function lcunningham$(p)
Dim s
Dim m
s = 1
m = 2 * p + 1
While esprimo(m)
s = s + 1
m = 2 * m + 1
Wend
End If
lcunningham = s
End Function
Ahora la variable s cuenta los elementos en lugar de
incorporarlos al texto. La nueva tabla sería esta:
Para estadísticas y clasificaciones es más útil que la que
devuelve un texto. La podemos traducir a PARI.
lc(p)=my(c=0,m=2*p+1);if(p==2,c=5,if(isprime(p)&&!isprime((p-1)/2),c=1;while(isprime(m),c+=1;m=2*m+1)));c
Aquí asignamos un 5 al valor 2, para sacarlo del algoritmo
general, y el resto es traducción del lenguaje de Excel.
Los inicios de la tabla anterior se pueden reproducir con
forprime(n=2,500,if(lc(n)>=2,print1(n,", ")))
Así resultan los primeros inicios:
2, 3, 29, 41, 53, 89, 113, 131, 173, 191, 233, 239, 251, 281,
293, 419, 431, 443, 491,…
Sustituyendo lc(n)>=2 por otras condiciones, como lc(n)==2, lc(n)==3,
lc(n)<5…podemos clasificar las cadenas según su longitud. Esto ya está
estudiado, por lo que nos limitaremos a comprobar algunos resultados:
lc(n)==3
Nos resultan las cadenas de longitud 3, con inicios
41, 1031, 1451, 1481, 1511, 1811, 1889, 1901, 1931, 3449, 3491,
3821, 3911,…
Están recogidos en http://oeis.org/A059762.
lc(n)==5
2, 53639, 53849, 61409, 66749, 143609, 167729, 186149, 206369,
268049, 296099, 340919, 422069, 446609,
Observamos que entre 2 y 50000 no hay soluciones. Puedes
estudiar estos números en http://oeis.org/A059764.
Si cambiamos la condición, es posible que los resultados no estén
publicados.
lc(n)>=4
2, 89, 509, 1229, 1409, 2699, 3539, 6449, 10589, 11549, 11909,
12119, 17159, 19709, 19889, 22349, 26189, 27479, 30389, 43649,…
En efecto, al menos en OEIS no se recoge esta sucesión. No
seguimos, porque se reduciría a una casuística.
Parece ser que se ha llegado a encontrar cadenas de 13 elementos
(en el momento de escribir esto probablemente se habrá sobrepasado este
número).
Con nuestras herramientas podemos encontrar los primeros números
que son inicios de cadenas de longitud ocho. Los primeros son 19099919 y
52554569.
Con la función cunningham
podemos encontrar esas cadenas:
19099919, 38199839, 76399679, 152799359, 305598719, 611197439,
1222394879, 2444789759.
52554569, 105109139,
210218279, 420436559, 840873119, 1681746239, 3363492479, 6726984959.
También hemos encontrado la primera cadena con nueve elementos:
85864769, 171729539,
343459079, 686918159, 1373836319, 2747672639, 5495345279, 10990690559,
21981381119.
Con hoja de cálculo no llegaremos más allá.
Estadísticas
Es curioso que el número de cadenas por intervalos se mantiene
casi constante. En la siguiente tabla hemos estudiado intervalos de 5000
números, tomando nota del número de cadenas y el promedio de sus longitudes:
Total de cadenas y longitud media
De 1 a 5000 597 1,20771
De 5001 a 10000 517 1,15474
De 10001 a 15000 481 1,18087
15001 a 20000 477 1,15304
20001 a 25000 462 1,13853
25001 a 30000 446 1,06867
30001 a 35000 458
1,12664
35001 a 40000 439 1,14806
40001 a 45000 433 1,13857
45001 a 50000 432 1,12269
Observamos una gran semejanza en los datos, con ligera tendencia
a disminuir.
Se observa la misma tendencia si los intervalos tienen longitud
50000:
De 50000 en 50000
De 2 a 50000 4742 1,15099
De 50001 a 100000 4180 1,13254
De 100001 a 150000 4005 1,12784
150001 a 200000 3886 1,11863
Se deja como propuesta comparar estos datos con las
distribuciones de números primos y de los de Sophie Germain.
No hay comentarios:
Publicar un comentario