Generadores de números de Gabonacci

PorJosé A. Alonso 9-marzo-201720-marzo-2017

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

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)

1	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)

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)

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)

10 Comentarios

gabonacci :: Integer -> Integer -> [Integer]
gabonacci a b = fs
  where (xs,ys,fs) = (zipWith (+) ys fs, b:xs, a:ys)


menorGenerador :: Integer -> (Integer, Integer)
menorGenerador n = head [(a,b) | b <- [1..n]
                               , a <- [1..b]
                               , n == (head . dropWhile (<n) . gabonacci a) b]

gabonacci :: Integer -> Integer -> [Integer]

gabonacci a b = fs

where (xs,ys,fs) = (zipWith (+) ys fs, b:xs, a:ys)

menorGenerador :: Integer -> (Integer, Integer)

menorGenerador n = head [(a,b) | b <- [1..n]

, a <- [1..b]

, n == (head . dropWhile (<n) . gabonacci a) b]

Responder

-- Primera definición: consiste en ver el mínimo valor que, tras aplicar
-- f, obtenemos de los pares (a,b) con a + b = x 
menorGenerador x =  v (minimum (map f (generadores1 x)))
  where v (a,b) = (b,a)
        f (a,b) | b < a-b || a == b = (a,b)
                | otherwise = f (b,a-b)
        generadores1 x = [(x-a,a) | a <- [div x 3..div x 2]]

-- Segunda definición: probar si un cierto generador (a,b) nos lleva a x.
menorGenerador2 x = aux (1,1) (1,1) x
  where aux (a,b) (c,d) x | c + d == x = (a,b)
                          | c + d < x = aux (a,b) (d,c+d) x
                          | a < b = aux (a+1,b) (a+1,b) x
                          | otherwise = aux (1,b+1) (1,b+1) x


-- Tercera definición: se obtiene demostrando que el menor generador es
-- el par (a,b) con a+b = x y (número de oro)*a = b
-- 
-- Este par (a,b) admite mayor número de recursiones de f, y a mayor
-- número de recursiones, menor es el generador. 
menorGenerador3 x = f (a,b)
  where b = round (fromIntegral (x)/1.61803398875)
        a = x-b
        f (a,b) | a < b-a || a == b = (a,b)
                | otherwise = f (b-a,a)

-- Primera definición: consiste en ver el mínimo valor que, tras aplicar

-- f, obtenemos de los pares (a,b) con a + b = x

menorGenerador x = v (minimum (map f (generadores1 x)))

where v (a,b) = (b,a)

f (a,b) | b < a-b || a == b = (a,b)

| otherwise = f (b,a-b)

generadores1 x = [(x-a,a) | a <- [div x 3..div x 2]]

-- Segunda definición: probar si un cierto generador (a,b) nos lleva a x.

menorGenerador2 x = aux (1,1) (1,1) x

where aux (a,b) (c,d) x | c + d == x = (a,b)

| c + d < x = aux (a,b) (d,c+d) x

| a < b = aux (a+1,b) (a+1,b) x

| otherwise = aux (1,b+1) (1,b+1) x

-- Tercera definición: se obtiene demostrando que el menor generador es

-- el par (a,b) con a+b = x y (número de oro)*a = b

-- Este par (a,b) admite mayor número de recursiones de f, y a mayor

-- número de recursiones, menor es el generador.

menorGenerador3 x = f (a,b)

where b = round (fromIntegral (x)/1.61803398875)

a = x-b

f (a,b) | a < b-a || a == b = (a,b)

| otherwise = f (b-a,a)

Responder

-- Elimina los errores de menorGenerador3
menorGenerador4 :: Integer -> (Integer,Integer)
menorGenerador4 x =  (
  v.minimum.map v) ([fst (f (x-z,z) 1) | z <- [b..b+t]] ++
                    [fst (f (x-z,z) 1) | z <- [b-q..b]])
  where v (a,b) = (b,a)
        b = round (fromIntegral (x)/1.61803398875)
        a = x-b
        f (a,b) n | a < b-a || a == b = ((a,b),n)
                  | otherwise = f (b-a,a) (n+1)
        t = head [ n | n <- [1..], snd (f (a-n,b+n) 1) < snd p]
        q = head [ n | n <- [1..], snd (f (a+n,b-n) 1) < snd p]
        p = f (a,b) 1

-- Elimina los errores de menorGenerador3

menorGenerador4 :: Integer -> (Integer,Integer)

menorGenerador4 x = (

v.minimum.map v) ([fst (f (x-z,z) 1) | z <- [b..b+t]] ++

[fst (f (x-z,z) 1) | z <- [b-q..b]])

where v (a,b) = (b,a)

b = round (fromIntegral (x)/1.61803398875)

a = x-b

f (a,b) n | a < b-a || a == b = ((a,b),n)

| otherwise = f (b-a,a) (n+1)

t = head [ n | n <- [1..], snd (f (a-n,b+n) 1) < snd p]

q = head [ n | n <- [1..], snd (f (a+n,b-n) 1) < snd p]

p = f (a,b) 1

Responder

-- menorGenerador :: Integer -> (Integer,Integer)
-- gabonacci :: Integer -> Integer -> [Integer]

gabonacci x y = x : y : zipWith (+) xs ys
    where ys = tail (gabonacci x y)
          xs = gabonacci x y 

menorGenerador x = head [(a,b) | b <- [1..x], a <- [1..b],
                                 x == head (dropWhile (< x) (gabonacci a b))]

-- menorGenerador :: Integer -> (Integer,Integer)

-- gabonacci :: Integer -> Integer -> [Integer]

gabonacci x y = x : y : zipWith (+) xs ys

where ys = tail (gabonacci x y)

xs = gabonacci x y

menorGenerador x = head [(a,b) | b <- [1..x], a <- [1..b],

x == head (dropWhile (< x) (gabonacci a b))]

Responder

Sólo da resultado para los tres primeros ejemplos.

sucGabonacci (a,b) = [ g(x) | x <- [0..]]
                    where g(0) = a
                          g(1) = b
                          g(x) = g(x-1)+g(x-2)

menorGenerador :: Integer -> (Integer,Integer)
menorGenerador n = vuelta (minimum [ (b,a) | b <- [1..n],
                                             a <- [1..b],
                          n `elem` take (fromInteger n) ( sucGabonacci (a,b))])
  
vuelta (a,b) = (b,a)

sucGabonacci (a,b) = [ g(x) | x <- [0..]]

where g(0) = a

g(1) = b

g(x) = g(x-1)+g(x-2)

menorGenerador :: Integer -> (Integer,Integer)

menorGenerador n = vuelta (minimum [ (b,a) | b <- [1..n],

a <- [1..b],

n `elem` take (fromInteger n) ( sucGabonacci (a,b))])

vuelta (a,b) = (b,a)

Responder

gabonacci :: (Integer,Integer) -> [Integer]
gabonacci (a,b) = a:b:(a+b):(drop 2 (gabonacci (b,(a+b)))) 

menorGenerador :: Integer -> (Integer, Integer)
menorGenerador n = head [(a,b) | b <- [1..n]
                               , a <- [1..b]
                               , n == head (dropWhile (<n) (gabonacci (a,b)))]

gabonacci :: (Integer,Integer) -> [Integer]

gabonacci (a,b) = a:b:(a+b):(drop 2 (gabonacci (b,(a+b))))

menorGenerador :: Integer -> (Integer, Integer)

menorGenerador n = head [(a,b) | b <- [1..n]

, a <- [1..b]

, n == head (dropWhile (<n) (gabonacci (a,b)))]

Responder

gib :: Integer -> Integer -> [Integer]
gib a b= gs
  where (xs,ys,gs) = (zipWith (+) ys gs, b:xs, a:ys)

menorGenerador :: Integer -> (Integer,Integer)
menorGenerador x = aux (sucPares) 
  where aux ((a,b):ys) | pertenece x (gib a b) = (a,b)
                       | otherwise = aux ys 

sucPares :: [(Integer,Integer)]
sucPares = zip (concatMap (\n -> [1..n]) [1..])
             (concatMap (\n -> replicate (fromInteger n+1) n) [1..]) 

pertenece :: Integer -> [Integer] -> Bool
pertenece x xs = head (dropWhile (<x) xs) == x

gib :: Integer -> Integer -> [Integer]

gib a b= gs

where (xs,ys,gs) = (zipWith (+) ys gs, b:xs, a:ys)

menorGenerador :: Integer -> (Integer,Integer)

menorGenerador x = aux (sucPares)

where aux ((a,b):ys) | pertenece x (gib a b) = (a,b)

| otherwise = aux ys

sucPares :: [(Integer,Integer)]

sucPares = zip (concatMap (\n -> [1..n]) [1..])

(concatMap (\n -> replicate (fromInteger n+1) n) [1..])

pertenece :: Integer -> [Integer] -> Bool

pertenece x xs = head (dropWhile (<x) xs) == x

Responder

gabonacci :: (Int,Int)-> [Int]
gabonacci (a,b) = g(0) : g(1) : [g (n) | n <- [2..]]
  where g 0 = a
        g 1 = b
        g n = g(n-1) + g(n-2)

menorg :: Int -> (Int,Int)
menorg x =
  head [(a,b) | (a,b)<-ys x
              , null [(c,t) | (c,t) <-ys x
                            , t == b && c < a || t < b]]

ys x = [(a,b) | a <- [1..x]
              , b <- [1..x]
              , elem x (takeWhile (<=x) (gabonacci (a,b)))
              , a <= b]

gabonacci :: (Int,Int)-> [Int]

gabonacci (a,b) = g(0) : g(1) : [g (n) | n <- [2..]]

where g 0 = a

g 1 = b

g n = g(n-1) + g(n-2)

menorg :: Int -> (Int,Int)

menorg x =

head [(a,b) | (a,b)<-ys x

, null [(c,t) | (c,t) <-ys x

, t == b && c < a || t < b]]

ys x = [(a,b) | a <- [1..x]

, b <- [1..x]

, elem x (takeWhile (<=x) (gabonacci (a,b)))

, a <= b]

Responder

menorGenerador :: Integer -> (Integer,Integer)
menorGenerador n = head $ dropWhile (notElem n . f) $ [(a,b) | b <- [1..], a <- [1..b]]
  where
    f (a,b) = xs 
      where xs = takeWhile (<=n) $ a:scanl (+) b xs

menorGenerador :: Integer -> (Integer,Integer)

menorGenerador n = head $ dropWhile (notElem n . f) $ [(a,b) | b <- [1..], a <- [1..b]]

where

f (a,b) = xs

where xs = takeWhile (<=n) $ a:scanl (+) b xs

Responder

menorGenerador :: Integer -> (Integer,Integer)
menorGenerador = head.pares

gabonacci :: (Integer,Integer) -> [Integer]
gabonacci (a,b) = a : b : gabonacci (a+b,a+2*b)

pares :: Integer -> [(Integer,Integer)]
pares x = [(a,b) | b <- [1..x], a <- [1..b], x `elem` (t $ g a b)]
        where t = take $ fromInteger x
              g a b = gabonacci (a,b)

menorGenerador :: Integer -> (Integer,Integer)

menorGenerador = head.pares

gabonacci :: (Integer,Integer) -> [Integer]

gabonacci (a,b) = a : b : gabonacci (a+b,a+2*b)

pares :: Integer -> [(Integer,Integer)]

pares x = [(a,b) | b <- [1..x], a <- [1..b], x `elem` (t $ g a b)]

where t = take $ fromInteger x

g a b = gabonacci (a,b)

Responder

Generadores de números de Gabonacci

Soluciones

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico