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.