lunes, 30 de noviembre de 2015

Primos de Fibonacci


Hoy estudiaremos otra conjetura bastante popular:

Existen infinitos números de Fibonacci que son primos.

Así que si construimos la sucesión de Fibonacci y elegimos los términos que sean primos, encontraremos uno de ellos que sea mayor que cualquier otro entero que imaginemos. Aprovecharemos esta conjetura para repasar conceptos, construir algoritmos y explicar algunas propiedades de los números de Fibonacci.

Los primeros primos de Fibonacci son estos:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497,…

(http://oeis.org/A005478)

Según la conjetura, esta sucesión debería tener infinitos términos. No es intuitivo, porque en cada aumento de índice resulta más improbable que el término correspondiente sea primo, pero así son las conjeturas, que se encuentran a veces en el término de separación entre lo imposible e improbable.

Comprobación de la conjetura

En la hoja Conjeturas
(http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#conjeturas)

dispones de las funciones necesarias para comprobar la conjetura, se entiende que en unos pocos ejemplos. La primera, ESPRIMO, ya ha sido presentada muchas veces en este blog (escribe ESPRIMO HOJA en un navegador de Internet), pero necesitamos otra,  ESFIBO, que nos indica si un número pertenece o no a la sucesión de Fibonacci. Esta función se basa en un popular criterio para saber si un número es de Fibonacci o no: Un número N pertenece a la sucesión de Fibonacci si y sólo si 5N2+4 o 5N2-4 es un cuadrado perfecto.

(Ver http://gaussianos.com/algunas-curiosidades-sobre-los-numeros-de-fibonacci/)

Según eso, ésta puede ser la función que devuelva VERDADERO si un número es del tipo Fibonacci y FALSO en el caso opuesto:

Public Function esfibo(n) As Boolean 'devuelve verdadero si N es de Fibonacci
Dim f As Boolean
Dim a

f = False
a = 5 * n * n + 4
If escuad(a) Then f = True
a = 5 * n * n - 4
If escuad(a) Then f = True
esfibo = f
End Function

Disponiendo de esta función y de la ESPRIMO, podemos construir otra, a la que llamaremos FIBOPRIMPROX, que, dado un entero positivo, devuelva el menor primo Fibonacci que es mayor que él, es decir, el “próximo primo Fibonacci”. Su código sería:

Function fiboprimprox(a) As Long
Dim p, prim As Long
Dim sale As Boolean

'Encuentra el menor primo de Fibonacci mayor que el dado
p = a + 1: sale = False: prim = 0
While Not sale
If esprimo(p) And esfibo(p) Then prim = p: sale = True
p = p + 1
Wend
fiboprimprox = prim
End Function

Se entiende fácilmente. El problema, como ocurre frecuentemente en este blog, es que la hoja de cálculo tiene una capacidad limitada de cálculo con enteros. Por ello, con la hoja CONJETURAS sólo hemos podido llegar al próximo a 100000.



Observa que los números de la segunda columna pertenecen a la sucesión de primos Fibonacci. El siguiente, 433494437, sería difícil de obtener con este procedimiento.

Si la conjetura es cierta, la función FIBOPRIMPROX(N) debe devolver un resultado por muy grande que sea N.

Como procedemos a menudo en este blog, traducimos el proceso a PARI para ver si podemos reproducir más elementos de la sucesión. Hemos optado por este código:

{for(i=1,10^4,f=fibonacci(i);if(isprime(f),print(f)))}

El resultado ha sido impresionante, porque en pocos segundos nos ha devuelto los primos contenidos en los 10000 primeros términos de la sucesión de Fibonacci:



Si en el código PARI hubiéramos pedido el valor del índice en lugar del término de Fibonacci nos hubiera resultado la sucesión:

3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677,…

Como se ve, salvo el caso del 4, todos los índices de números de Fibonacci primos son también primos. Esto se deriva de que si p divide a q, Fp también divide a Fq para p,q>=3. Así que si el número de orden no es primo, tampoco lo será el número Fibonacci correspondiente. La propiedad recíproca no es cierta. Por ejemplo, el término de índice 19, primo, es 4181=37*113, compuesto.

Divisibilidad en los números Fibonacci

La cuestión anterior da pie a que revisemos algunas propiedades interesantes que presentan los factores primos de los términos de esta sucesión.

El máximo común divisor

Los términos de la sucesión  de Fibonacci cumplen la siguiente curiosa propiedad:


Por ejemplo, si elegimos los términos 24 y 36 de la sucesión,

 F(24) = 46368 =25*32*7*23 y F(36) = 14930352 = 24*33*17*19*107, tendremos

MCD(46368, 14930352) = 144, MCD(24, 36) = 12 y F(12)=144

Por tanto, si el índice de un número de Fibonacci es primo, éste será coprimo con el anterior y el siguiente. Obviamente, esto lo cumplirán los primos Fibonacci, pero también el contraejemplo que vimos más arriba, F(19) = 4181. En la tabla verás la falta de elementos comunes con el anterior y el siguiente elemento Fibonacci.




Teorema de Carmichael

Relacionado con este tema de divisores de los números Fibonacci disponemos de este interesante teorema:

Todo término de la sucesión de Fibonacci distinto de 1, 8 y 144, posee un factor primo que no divide al anterior término.

Lo puedes comprobar en esta tabla de divisores de los términos 10 a 20:



Todo término posee un factor primo que no divide al anterior (recuerda que el segundo número de cada corchete es el exponente del factor primo).

Puede ocurrir que un factor dado no divida a ningún otro término anterior. Por ejemplo, el factor 41 de F(20) no divide a ningún término anterior. En este caso le llamaremos factor característico o primitivo. Los tienes en https://oeis.org/A001578.


jueves, 19 de noviembre de 2015

Sucesión de Golomb

Ya estudiamos en 2010 conjuntos relacionados con este matemático

http://hojaynumeros.blogspot.com.es/2010/03/jugamos-con-sidon-y-golomb.html

Hoy lo hacemos con una de sus sucesiones. Se trata de esta:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12,…

http://oeis.org/A001462

También se la conoce como sucesión de Silverman. Como ves, es no-decreciente.

Tiene una definición muy curiosa, y es que a(n) representa el número de veces que aparece n en la sucesión, si además definimos a(1)=1 e implícitamente aceptamos que cada valor  de n ocupa el mínimo número de orden posible.
Lo verás mejor si acompañamos cada valor con su índice:



La imagen de 1 es 1 por definición. La de 2 es 2 porque en la sucesión figura ese valor dos veces. También el 3 aparece repetido, por lo que a(3)=2. A(4)=3 debido a que aparecen tres cuatros, y así con todos.

Este es un ejemplo muy elegante de autorreferencia, pues se define un objeto como si ya estuviera construido, pero sólo lo podemos formar si seguimos la definición.

Si aceptamos la condición de que cada valor ocupe el primer número de orden que esté libre, y que cada nueva imagen es la menor que cumple a(n)>=a(n-1), esta sucesión es única. En efecto, nos ponemos a razonar:

A(1)=1 por definición, luego sólo existirá un 1 en la sucesión, por lo que la imagen de 2 no podrá ser 1. Según las condiciones, ha de ser 2, luego en la sucesión deberá haber un par de 2. Como hemos quedado en que se ocupan los menores números de orden, deberá quedar:


Esto significa que a(3)=2, luego también repetiremos el 3 dos veces:


Obligamos así a que el 4 y el 5 figuren tres veces:


Ya podrás seguir tú el razonamiento y completar la sucesión, que con las condiciones impuestas será única.

¿Lo podría conseguir una hoja de cálculo? La respuesta es afirmativa, y el algoritmo no es muy complejo. Necesitamos dos punteros, indi1, que recorrerá los valores de n, e indi2 que llevará la cuenta de los lugares que van quedando libres en la sucesión. Con indi1 se leen los valores, y con indi2 se escriben. Para evitar celdas vacías en los primeros valores, se rellenan el 1 y el 2. Quedará así con el Basic de las hojas:


Sub golomb()
Dim indi1, indi2, i, j, v


indi1 = 2 ‘El primer valor que se lee es el 2, en la celda (2,2)
indi2 = 2 ‘El primero que se escribe también es el 2
Cells(1, 2).Value = 1 ‘Rellenamos los dos primeros valores en las celdas (1,2) y (2,2)
Cells(2, 2).Value = 2
For i = 1 To 12 ‘Tomamos 12 valores, pero podían ser muchos más
v = Cells(indi1, 2).Value ‘Leemos el valor indicado por indi1 (que también es fila en la hoja)
For j = 1 To v ‘Escribimos tantos valores nuevos como indique v
Cells(indi2, 2).Value = indi1 ‘Todos los valores serán iguales a indi1
indi2 = indi2 + 1 ‘Avanza la escritura
Next j
indi1 = indi1 + 1 ‘Avanza la lectura
Next i
End Sub

Con esta subrutina se generará la sucesión de Golomb en la columna 2 de una hoja de cálculo:



Para mayor claridad hemos copiado los resultados en varias columnas, manualmente. Observarás que se reproducen fielmente los valores deseados.



La forma de generación de esta sucesión garantiza que a(n)<=n, ya que los valores de los números naturales aparecen “con retraso”, y cuando aparece el valor, el índice ha crecido más que él. El retraso se puede medir con la diferencia n-a(n):



Vemos que los retrasos a partir de 3 son todos positivos y crecientes.

Una propiedad elemental, pero que hay que pensar en ella un poco, es que las sumas parciales de esta sucesión coinciden con el índice de la última aparición en la sucesión del número de sumandos. Más claro: si sumo tres términos, 1+2+2=5, obtengo que la última aparición del 3 ocurrirá en el término 5. Esto es por la propia definición: el 1 aparece una vez, el 2 dos y el 3 otras dos, luego el último 3 aparecerá en el lugar 5.

La sucesión de sumas parciales es

1, 3, 5, 8, 11, 15, 19, 23, 28, 33, 38, 44, 50, 56, 62, 69, 76, 83, 90, 98, 106, 114, 122, 131, 140, 149, 158, 167, 177, 187,… (http://oeis.org/A001463) y coincide con el lugar de la última aparición de su número de orden. Así, si el quinto término es 11, ahí ocurrirá la última aparición del 5.

Según esto, si llamamos F(n) a los términos de la sucesión de Golomb y G(n) a sus sumas parciales, se cumplirá (estúdialo bien) que

F(G(n)) = n


Fórmula recurrente

Colin Mallows ha ideado una recurrencia muy atractiva para evaluar F(n):

F(1) = 1; F(n+1) = 1 + F(n+1-F(F(n)))

En hoja de cálculo las recurrencias son posibles, pero si se agota la pila de datos se puede bloquear el cálculo. Lo hemos intentado y funciona bien para los primeros términos, pero no va mucho más allá. En Basic sería

Public Function a(n)
If n = 1 Then
a = 1
Else
a = 1 + a(n - a(a(n - 1)))
End If
End Function

Con ella hemos formado esta tabla



En PARI también funciona la recurrencia, pero no merece la pena porque se va ralentizando para números grandes:

a(n)=if(n==1,1,1+a(n-a(a(n-1))))
{for(i=1,30,print1(a(i),", "))}



Aproximación asintótica

Por lo que hemos leído, no ha sido muy fácil llegar a esta expresión:


La comprobamos gráficamente



Se ve que son prácticamente indistinguibles.

lunes, 9 de noviembre de 2015

Damos vueltas a los triangulares cuadrados (2). Curiosidades.


En la anterior entrada generamos los números que son a la vez triangulares y cuadrados mediante varios algoritmos y fórmulas directas, tanto para hojas de cálculo como en el lenguaje PARI, e incluso a través de una función recursiva. En esta segunda entrada veremos algunas de sus propiedades y curiosidades sobre ellos.

Otra recurrencia

Según un comentario incluido en http://oeis.org/A001110, podemos tener en cuenta otra recurrencia a partir de n=3:



En efecto, 1225=(36-1)2/1, 41616=(1225-1)2/36, … O con hoja de cálculo:



Intenta averiguar cómo crear esta tabla siguiendo la recurrencia. La podemos expresar también como que la media geométrica entre el anterior y el siguiente a un término coincide con el cuadrado de ese término al que se le ha restado una unidad.

Una propiedad similar es que la media geométrica entre un término y el siguiente es también un número triangular. Lo tienes en esta tabla. Escribe los triangulares cuadrados e intenta después reproducirla:



En http://oeis.org/A029549 tienes estudiadas esas medias geométricas y puedes descubrir que estos números son oblongos y también su conexión con ciertas ternas pitagóricas. A partir de esta sucesión se abren tantos caminos que es mejor parar aquí.

Por otra parte, por ser cuadrados, los términos son suma de dos triangulares consecutivos, luego los triangulares cuadrados son “triangulares suma de dos triangulares consecutivos”

Raíz cuadrada

Ya que tratamos con cuadrados, sería interesante estudiar sus raíces cuadradas, que son estas:

0, 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214, 46611179, 271669860,…
(http://oeis.org/A001109)

Estos números no nos son desconocidos, pues son soluciones de la incógnita Y en la ecuación de Pell que usamos para encontrar sus cuadrados

Insertamos de nuevo la tabla que obtuvimos:



Más adelante veremos valores relacionados con la variable X.

Recurrencia entre las raíces

Al igual que sus cuadrados, estos números se pueden generar mediante una recurrencia de segundo grado. Para descubrirla operamos como en la entrada anterior

Dn=aDn-1+bDn-2+c usaremos los valores iniciales 0, 1, 6, 35, 204 para plantear:

6=a*1+b*0+c
35=a*6+b*1+c
204=a*35+b*6+c

Resolvemos

29=5a+b
169=29a+5b
169-5*29=169-145=24=4a    a=6, b=-1, c=0

Luego Dn=6Dn-1-Dn-2, que es la recursión que figura en A001109

Esta recurrencia la podemos comprobar con nuestra hoja de cálculo dedicada a ellas
http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2

Escribimos los coeficientes 6 y -1



Y obtenemos la sucesión


Orden como triangulares

Al igual que hemos estudiado las raíces cuadradas de los triangulares cuadrados, también podemos fijar la atención en su orden como triangulares.

Para ello planteamos k(k+1)/2=A(n), siendo A(n) un término de la sucesión de triangulares cuadrados. Es fácil ver que la solución será



Se generará esta otra sucesión:

1, 8, 49, 288, 1681, 9800, 57121, 332928, 1940449, 11309768, 65918161, 384199200,… (http://oeis.org/A001108)

También estos números están relacionados con la ecuación de Pell de la anterior entrada



Basta recordar que llamamos x a 2n+1. Deshaciendo el cambio en la tabla:
(3-1)/2=1, (17-1)/2=8, (99-1)/2=49, (577-1)/2=288,… y así resultarán todos.

Según OEIS, su fórmula recursiva es idéntica a la de los anteriores, pero con término independiente igual a 2:

Dn=6Dn-1-Dn-2+2

Para no cansar a los lectores nos limitamos a comprobarla.

8=6*1-0+2, 49=6*8-1+2, 288=6*49-8+2,…

Diferencias entre términos

Si restamos cada dos términos consecutivos, el resultado coincide con las raíces cuadradas de los términos de orden impar. Es una propiedad muy curiosa, pero no he encontrado ninguna demostración elemental de la misma.



En la tabla, si elevamos las diferencias al cuadrado nos resultan los términos de orden impar. Son los de color rojo enlazados con flechas. Si, además, encontráramos su orden como triangulares, sería un cuadrado (compruébalo), y ellos mismos, además de triangulares serían hexagonales. Bastante curioso, como ves.

Recurrencia directa

Lekraj Beedassy, en http://oeis.org/A001110, propone la siguiente recurrencia no lineal que sólo depende del término anterior:


Esta propiedad permite engendrar de nuevo los números triangulares cuadrados en una hoja de cálculo directamente, sin macros, y con gran rapidez, con una fórmula similar a =1+17*I5+6*RAIZ(I5+8*I5^2), donde puedes sustituir I5 por el término anterior de la sucesión.