Menu Close

Períodos de Fibonacci

Los primeros términos de la sucesión de Fibonacci son

   0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610

Al calcular sus restos módulo 3 se obtiene

   0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1

Se observa que es periódica y su período es

   0,1,1,2,0,2,2,1

Definir las funciones

   fibsMod                   :: Integer -> [Integer]
   periodoFibMod             :: Integer -> [Integer]
   longPeriodosFibMod        :: [Int]
   graficaLongPeriodosFibMod :: Int -> IO ()

tales que

  • (fibsMod n) es la lista de los términos de la sucesión de Fibonacci módulo n. Por ejemplo,
     λ> take 24 (fibsMod 3)
     [0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1]
     λ> take 24 (fibsMod 4)
     [0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1]
  • (periodoFibMod n) es la parte perioica de la sucesión de Fibonacci módulo n. Por ejemplo,
     periodoFibMod 3  ==  [0,1,1,2,0,2,2,1]
     periodoFibMod 4  ==  [0,1,1,2,3,1]
     periodoFibMod 7  ==  [0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1]
  • longPeriodosFibMod es la sucesión de las longitudes de los períodos de las sucesiones de Fibonacci módulo n, para n > 0. Por ejemplo,
     λ> take 20 longPeriodosFibMod
     [1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60]
  • (graficaLongPeriodosFibMod n) dibuja la gráfica de los n primeros términos de la sucesión longPeriodosFibMod. Por ejemplo, (graficaLongPeriodosFibMod n) dibuja
    Periodos_de_Fibonacci 300

Soluciones

import Graphics.Gnuplot.Simple
 
fibsMod :: Integer -> [Integer]
fibsMod n = map (`mod` n) fibs
 
-- fibs es la sucesión de Fibonacci. Por ejemplo,
--    λ> take 20 fibs
--    [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
periodoFibMod :: Integer -> [Integer]
periodoFibMod 1 = [0]
periodoFibMod n = 0 : 1 : aux (drop 2 (fibsMod n))
  where aux (0:1:xs) = []
        aux (a:b:xs) = a : aux (b:xs)
 
longPeriodosFibMod :: [Int]
longPeriodosFibMod =
  [length (periodoFibMod n) | n <- [1..]]
 
-- 2ª definición de longPeriodosFibMod
-- ===================================
 
longPeriodosFibMod2 :: [Int]
longPeriodosFibMod2 = map longPeriodoFibMod [1..]
 
longPeriodoFibMod :: Integer -> Int
longPeriodoFibMod 1 = 1
longPeriodoFibMod n = aux 1 (tail (fibsMod n)) 0
  where aux 0 (1 : xs) k = k
        aux _ (x : xs) k = aux x xs (k + 1)
 
graficaLongPeriodosFibMod :: Int -> IO ()
graficaLongPeriodosFibMod n =
  plotList [ Key Nothing
           , Title ("graficaLongPeriodosFibMod " ++ show n)
           , PNG ("Periodos_de_Fibonacci " ++ show n ++ ".png")]
           (take n longPeriodosFibMod)
Medio

7 soluciones de “Períodos de Fibonacci

  1. jaibengue
    fib :: [Integer]
    fib = 0 : 1 : zipWith (+) fib (tail fib)
     
    fibsMod :: Integer -> [Integer]
    fibsMod n = map (`mod` n) fib
     
    periodoFibMod :: Integer -> [Integer]
    periodoFibMod 1 = [0]
    periodoFibMod n = 0 : aux (tail (fibsMod n))
      where aux (0:1:_) = []
            aux (x:xs)  = x : aux xs
     
    longPeriodosFibMod :: [Int]
    longPeriodosFibMod = map length [periodoFibMod n | n <- [1..]]
  2. angruicam1
    import Data.Array              (elems, array, (!))
    import Data.List.Split         (splitOn)
    import Graphics.Gnuplot.Simple (plotList, Attribute (Title, Key))
     
    fibsMod :: Integer -> [Integer]
    fibsMod 1 = repeat 0
    fibsMod n = elems a
      where a = array (0,2000)
                ([(0,0),(1,1)]
                 ++ [(i,(a!(i-1)+a!(i-2)) `mod` n)
                    | i <- [2..2000]])
     
    periodoFibMod :: Integer -> [Integer]
    periodoFibMod 1 = [0]
    periodoFibMod n =
      (0:) . head . splitOn [0,1] . tail . fibsMod $ n
     
    longPeriodosFibMod :: [Int]
    longPeriodosFibMod = map (length . periodoFibMod) [1..]
     
    graficaLongPeriodosFibMod :: Int -> IO ()
    graficaLongPeriodosFibMod n =
      plotList
      [Title ("graficaLongPeriodosFibMod " ++ show n),
       Key Nothing]
      (take n longPeriodosFibMod)
    • jaibengue

      Otra definición inspirada en tu idea:

      import Data.Array
       
      fibsMod :: Integer -> [Integer]
      fibsMod 1 = repeat 0
      fibsMod n = cycle(periodoFibMod n)
       
      periodoFibMod :: Integer -> [Integer]
      periodoFibMod 1 = [0]
      periodoFibMod n = 0:aux (tail u)
        where aux (0:1:_) = []
              aux (x:xs) = x:aux xs
              v = listArray (1,n^2+1) u 
              u = 0:1:[(v!(i-1)+v!(i-2)) `mod` n | i<-[3..n^2+1]]
      • antgongar

        Para que la definición de jaibengue no tenga el mismo problema que la de angruicam1 habría que demostrar que para todo n, la longitud del período no es mayor que n^2+1.

    • antgongar

      En la definición de angruicam1, al limitar la longitud del vector a 2000 da respuestas erróneas para los números con períodos de más de 2000 elementos. Por ejemplo,

      λ> length (periodoFibMod 1325)
      2001

      pero debería de dar 2700.

  3. antnavoro

    Un intento de definición sin argumentos:

    fibs :: [Integer]
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
     
    fibsMod :: Integer -> [Integer]
    fibsMod = flip map fibs . flip mod
     
    periodoFibMod :: Integer -> [Integer]
    periodoFibMod =
      (take
       . succ
       . length
       . takeWhile (not . isPrefixOf [0, 1])
       . tail
       . tails
       . fibsMod) <*> fibsMod
     
    longPeriodosFibMod :: [Int]
    longPeriodosFibMod = 1 : map (length . periodoFibMod) [2..]
  4. carbremor
    import Data.Numbers.Fibonacci
    import Graphics.Gnuplot.Simple
    import Test.Hspec
     
    -- Usaremos la librería Data.Numbers.Fibonacci
    -- para la resolución de este ejercicio. 
     
    -- λ> take 10 fibonacci
    -- [0,1,1,2,3,5,8,13,21,34]
    -- λ> length (show (fibonacci !! 251^37))
    -- 1928
    fibonacci :: [Integer]
    fibonacci = map fib [0..]
     
    -- λ> take 20 (fibsMod 7)
    -- [0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2]
    fibsMod  :: Integer -> [Integer]
    fibsMod = flip map fibonacci . flip mod
     
    -- λ> periodoFibMod 9
    -- [0,1,1,2,3,5,8,4,3,7,1,8,0,8,8,7,6,4,1,5,6,2,8,1]
    periodoFibMod :: Integer -> [Integer]
    periodoFibMod n  = take (periodo n) (fibsMod n)
     
    longPeriodosFibMod :: [Int]
    longPeriodosFibMod = map periodo [1..]
     
    graficaLongPeriodosFibMod :: Int -> IO ()
    graficaLongPeriodosFibMod n  = plotList [] (take n longPeriodosFibMod)
     
    -- Basado en el término general de la sucesión de Pisano, 
    -- para más información: https://goo.gl/4RnF5g
    periodo 1 = 1
    periodo n = f 1 ps 0
      where
       f 0 (1 : xs) pi = pi
       f _ (x : xs) pi = f x xs (pi + 1)
       ps = 1 : 1 : zipWith (u v -> (u + v) `mod` n) (tail ps) ps 
     
    -- ---------------------------------------------------------------------
    -- § Verificación                                                     --
    -- ---------------------------------------------------------------------
     
    verifica :: IO ()
    verifica = hspec $ do
      describe "fibsMod" $ do
        it "e1" $ do 
          take 24 (fibsMod 3) `shouldBe`
           [0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1]
        it  "e2" $ do
          take 24 (fibsMod 4) `shouldBe`
           [0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1]
     
      describe "periodoFibMod" $ do
        it "e1" $ do 
            periodoFibMod 3 `shouldBe`
             [0,1,1,2,0,2,2,1]
        it  "e2" $ do
            periodoFibMod 4 `shouldBe`
             [0,1,1,2,3,1]
        it  "e3" $ do
            periodoFibMod 7 `shouldBe`
             [0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1]
     
      describe "longPeriodosFibMod" $ do
         it "e1" $ do 
             take 20 longPeriodosFibMod `shouldBe`
              [1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60]
     
     
    -- λ> verifica
     
    -- fibsMod
      -- e1
      -- e2
    -- periodoFibMod
      -- e1
      -- e2
      -- e3
    -- longPeriodosFibMod
      --e1
     
    -- Finished in 0.0028 seconds
    -- 6 examples, 0 failures
    -- (0.01 secs, 302,384 bytes)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.