Producto de Fibonaccis consecutivos
Los números de Fibonacci son los números F(n) de la siguiente sucesión
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
que comienza con 0 y 1 y los siguientes términos son las sumas de los dos anteriores.
Un número x es el producto de dos números de Fibonacci consecutivos si existe un n tal que
F(n) * F(n+1) = x
y su prueba es (F(n),F(n+1),True). Por ejemplo, 714 es el producto de dos números de Fibonacci consecutivos ya que
F(8) = 21, F(9) = 34 y 714 = 21 * 34.
Su prueba es (21, 34, True).
Un número x no es el producto de dos números de Fibonacci consecutivos si no existe un n tal que
F(n) * F(n+1) = x
y su prueba es (F(m),F(m+1),False) donde m es el menor número tal que
F(m) * F(m+1) > x
Por ejemplo, 800 no es el producto de dos números de Fibonacci consecutivos, ya que
F(8) = 21, F(9) = 34, F(10) = 55 y 21 * 34 < 800 < 34 * 55.
Su prueba es (34, 55, False),
Definir la función
productoFib :: Integer -> (Integer, Integer, Bool)
tal que (productoFib x) es la prueba de que es, o no es, el producto de dos números de Fibonacci consecutivos. Por ejemplo,
productoFib 714 == (21, 34, True) productoFib 800 == (34, 55, False) productoFib 4895 == (55, 89, True) productoFib 5895 == (89, 144, False)
Soluciones
-- 1ª solución -- =========== productoFib1 :: Integer -> (Integer, Integer, Bool) productoFib1 n | c == n = (a,b,True) | otherwise = (a,b,False) where (a,b,c) = head (dropWhile (\(x,y,z) -> z < n) productos) -- fibs es la sucesión de números de Fibonacci. Por ejemplo, -- take 14 fibs == [0,1,1,2,3,5,8,13,21,34,55,89,144,233] fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) -- productos es la lista de las ternas (a,b,c) tales que a y b son dos -- números de Fibonacci consecutivos y c es su producto. Por ejemplo, -- λ> take 7 productos -- [(0,1,0),(1,1,1),(1,2,2),(2,3,6),(3,5,15),(5,8,40),(8,13,104)] productos :: [(Integer,Integer,Integer)] productos = [(x,y,x*y) | (x,y) <- zip fibs (tail fibs)] -- 2ª solución -- =========== productoFib :: Integer -> (Integer, Integer, Bool) productoFib n = aux 0 1 n where aux a b c | a * b >= c = (a, b, a * b == c) | otherwise = aux b (a + b) c