Generadores de números de Gibonacci
Los números de Gabonacci generados por (a,b) son los elementos de la sucesión de Gabonacci definida por
G(0) = a G(1) = b G(n) = G(n-2) + G(n-1), si n > 1
Por ejemplo, la sucesión de Gabonacci generada por (2,5) es 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, ...
Un número pertenece a distintas sucesiones de Gabonacci. Por ejemplo, el 9 pertenece a las sucesiones de Gabonacci generados por (3,3), (1,4) y (4,5).
El menor generador de Gabonacci de un número x es el par (a,b), con 1 ≤ a ≤ b, tal que (a,b) es un generador de Gabonacci de x y no existe ningún generador de Gabonacci de x (a',b') tal que b' < b ó b' = b y a' < a. Por ejemplo, el menor generador de Gabonacci de 9 es (3,3).
Definir la función
menorGenerador :: Integer -> (Integer,Integer)
tal que (menorGenerador x) es el menor generador de Gabonacci de x. Por ejemplo,
menorGenerador 9 == (3,3) menorGenerador 7 == (1,3) menorGenerador 5 == (1,1) menorGenerador 27 == (3,7) menorGenerador 57 == (4,9) menorGenerador 218 == (10,21) menorGenerador 1121 == (20,41) menorGenerador 89 == (1,1) menorGenerador 123 == (1,3) menorGenerador 1000 == (2,10) menorGenerador 842831057 == (2,7) menorGenerador 1573655 == (985,1971)
Soluciones
menorGenerador :: Integer -> (Integer,Integer) menorGenerador = head . generadores generadores :: Integer -> [(Integer,Integer)] generadores x = [(a,b) | b <- [1..x] , a <- [1..b] , pertenece x (gabonacci a b)] gabonacci :: Integer -> Integer -> [Integer] gabonacci a b = aux where aux = a : scanl (+) b aux pertenece :: Integer -> [Integer] -> Bool pertenece x ys = x == head (dropWhile (<x) ys)