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.

jueves, 14 de noviembre de 2019

Relaciones entre PHI(n) y TAU(n)



Función TAU

Las funciones PHI y TAU, aplicadas a un número entero positivo, tienen algo de complementarias. La segunda, TAU, cuenta los divisores de un número N. También es llamada función divisor, o D(x). En el caso de un número primo p, es claro que los divisores son 1 y p, luego la función TAU valdrá 2 en este caso. 

Igualmente, es fácil deducir que para potencias de un número primo, pk, TAU(pk)=1+k

Puedes acudir  a nuestra publicación Funciones multiplicativas (http://www.hojamat.es/publicaciones/multifun.pdf)
para consultar la fórmula general.

TAU(N)=(1+a1)(1+a2)…(1+ak)
a1, a2, …ak son los exponentes de los factores primos de N.

Por ejemplo, TAU(24)=TAU(23*3)=(1+3)(1+1)=8

Efectivamente, los divisores de 24 son ocho: 1, 2, 3, 4, 6, 8, 12 y 24.

Función PHI

La función j(n) (indicatriz o indicador de Euler) es el cardinal del conjunto de elementos inversibles en Zn o bien el conjunto de números coprimos con n y menores que él contando el 1. Esta segunda versión es más clara y adecuada al estudio que vamos a iniciar: cuenta los números primos con N y menores que N, con el añadido del 1.

La función indicatriz de Euler es multiplicativa, porque si m y n son coprimos, se cumple que

j(m). j(n) = j(m.n)

Su fórmula explícita es


(pi son sus factores primos)

Por ejemplo, el número 18=32*2 posee un valor de PHI igual a 18(1-1/2)(1-1/3)=6, Podemos comprobar que los números coprimos con 18 y menores que él son: 1, 5, 7, 11, 13 y 17. En total 6.

En los números primos p el valor de PHI(p)=p-1, como es fácil deducir.

En algunos lenguajes de programación recibe el nombre de función totient.

Relaciones entre TAU y PHI

Para cualquier número natural N, los números comprendidos entre 1 y N pertenecen a uno de estos tres conjuntos:

{A} Divisores de N: los cuenta la función TAU

{B} Coprimos con N incluido el 1: los cuenta la función PHI. En ambos conjuntos se encuentra el 1, lo que hace que no sean disjuntos.

{C} Resto de números: son aquellos números r que no son divisores de N ni coprimos con él: tienen un m.c.d con N que es mayor que 1 y menor que r.

Por ejemplo, en el número 30, los conjuntos serían:

{A} = {1, 2, 3, 5, 6, 10, 15, 30}, pues 30=2*3*5 y TAU(30)=(1+1)(1+1)(1+1)=8
{B} = {1, 7, 11, 13, 17, 19, 23, 29}, y PHI(30)=30(1-1/2)(1-1/3)(1-1/5)=1*2*4=8
{C} = {4, 8, 9, 12, 14, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28}, que son 15 elementos.

La suma de los cardinales de los tres conjuntos es 31, porque el 1 está repetido, y 8+8+15=31.

Con este planteamiento se adivina que pueden existir varias relaciones distintas entre los tres cardinales. El primero lo recoge TAU y el segundo PHI. El tercero lo dejamos como complemento de los otros dos.

PHI=TAU

Según lo publicado en http://oeis.org/A020488, solo existen estos casos: 1, 3, 8, 10, 18, 24, 30.

Por ejemplo, en N=10, TAU(10)=TAU(2*5)=(1+1)(1+1)=4 y PHI(10)=10(1-1/2)(1-1/5)=1*4=4.

No debemos conformarnos con lo publicado. Puedes comprobarlo con las dos versiones sencillas para el cálculo de ambas funciones que hemos preparado con el Basic de las hojas de cálculo. Para no interrumpir el estudio, las incluimos en un Anexo.

Jud McCranie da razones en esa página de por qué no hay más soluciones, y lo probó A. P. Minin  1894 . Lo comprobamos con nuestras funciones de hoja de cálculo:




El único número primo de la lista es 3, pues TAU(p)=2  para cualquier primo, y PHI(p)=p-1. Luego ha de ser 2=p-1 y p=3.

PHI doble de  TAU

También existen pocos casos (http://oeis.org/A062516):

5, 9, 15, 28, 40, 72, 84, 90 y 120.

Con nuestras funciones tenemos:




TAU doble de PHI

Sólo hay dos casos:



Otros casos

Con PHI=TAU+1 parece que no hay ninguno, y con PHI+1=TAU, solo dos casos:



PHI múltiplo de TAU

Si solo tenemos en cuenta múltiplos propios, cuyo cociente es mayor que 1, nos aparecen muchas soluciones. Las primeras son:



Si la relación de múltiplo es a la inversa, solo aparecen las soluciones ya vistas en las que TAU es el doble de PHI.

Por último, una curiosidad:

Pitagóricos

PHI y TAU son ambos catetos de una terna pitagórica. Solo se encuentran cinco soluciones:

20, 36, 60, 100, 300

Según el siguiente cuadro, en las ternas formadas sus elementos son múltiplos de las primitivas {3, 4, 5} o {9. 40, 41}.




Esta sucesión estaba inédita, y la hemos publicado en http://oeis.org/A308664. En esa página podrás leer un razonamiento de de Giovanni Resta con el que justifica que la sucesión sea finita.


  
ANEXO

Listado de la función PHI (Basic de Excel)

Public Function euler(n)
Dim f, a, e
Dim es As Boolean

'Calcula la indicatriz de Euler de un número

a = n ‘Copia el valor de n
f = 2 ‘Inicia el listado de primos
e = n ‘Inicia el valor de PHI
While f <= a ‘Recorre los primos posibles
es = False ‘Variable que indica si hemos llegado a un divisor primo o no
While a / f = a \ f ‘Si es un factor, se va eliminando del valor de n
a = a / f: es = True
Wend
If es Then e = e * (f - 1) / f ‘Si se ha encontrado un factor primo, se incorpora a PHI
If f = 2 Then f = 3 Else f = f + 2 ‘Busca el siguiente primo
Wend
euler = e
End Function


Listado de TAU
Es muy parecido al anterior


Public Function tau(n)
Dim f, a, e, exx


a = n ‘Copia el valor de n
f = 2 ‘Inicia el listado de primos
e = 1  ‘Inicia el valor de TAU
While f <= a ‘Recorre los primos posibles
exx = 0
While a / f = a \ f
a = a / f: exx = exx + 1 ‘Incrementa el exponente del factor primo encontrado
Wend
e = e * (1 + exx) ‘Construye TAU
If f = 2 Then f = 3 Else f = f + 2
Wend
tau = e
End Function