Fibonacci nuevamente
La sucesión de fibonacci se define de la siguiente manera:
$f(n) =$
Empezando con el uno los primeros 10 términos de esta sucesión son:
$ F_{1} = 1,;; F_{2} = 1,;; F_{3} = 2,;; F_{4} = 3,;; F_{5} = 5,;; F_{6} = 8,;; F_{7} = 13,;; F_{8} = 21,;; F_{9} = 34,;; F_{10} = 55$
Quizás están pensando que este post trata simplemente en implementar la función en algun lenguaje de programación y entonces probablemente su primera reacción será “ya me lo se…”. ¿Pues que creen? lo que aquí les mostrare es una alternativa al calculo de los términos de fibonacci. Me refiero al número aureo o golden ratio.
$F\_{n} = \left[\frac{\varphi^{n}}{\sqrt{5}}\right]$
Donde los corchetes indican que el n-esimo término corresponde al entero más cercano. Y por supuesto, n es el término que deseamos conocer…Hey! Alto! Alto! Y ese “phi” de donde salio?, veamos, la constante φ es un numero irracional con valor aproximado de 1.618033988749894848204586834365638117720309179805762862135448622705260 el cual se obtiene de la siguiente fórmula:
$\varphi = \frac{1 + \sqrt{5}}{2}$
Es probable que halla muchas dudas al respecto de φ, yo las tengo. Desafortunadamente yo no puedo explicarles eso así que checar aquí para mas información.
Veamos un ejemplo. Sabemos que F_10 = 55, y según la fórmula:
$F\_{10} = \left[\frac{\varphi^{10}}{\sqrt{5}}\right] \approx 55.0036361232 \rightarrow 55$
Encontré esta razón en los foros de projecteuler.net después de resolver el problema 25 por fuerza bruta y me llamo mucho la atención la solución tan elegante con esta propiedad. Acá les dejo el problema para que practiquen.
La sucesión de Fibonacci se define por la siguiente relación recurrente.
Fn = Fn-1 + Fn-2, donde F1 = 1 y F2 = 1.
Por ende los primeros 12 términos son:
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55
F(11) = 89
F(12) = 144
El 12th término, F(12), es el primer término que contiene 3 dígitos.
¿Cual es el primer término el la sucesión de fibonacci que contiene 1000 dígitos?
www.projecteuler.net Problem 25.
#Referencias [1] ProjectEuler.net, foro del problema 25. [2] Número aureo, Wikipedia.