Terminaciones de Fibonacci

José A. Alonso

02-01-2017

Definir la sucesión

sucFinalesFib :: [(Integer,Integer)]

cuyos elementos son los pares (n,x), donde x es el n-ésimo término de la sucesión de Fibonacci, tales que la terminación de x es n. Por ejemplo,

λ> take 6 sucFinalesFib
[(0,0),(1,1),(5,5),(25,75025),(29,514229),(41,165580141)]
λ> head [(n,x) | (n,x) <- sucFinalesFib, n > 200]
(245,712011255569818855923257924200496343807632829750245)
λ> head [n | (n,_) <- sucFinalesFib, n > 10^4]
10945

Soluciones

import Data.List (genericIndex, isSuffixOf)

sucFinalesFib :: [(Integer, Integer)]
sucFinalesFib =
  [(n, fib n) | n <- [0..]
              , show n `isSuffixOf` show (fib n)]

sucFib :: [Integer]
sucFib = 0 : 1 : zipWith (+) sucFib (tail sucFib)

-- (fib n) es el n-ésimo término de la sucesión de Fibonacci.
fib :: Integer -> Integer
fib n = sucFib `genericIndex` n