Menu Close

Producto de Fibonaccis consecutivos

José A. Alonso,

Los números de Fibonacci son los números F(n) de la siguiente sucesión

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

que comienza con 0 y 1 y los siguientes términos son las sumas de los dos anteriores.

Un número x es el producto de dos números de Fibonacci consecutivos si existe un n tal que

   F(n) * F(n+1) = x

y su prueba es (F(n),F(n+1),True). Por ejemplo, 714 es el producto de dos números de Fibonacci consecutivos ya que

F(8) = 21, F(9) = 34 y 714 = 21 * 34.

Su prueba es (21, 34, True).

Un número x no es el producto de dos números de Fibonacci consecutivos si no existe un n tal que

   F(n) * F(n+1) = x

y su prueba es (F(m),F(m+1),False) donde m es el menor número tal que

   F(m) * F(m+1) > x

Por ejemplo, 800 no es el producto de dos números de Fibonacci consecutivos, ya que

 F(8) = 21, F(9) = 34, F(10) = 55 y 21 * 34 < 800 < 34 * 55.

Su prueba es (34, 55, False),

Definir la función

   productoFib :: Integer -> (Integer, Integer, Bool)

tal que (productoFib x) es la prueba de que es, o no es, el producto de dos números de Fibonacci consecutivos. Por ejemplo,

   productoFib 714  == (21,  34, True)
   productoFib 800  == (34,  55, False)
   productoFib 4895 == (55,  89, True)
   productoFib 5895 == (89, 144, False)

Soluciones

-- 1ª solución
-- ===========
 
productoFib :: Integer -> (Integer, Integer, Bool)
productoFib n
  | c == n    = (a,b,True)
  | otherwise = (a,b,False)
  where (a,b,c) = head (dropWhile (\(x,y,z) -> z < n) productos) 
 
-- fibs es la sucesión de números de Fibonacci. Por ejemplo,
--    take 14 fibs  ==  [0,1,1,2,3,5,8,13,21,34,55,89,144,233]
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
-- productos es la lista de las ternas (a,b,c) tales que a y b son dos
-- números de Fibonacci consecutivos y c es su producto. Por ejemplo,
--    λ> take 7 productos
--    [(0,1,0),(1,1,1),(1,2,2),(2,3,6),(3,5,15),(5,8,40),(8,13,104)]
productos :: [(Integer,Integer,Integer)]
productos = [(x,y,x*y) | (x,y) <- zip fibs (tail fibs)] 
 
-- 2ª solución
-- ===========
 
productoFib2 :: Integer -> (Integer, Integer, Bool)
productoFib2 n = aux 0 1 n
  where
    aux a b c
        | a * b >= c = (a, b, a * b == c)
        | otherwise  = aux b (a + b) c
 
-- 3ª solución
-- ===========
 
productoFib3 :: Integer -> (Integer, Integer, Bool)
productoFib3 x = aux 0 1
  where
    aux a b | a * b >= x = (a, b, x == a * b)
            | otherwise  = aux b (a + b)
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> let (x,_,_) = productoFib (10^20000) in length (show x)
--    10000
--    (1.15 secs, 323,396,360 bytes)
--    λ> let (x,_,_) = productoFib2 (10^20000) in length (show x)
--    10000
--    (1.10 secs, 317,268,672 bytes)
--    λ> let (x,_,_) = productoFib3 (10^20000) in length (show x)
--    10000
--    (1.08 secs, 314,972,440 bytes)

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

“El placer que obtenemos de la música proviene de contar, pero contando inconscientemente. La música no es más que aritmética inconsciente.”

Gottfried Wilhelm Leibniz.

Medio
, , , , , , ,

5 soluciones de “Producto de Fibonaccis consecutivos”

  1. Responder
    melgonaco 
    productoFib :: Integer -> (Integer,Integer,Bool)
productoFib x
  | fib n * fib (n+1) == x = (fib n,fib (n+1),True)
  | otherwise              = (fib n,fib (n+1),False)
  where n = head [y | y <- [0..], fib y * fib (y+1) >= x]
 
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
fib :: Integer -> Integer
fib n = head [a | (a,m) <- zip fibs [0..n], m == n]
  2. Responder
    pedperpal 
    productoFib :: Integer -> (Integer, Integer, Bool)
productoFib x = aux 0 1
  where
    aux a b | a * b >= x = (a, b, x == a * b)
            | otherwise  = aux b (a + b)
    • Responder
      pedperpal

      En Python

      def productoFib(x):
    a, b = 0, 1
    while x > a * b:
        a, b = b, a + b
    return [a, b, x == a * b]
      • Responder
        pedperpal

        En Julia

        function productoFib(x)
    a, b = BigInt(0), BigInt(1)
    while BigInt(x) > a * b
        a, b = b, a + b
    end
    (a, b, x == a * b ? true : false)
end
        • Responder
          pedperpal

          En Maxima

          productoFib(x) := block ([a:0, b:1],
  while (x > a * b) do
    [a, b] : [b, a + b],
  [a, b, is(x = a * b)])$

Escribe tu solución

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