Menu Close

Sucesión fractal

José A. Alonso,

La sucesión fractal

   0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 
   10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

está construida de la siguiente forma:

  • los términos pares forman la sucesión de los números naturales 
     0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
  • los términos impares forman la misma sucesión original
     0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

   sucFractal     :: [Integer]
   sumaSucFractal :: Integer -> Integer

tales que

  • sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo, 
     take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
     sucFractal !! 30     == 15
     sucFractal !! (10^7) == 5000000
  • (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,
     sumaSucFractal 10      == 13
     sumaSucFractal (10^5)  == 1666617368
     sumaSucFractal (10^10) == 16666666661668691669
     sumaSucFractal (10^15) == 166666666666666166673722792954
     sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
     length (show (sumaSucFractal (10^15000))) == 30000
     sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

Soluciones

 
-- 1ª definición de sucFractal
-- ===========================
 
sucFractal1 :: [Integer]
sucFractal1 = 
  map termino [0..]
 
-- (termino n) es el término n de la secuencia anterior. Por ejemplo,
--   termino 0            ==  0
--   termino 1            ==  0
--   map termino [0..10]  ==  [0,0,1,0,2,1,3,0,4,2,5]
termino :: Integer -> Integer
termino 0 = 0
termino n 
  | even n    = n `div` 2
  | otherwise = termino (n `div` 2)
 
-- 2ª definición de sucFractal
-- ===========================
 
sucFractal2 :: [Integer]
sucFractal2 =
  0 : 0 : mezcla [1..] (tail sucFractal2)
 
-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas
-- xs e ys. Por ejemplo,
--    take 10 (mezcla [0,2..] [0,-2..])  ==  [0,0,2,-2,4,-4,6,-6,8,-8]
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla (x:xs) (y:ys) =
  x : y : mezcla xs ys
 
-- Comparación de eficiencia de definiciones de sucFractal
-- =======================================================
 
--    λ> sum (take (10^6) sucFractal1)
--    166666169612
--    (5.56 secs, 842,863,264 bytes)
--    λ> sum (take (10^6) sucFractal2)
--    166666169612
--    (1.81 secs, 306,262,616 bytes)
 
-- En lo que sigue usaremos la 2ª definición
sucFractal :: [Integer]
sucFractal = sucFractal2
 
-- 1ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal1 :: Integer -> Integer
sumaSucFractal1 n =
  sum (map termino [0..n-1])
 
-- 2ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal2 :: Integer -> Integer
sumaSucFractal2 n =
  sum (take (fromIntegral n) sucFractal)
 
-- 3ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal3 :: Integer -> Integer
sumaSucFractal3 0 = 0
sumaSucFractal3 1 = 0
sumaSucFractal3 n
  | even n    = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)
  | otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)
  where sumaN n = (n*(n-1)) `div` 2
 
-- Comparación de eficiencia de definiciones de sumaSucFractal
-- ===========================================================
 
--    λ> sumaSucFractal1 (10^6)
--    166666169612
--    (5.25 secs, 810,622,504 bytes)
--    λ> sumaSucFractal2 (10^6)
--    166666169612
--    (1.72 secs, 286,444,048 bytes)
--    λ> sumaSucFractal3 (10^6)
--    166666169612
--    (0.01 secs, 0 bytes)
--    
--    λ> sumaSucFractal2 (10^7)
--    16666661685034
--    (17.49 secs, 3,021,580,920 bytes)
--    λ> sumaSucFractal3 (10^7)
--    16666661685034
--    (0.01 secs, 0 bytes)
Medio
, , , , , , ,

5 soluciones de “Sucesión fractal”

  1. Responder
    rebgongor 
    import Data.List
 
sucFractal :: [Integer]
sucFractal = 0 : xs
  where xs = 0 : concat [[x,y] | (x,y) <- zip [1..] xs]
 
sumaSucFractal :: Integer -> Integer
sumaSucFractal n = sum $ genericTake n sucFractal
  2. Responder
    fercarnav 
    import Data.List
 
sucFractal :: [Integer]
sucFractal = 0 : xs
  where xs = 0 : concat [[x,y] | (x,y) <- zip [1..] xs]
 
sumaSucFractal :: Integer -> Integer
sumaSucFractal n | n<=0 = 0
sumaSucFractal 1 = 0
sumaSucFractal m = div (n*(n+1)) 2  + sumaSucFractal ( p ) 
  where n = div m 2 -1 + mod m 2
        p = div m 2
  3. Responder
    juasuator1 
    import Data.List
 
sucFractal :: [Integer]
sucFractal  = 0:f sucFractal  [1..]
  where f (y:ys) (x:xs) = y:x:f ys xs
 
sumaSucFractal :: Integer -> Integer
sumaSucFractal 0 = 0
sumaSucFractal 1 = 0 
sumaSucFractal n
  | even n    = (t*(t+1)) `div`2  + sumaSucFractal (n-t-1)
  | otherwise = (q*(q+1)) `div`2  + sumaSucFractal (n-q-1)
  where t = n `div` 2 -1
        q = (n -1) `div`2
  4. Responder
    Enrique Zubiría 
    sucFractal :: [Integer]
sucFractal = 0 : 0 : concat [[x,y] | (x,y) <- zip [1..] (tail sucFractal)]
 
sumaSucFractal :: Integer -> Integer
sumaSucFractal n = sum (take (fromIntegral n) sucFractal)
  5. Responder
    jaicarrod1 
    sucFractal :: [Integer]
sucFractal = 0 : xs
  where xs = 0 : concat [[x,y] | (x,y) <- zip [1..] xs]
 
sumaSucFractal :: Integer -> Integer
sumaSucFractal 0 = 0
sumaSucFractal 1 = 0
sumaSucFractal m
  | rem m 2 == 0 = div (n*(n+1)) 2  + sumaSucFractal p 
  | otherwise = div ((n*(n+1))+1) 2 + sumaSucFractal p
  where n = div m 2 - 1 + rem m 2
        p = div m 2

Escribe tu solución

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