lunes, 16 de diciembre de 2019

Cadenas de Cunningham


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

 If esprimo(p) And Not esprimo((p - 1) / 2) Then
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.

miércoles, 4 de diciembre de 2019

Números de Fortune


 A los números que vamos a estudiar se les suele llamar afortunados, pero esa denominación puede confundirse con otras parecidas, como “números felices” o “de la suerte”. Por ello los nombraremos según el primer matemático que los estudió, que fue Reo Franklin Fortune.
Para definirlos bien podemos comenzar recordando los números de Euclides. Son aquellos formados por el producto de los primeros números primos con el añadido de una unidad:
E(n)=p1*p2*p3*….*pn+1
y
Los conocimos en la demostración clásica de la infinitud de números primos, y unos son primos y otros compuestos, como 30031=59*509.
Al primer sumando en la definición se le llama primorial, y ya lo hemos estudiado en este blog
El primorial se suele representar como N#, siendo N el número de factores primos consecutivos de su producto. Por ejemplo, 4#=2*3*5*7=210.
Llamemos Q(n) al primer primo posterior al número de Euclides E(n) de orden n, es decir, posterior a n#+1.
Puede ocurrir que la diferencia P(n) = Q(n)-n# sea un número primo, y en ese caso diremos que P(n) es un número afortunado o de Fortune. Este autor conjeturó que todos ellos serían primos. Es una cuestión no demostrada aún.
Por ejemplo, 2*3*5=30 es el tercer primorial, por lo que 31 es un número de Euclides. Su primo más próximo en orden creciente es 37, y la diferencia 37-30=7 es prima, luego 7 es un número afortunado.
En siguiente página de MathWorld puedes consultar lo más importante sobre estos números.

Búsquedas
Podemos reproducir la lista de números afortunados según el orden creciente de primoriales. El inconveniente, nada grave con una hoja de cálculo, es que resultarán desordenados y duplicados, pues existen soluciones iguales para distintos órdenes. Probamos con este tipo de búsqueda. Usaremos la siguiente función:
Function fortune(n)
dim i,k,p,q,j

k=0
j=2
p=1
for i=1 to n
p=p*j ‘Los primoriales se van formando en la variable p
j=primprox(j) ‘Se añade un nuevo primo
next i
q=primprox(p+1)-p ‘Se restan el siguiente primo y el primorial
if esprimo(q) then k=q ‘Si la diferencia es prima, q es afortunado.
fortune=k
end function

La función devuelve un cero si el primo buscado no es afortunado o un número primo si lo es. Con ella podemos descubrir los primeros números de Fortune. Solo podemos llegar al orden 9 porque se produce desbordamiento:



Están publicados en http://oeis.org/A005235 de forma no ordenada y con duplicados: 3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109, 89, 103, 79, 151, 197, 101, 103,…
Para retardar el desbordamiento podemos usar la versión en PARI:

fortune(n)=my(k=0,j=2,p=1);for(i=1,n,p=p*j;j=nextprime(j));q=nextprime(p+1)-q;if(isprime(q),k=q);k
print(fortune(4))

Este sería el resultado:



No parece que el tema dé para más con las herramientas de cálculo que usamos. Si consultas el tema en otras páginas descubrirás que es una cuestión limitada.

martes, 26 de noviembre de 2019

Iteración basada en la suma de cuadrados de cifras (5) - Alcances


Alcances entre números

Una cuestión amena es la de averiguar si un número de cierto tipo (primo, cuadrado, triangular,…) es alcanzable desde otro del mismo tipo mediante una recurrencia consistente en ir sumando a cada término el cuadrado de las cifras.
Por ejemplo, 23 es alcanzable desde 11, ambos primos, porque 13=11+1^2+1^2, 23=13+1^2+3^2

Todos los números sin ningún tipo especial son alcanzables, salvo los colombianos cuadráticos, ya estudiados aquí: 1, 3, 4, 5, 7, 8, 9, 10, 14, 15, 16, 18, 19, 21, 22, 25, 27, 28,…

El resto, por ejemplo el 6 y el 12 o el 13, son alcanzables desde otro número:

2+2^2=6, 3+3^2=12, 11+1^2+1^2=13.

Además, todos los son con un solo paso, pues basta elegir el último término de cualquier recurrencia.

Pasamos entonces a estudiar diversos tipos:

Números primos

Hemos preparado una función en Excel que nos puede ayudar a decidir si un número es alcanzable en el sentido que le hemos dado a la palabra. El listado que sigue es la versión entre primos, pero se cambia fácilmente por otro tipo:

Public Function alcance$(n)
'desde el final del alcance hacia atrás para ver si alguno lo alcanza
Dim i, j
Dim s$

If Not esprimo(n) Then alcance = "NO": Exit Function 'Si no es primo, renunciamos.
s$ = "" ‘Contendrá las soluciones
i = 1
While i <= n And s = ""
If esprimo(i) Then 'Puede ser otra condición
j = i
While j < n
j = j + sumacifras(j, 2)
If j = n Then s = s + Str$(i)
Wend
End If
i = i + 1
Wend
If s$ = "" Then s$ = "NO"
alcance = s
End Function

Si no existen soluciones, devuelve un “NO” y si las hay, el conjunto de ellas. Aquí tienes la función aplicada a los números primos entre 20 y 80:



Solo son alcanzables 23, 41 y 67. Ampliamos el rango de búsqueda para confeccionar una tabla. Aquí tienes los primeros primos alcanzables:



Los puedes obtener en PARI con un algoritmo similar al de Excel:

forprime(n=1,1000,s=0;i=1;while(i<=n&&s==0,if(isprime(i),j=i;s=0;while(j<n&&s==0,j=j+norml2(digits(j));if(j==n,s=1;write1("final.txt",n,", "))));i+=1))

13, 17, 23, 41, 67, 101, 103, 107, 113, 127, 131, 157, 163, 181, 191, 199, 227, 251, 263, 269, 271, 281, 311, 379, 421, 457, 461, 467, 499, 509, 521, 541, 547, 563, …

Final de la recurrencia

Podemos plantearnos la cuestión opuesta, la de si dado un número primo, llega a alcanzar a otro primo en la recurrencia. En este tipo de cuestiones el problema que solemos tener es el de fijar una cota de búsqueda. En la sucesión A094830 se nos da una pista, pues contiene los pasos que se han de dar para cada primo.

A094830              Start with x = n, repeatedly replace x with x + sum of squares of digits of x until you reach a prime; sequence gives number of steps.                  
1, 0, 0, 6, 0, 4, 0, 11, 5, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 5, 13, 9, 0, 4, 11, 12, 17, 3, 0, 8, 0, 8, 7, 1, 7, 3, 0, 5, 7, 4, 0, 3, 0, 3, 7, 8, 0, 2, 2, 2, 6, 3, 0, 10, 2, 3, 1, 3, 0, 3, 0, 2, 2, 18, 2, 11, 0, 2, 6, 9, 0, 10, 0, 1, 1, 2, 5, 1, 0, 16, 2, 8, 0, 3, 11, 6, 10, 2, 0, 4, 1, 15, 2, 1, 9, 2, 0, 7, 7, 1

Según esta tabla, el máximo número de pasos de recurrencia para números pequeños es de 18, contando primos y compuestos. Podemos buscar, por ejemplo, hasta 25 iteraciones y marcar aquellos primos en los que ese número sea insuficiente.

Entre los primos menores que 5000 aparecen ya ejemplos en los que no basta con 25 iteraciones:

167, 191, 1709, 1783, 1831, 4229, 4421, 4621, 4787, 4793, 4817, 4969, 4993

Si aumento a 50, prácticamente todos los primos de ese rango alcanzan a otro primo:



Podemos conjeturar que siempre se alcanza un primo, pero actualmente no se sabe si es cierto o no.

Son muchos los que se repiten en la segunda columna. Llama la atención la frecuencia con la que aparecen. Con una nueva función que no vamos a insertar aquí, descubrimos que esos números provienen de muchos inicios primos en la recurrencia. Por ejemplo, 10391 proviene de 243 recurrencias distintas.

Números cuadrados

Los primeros cuadrados alcanzables por otro cuadrado son estos:

 

En la primera columna el alcanzable y en la tercera el origen de la recurrencia
Hemos adaptado la función de alcance a cuadrados

Public Function alcance$(n)
Dim i, j, m
Dim s$


If Not escuad(n) Then alcance = "NO": Exit Function 'U otra condición
s$ = ""
i = 1
m = 0
While i * i <= n And s = ""
'If escuad(i) Then 'puede ser otra condición, e incluso i=i
j = i * i
While j < n
j = j + sumacifras(j, 2)
If j = n Then s = s + Str$(i): m = m + 1
Wend
'End If
i = i + 1
Wend
If s$ = "" Then s$ = "NO"
alcance = s$
End Function

Con PARI

for(n=1,500,m=n*n;s=0;i=1;while(i<=n&&s==0,j=i*i;while(j<m&&s==0,j=j+norml2(digits(j));if(j==m,s=1;print1(m,", ")));i+=1))

Obtenemos el listado:

81, 196, 1024, 1156, 1225, 1600, 3600, 4489, 4624, 5625, 7056, 7225, 10201, 12100, 13225, 13456, 15625, 28900, 37636, 40401, 43681, 46225, 50625, 55696, …

Problema inverso

Podemos estudiar hasta donde llega cada origen. Al igual que con números primos, conjeturaremos que todos los cuadrados finalizan en otro cuadrado con un número de pasos adecuado en la recurrencia.

Hemos ido aumentando el máximo de pasos en la misma y, si llegamos a 2000 iteraciones, aún quedan estos tres al menos:

197136, 200704, 201601

Con 5000 iteraciones, los que quedan fuera se acercan a 300000:

2961841, 2965284, 2968729,…

Por último, con 10000 iteraciones, todos los cuadrados inferiores a 9000000 alcanzan a otro cuadrado. Podemos conjeturar que los cuadrados terminan alcanzando a otro cuadrado.

Triangulares

Sólo insertaremos la tabla de los primeros triangulares alcanzables por otro triangular:

Como en otros temas parecidos, una vez que hemos construido funciones para las búsquedas importantes, detenemos aquí los posibles otros casos (cubos, oblongos,…) y los dejamos como ejercicio.