Sucesión de cubos perfectos
Definir la lista
1 |
sucesion :: [Integer] |
cuyos elementos son los términos de la sucesión
1 |
107811/3, 110778111/3, 111077781111/3, 111107777811111/3, ... |
Por ejemplo,
1 2 3 4 |
λ> take 5 sucesion [35937,36926037,37025927037,37035925937037,37036925926037037] λ> length (show (sucesion2 !! (3*10^6))) 9000005 |
Comprobar con QuickCheck que todos los términos de la sucesión son cubos perfectos.
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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
import Test.QuickCheck -- 1ª solución -- =========== sucesion :: [Integer] sucesion = map termino [1..] -- (termino n) es el término n-ésimo de la sucesión por ejemplo, -- termino 1 == 35937 -- termino 2 == 36926037 -- termino 3 == 37025927037 termino :: Int -> Integer termino n = numerador n `div` 3 -- (numerador n) es el numerador del término n-ésimo de la sucesión por -- ejemplo, -- λ> mapM_ print (map numerador [1..5]) -- 107811 -- 110778111 -- 111077781111 -- 111107777811111 -- 111110777778111111 numerador :: Int -> Integer numerador n = read (replicate n '1' ++ "0" ++ replicate n '7' ++ "81" ++ replicate n '1') -- Propiedad -- ========= -- La propiedad es prop_sucesion :: Int -> Property prop_sucesion n = n >= 0 ==> esCubo (sucesion !! n) -- La comprobación es -- λ> quickCheck prop_sucesion -- +++ OK, passed 100 tests. -- (esCubo x) se verifica si x es un cubo perfecto. Por ejemplo, -- esCubo 27 == True -- esCubo 28 == False esCubo :: Integer -> Bool esCubo x = (raizCubicaEntera x)^3 == x -- (raizCubicaEntera x) es el mayor entero cuyo cubo es menor o igual -- que x. Por ejemplo, -- raizCubicaEntera 26 == 2 -- raizCubicaEntera 27 == 3 -- raizCubicaEntera 28 == 3 raizCubicaEntera :: Integer -> Integer raizCubicaEntera x = aux (1,x) where aux (a,b) | d == x = c | c == a = c | d < x = aux (c,b) | otherwise = aux (a,c) where c = (a+b) `div` 2 d = c^3 -- Otra forma es observando los cubos de los términos de la sucesión -- λ> map raizCubicaEntera (take 7 sucesion) -- [33,333,3333,33333,333333,3333333,33333333] -- La propiedad es prop_sucesion2 :: Int -> Property prop_sucesion2 n = n >= 0 ==> sucesion !! n == ((10^(n+2)-1) `div` 3)^3 -- La comprobación es -- λ> quickCheck prop_sucesion2 -- +++ OK, passed 100 tests. -- 2ª solución -- =========== -- Basada en la propiedad anterior. sucesion2 :: [Integer] sucesion2 = [((10^n-1) `div` 3)^3 | n <- [2..]] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_equiv :: Int -> Property prop_equiv n = n >= 0 ==> sucesion !! n == sucesion2 !! n -- La comprobación es -- λ> quickCheck prop_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (show (sucesion !! (3*10^6))) -- 9000005 -- (6.34 secs, 5,161,177,808 bytes) -- λ> length (show (sucesion2 !! (3*10^6))) -- 9000005 -- (2.72 secs, 1,124,065,328 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Un comentario