Sucesión fractal
La sucesión fractal
|
1 2 |
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
|
1 |
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
|
1 |
0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ... |
Definir las funciones
|
1 2 |
sucFractal :: [Integer] sumaSucFractal :: Integer -> Integer |
tales que
- sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,
|
1 2 3 |
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,
|
1 2 3 4 5 6 7 |
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
-- 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) |