Menu Close

Períodos de Fibonacci

José A. Alonso,

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)
Posted in Medio
Tagged , , , , , , , , , , , ,

7 Comments

  1. jaibengue
    Responder 
    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
    Responder 
    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
      Responder

      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
        Responder

        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
      Responder

      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
    Responder

    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
    Responder 
    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.