miércoles, 1 de junio de 2016

La permutación Yellowstone


En los últimos meses nos hemos acostumbrado a estudiar sucesiones con definiciones muy originales, como las incluidas en el documento de N.J.A. Sloane “My Favorite Integer Sequences” http://arxiv.org/abs/math/0207175

En esta de hoy se comienza con los valores a(1)=1, a(2)=2 y a(3)=3, y los siguientes a(n) son los números naturales más pequeños que aún no hayan aparecido en la sucesión y que tengan algún factor común con a(n-2) y ninguno con a(n-1).

Para entenderlo bien podemos ir generando términos según la definición. A 1, 2 y 3 le debe seguir el 4, que es el más pequeño que comparte factores primos con el 2 pero no con el 3. Tenemos ya 1, 2, 3 y 4.

El siguiente no puede ser 5, 6, 7 ni 8. Deberá ser el 9, que comparte el factor 3 con el 3 y ninguno con el 4. Así podemos seguir generando, hasta completar:

1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7, 10, 21, 20, 27, 22, 39, 11, 13, 33, 26, 45, 28, 51, 32, 17, 18, 85, 24, 55, 34, 65,…( http://oeis.org/A098550)

Esta sucesión no es creciente, y algunos números tardan en aparecer, como el 10. Se llama permutación porque se ha demostrado que todos los números naturales aparecen una vez

 (Ver https://cs.uwaterloo.ca/journals/JIS/VOL18/Sloane/sloane9.pdf)

Más adelante comentaremos sus propiedades. Puedes consultar también el documento

http://arxiv.org/pdf/1501.01669v2.pdf

Ahora, como siempre intentamos en este blog, la intentaremos reproducir con hoja de cálculo.

Generación con hoja de cálculo

Aprovecharemos las columnas de una hoja de cálculo para simplificar el problema. La parte más pesada de la generación es averiguar si el siguiente número pertenece o no a la sucesión ya formada por k términos. Deberíamos recorrer los ya aparecidos y compararlos con el candidato nuevo. Se tarda bastante cuando ya existen muchos términos, y es conveniente simplificar.

Para que las comparaciones sean más rápidas dedicaremos la primera columna A de una hoja a llevar cuenta de los términos que ya han salido. Escribiremos un 1 en la fila k si ya ha aparecido un término con valor k, y la dejamos en blanco si aún no ha aparecido. Así, si analizamos un nuevo candidato, no hay que recorrer un conjunto, sino ir a su fila directamente. En la imagen vemos en la columna B los términos que van saliendo, y en la columna A un 1 en las filas correspondientes a dichos elementos:



Como el 14 y el 15 ya pertenecen a la sucesión, en las filas 14 y 15 figura un 1. La 10 está vacía porque aún no ha aparecido el 10 como término válido. Analiza bien los distintos valores de ambas columnas.

El averiguar si ya ha salido un número o no se puede resolver con esta función:

Function esta(m)
If ActiveWorkbook.Sheets(1).Cells(m, 1).Value = 1 Then esta = True Else esta = False
End Function

Si en la celda Cells(m, 1) hay escrito un 1, declaramos esta = True y false en caso contrario. Esto simplifica mucho el proceso y le da más rapidez.

La segunda parte, el que posea factores comunes con a(n-2) y no los posea con a(n-1) se resuelve con el MCD. Si este es mayor que 1, existen factores comunes y si es 1, no, y los términos son primos entre sí.

El Basic VBA lo resolvemos así: mcd(m, a) > 1 And mcd(m, b) = 1

Teniendo en cuenta estas dos consideraciones, el resto del algoritmo se reduce a borrados de celdas, estructuras de control y demás. Lo puedes estudiar en nuestra hoja yellowstone.xlsm, alojada en la dirección

http://www.hojamat.es/blog/yellowstone.xlsm

En ella, para comprobar que esta sucesión recorre todos los números naturales (por eso la llamamos permutación además de sucesión), permitimos que se escriba un entero (no debe ser muy grande por la limitada velocidad del algoritmo) y la sucesión se desarrolle hasta llegar a ese número.

En la imagen hemos deseado llegar hasta el 12:


Disponemos de un botón para borrar datos previos y otro para iniciar la sucesión. En efecto, al pulsar este, en la columna B aparece la sucesión Yellostone hasta el 12:


Los términos aparecen en la columna B y los lugares ya ocupados, mediante un 1, en la A.

Descarga la hoja si te apetece y busca valores algo mayores, para descubrir en qué número de orden aparecen en la sucesión y observarás que la columna A se va llenando de unos.

Por ejemplo, el 540 no aparece hasta el término 590


Esto significa que han aparecido unos 50 términos mayores que él antes de que se incorpore él mismo. Para quienes no deseen descargar la hoja y sólo estudiar el proceso, incluimos el código utilizado. En otras entradas comprobaremos algunas otras propiedades de esta sucesión.

Public Function mcd(a1, b1)
Dim a, b, r

'Halla el MCD de a1 y b1

r = 1
a = a1
b = b1
If b = 0 Then b = 1
If a = 0 Then a = 1
While r <> 0
r = a - b * Int(a / b)
If r <> 0 Then a = b: b = r
Wend
mcd = b
End Function
Function esta(m)
If ActiveWorkbook.Sheets(1).Cells(m, 1).Value = 1 Then esta = True Else esta = False
End Function

Sub sucesion()
Dim n, k, b, c, m, i


Call borrado
n = ActiveWorkbook.Sheets(1).Cells(6, 9).Value
a = 2: b = 3:  k = 3
ActiveWorkbook.Sheets(1).Cells(1, 2).Value = 1
ActiveWorkbook.Sheets(1).Cells(2, 2).Value = 2
ActiveWorkbook.Sheets(1).Cells(3, 2).Value = 3
ActiveWorkbook.Sheets(1).Cells(1, 1).Value = 1
ActiveWorkbook.Sheets(1).Cells(2, 1).Value = 1
ActiveWorkbook.Sheets(1).Cells(3, 1).Value = 1
While k < 10 ^ 5 And b <> n
m = 3
While esta(m): m = m + 1: Wend

While Not (mcd(m, a) > 1 And mcd(m, b) = 1) And m < 10 ^ 5
m = m + 1
While esta(m): m = m + 1: Wend
Wend

a = b: b = m: k = k + 1
ActiveWorkbook.Sheets(1).Cells(k, 2).Value = m
ActiveWorkbook.Sheets(1).Cells(m, 1).Value = 1
Wend

End Sub

Curiosidades

Ya conocemos la definición de esta sucesión y cómo generarla con hoja de cálculo. Ahora desarrollaremos alguna propiedades, la mayoría tomadas de la página http://oeis.org/A098550
En primer lugar, bueno será el estudio gráfico de la evolución de esta sucesión:



Los datos están tomados del ejemplo de la entrada anterior, términos hasta que aparezca el 540. Vemos una línea de tendencia lineal clara (en realidad, se ha visto que no es lineal), un poco por debajo de los números de orden, con otra línea de más pendiente algo difusa, además de casos aislados situados superior e inferiormente. Si esta sucesión recorre todos los valores, cada uno elegido en la escala del eje Y se corresponderá con un punto del gráfico. Parece ser que el nombre de Yellowstone proviene de este gráfico, en el que las imágenes más pequeñas corresponden a los números primos, el núcleo central contiene bastantes alternancias entre pares e impares, mientras que surgen picos semejantes a los chorros aleatorios de materia de un geyser. Muchos de estos picos aparecen dos unidades más tarde que los primos. Vemos un corte con más detalle:



Aquí los mínimos se sitúan en los valores primos 5, 7, 11 (junto al 13) y 19, mientras que los “chorros” o picos corresponden a 85, 91 y 95. Nos referimos a valores, no a números de orden.

Infinitud de la sucesión

Para demostrar que la serie es infinita bastará mostrar que dados un a(n-2) y a(n-1), el conjunto de candidatos a ser el siguiente número, no está vacío. En efecto, basta elegir el valor a(n-2)*p, siendo p un número primo mayor que a(n-1). Si ese conjunto no está vacío, siempre existirá un término posterior a los dados, y la sucesión será infinita. Por una razón similar, en cada tres términos consecutivos ha de haber al menos un número compuesto, pues tres primos consecutivos no cumplirían la definición.

Dentro de esta sucesión infinita los primeros primos aparecen en su orden natural, como podemos comprobar en esta lista

1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7, 10, 21, 20, 27, 22, 39, 11, 13, 33, 26, 45, 28, 51, 32, 17, 18, 85, 24, 55, 34, 65, 36, 91, 30, 49, 38, 63, 19, 42, 95, 44, 57, 40, 69, 50, 23, 48,…

No se ha podido demostrar esta conjetura para todos los primos.

Puntos fijos

Una cuestión curiosa es averiguar qué números aparecen en un número de orden igual a ellos, es decir, que a(n)=n. Hasta ahora sólo se han encontrado estos:
1, 2, 3, 4, 12, 50, 86 (http://oeis.org/A251411)

Se ha intentado hasta 10^8 sin conseguir otro más. Con nuestra hoja de cálculo podemos comprobar alguno. En la imagen tienes el correspondiente al 86: