Períodos de Fibonacci

PorJosé A. Alonso 9-febrero-201819-febrero-2018

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

1	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

1	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

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

Definir las funciones

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

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]

λ> 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]

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]

1 2	λ> 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

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)

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)

7 Comentarios

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

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

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)

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)

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]]

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]]

Responder

antgongar dice:

12-febrero-2018 a las 11:04

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.

Responder

antgongar dice:

12-febrero-2018 a las 10:56

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

1
2

λ> length (periodoFibMod 1325)
2001

pero debería de dar 2700.

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

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

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)

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)

Responder

Períodos de Fibonacci

Soluciones

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico