Tren de potencias
Si n es el número natural cuya expansión decimal es abc… , el tren de potencias de n es a^bc^d… donde el último exponente es 1, si n tiene un número impar de dígitos. Por ejemplo
1 2 |
trenDePotencias 2453 = 2^4*5^3 = 2000 trenDePotencias 24536 = 2^4*5^3*6^1 = 12000 |
Definir las funciones
1 2 3 4 |
trenDePotencias :: Integer -> Integer esPuntoFijoTrenDePotencias :: Integer -> Bool puntosFijosTrenDePotencias :: [Integer] tablaTrenDePotencias :: Integer -> Integer -> IO () |
tales que
- (trenDePotencias n) es el tren de potencia de n. Por ejemplo.
1 2 3 4 5 |
trenDePotencias 20 == 1 trenDePotencias 21 == 2 trenDePotencias 24 == 16 trenDePotencias 39 == 19683 trenDePotencias 623 == 108 |
- (esPuntoFijoTrenDePotencias n) se verifica si n es un punto fijo de trenDePotencias; es decir, (trenDePotencias n) es igual a n. Por ejemplo,
1 2 |
esPuntoFijoTrenDePotencias 2592 == True esPuntoFijoTrenDePotencias 24547284284866560000000000 == True |
- puntosFijosTrenDePotencias es la lista de los puntso fijos de trenDePotencias. Por ejemplo,
1 |
take 10 puntosFijosTrenDePotencias == [1,2,3,4,5,6,7,8,9,2592] |
- (tablaTrenDePotencias a b) es la tabla de los trenes de potencias de los números entre a y b. Por ejemplo,
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 |
λ> tablaTrenDePotencias 20 39 | 20 | 1 | | 21 | 2 | | 22 | 4 | | 23 | 8 | | 24 | 16 | | 25 | 32 | | 26 | 64 | | 27 | 128 | | 28 | 256 | | 29 | 512 | | 30 | 1 | | 31 | 3 | | 32 | 9 | | 33 | 27 | | 34 | 81 | | 35 | 243 | | 36 | 729 | | 37 | 2187 | | 38 | 6561 | | 39 | 19683 | λ> tablaTrenDePotencias 2340 2359 | 2340 | 8 | | 2341 | 32 | | 2342 | 128 | | 2343 | 512 | | 2344 | 2048 | | 2345 | 8192 | | 2346 | 32768 | | 2347 | 131072 | | 2348 | 524288 | | 2349 | 2097152 | | 2350 | 8 | | 2351 | 40 | | 2352 | 200 | | 2353 | 1000 | | 2354 | 5000 | | 2355 | 25000 | | 2356 | 125000 | | 2357 | 625000 | | 2358 | 3125000 | | 2359 | 15625000 | |
Comprobar con QuickCheck que entre 2593 y 24547284284866559999999999 la función trenDePotencias no tiene puntos fijos.
Soluciones
Puedes escribir tus soluciones en los comentarios o ver las soluciones propuestas pulsando [expand title=»aquí»]
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 |
import Test.QuickCheck import Text.Printf -- 1ª definición de trenDePotencias -- ================================ trenDePotencias :: Integer -> Integer trenDePotencias = trenDePotenciasLN . digitos -- (digitos n) es la lista de los dígitos del número n. Por ejemplo, -- digitos 2018 == [2,0,1,8] digitos :: Integer -> [Integer] digitos n = [read [c] | c <- show n] -- (trenDePotenciasLN xs) es el tren de potencias de la lista de números -- xs. Por ejemplo, -- trenDePotenciasLN [2,4,5,3] == 2000 -- trenDePotenciasLN [2,4,5,3,6] == 12000 trenDePotenciasLN :: [Integer] -> Integer trenDePotenciasLN [] = 1 trenDePotenciasLN [x] = x trenDePotenciasLN (u:v:ws) = u ^ v * (trenDePotenciasLN ws) -- 2ª definición de trenDePotencias -- ================================ trenDePotencias2 :: Integer -> Integer trenDePotencias2 = trenDePotenciasLN2 . digitos -- (trenDePotenciasLN2 xs) es el tren de potencias de la lista de números -- xs. Por ejemplo, -- trenDePotenciasLN2 [2,4,5,3] == 2000 -- trenDePotenciasLN2 [2,4,5,3,6] == 12000 trenDePotenciasLN2 :: [Integer] -> Integer trenDePotenciasLN2 xs = product [x^y | (x,y) <- pares xs] -- (pares xs) es la lista de los pares de elementos en la posiciones -- pares y sus siguientes; si la longitud de xs es impar, la segunda -- componente del último par es 1. Por ejemplo, -- pares [2,4,5,3] == [(2,4),(5,3)] -- pares [2,4,5,3,6] == [(2,4),(5,3),(6,1)] pares :: [Integer] -> [(Integer,Integer)] pares [] = [] pares [x] = [(x,1)] pares (x:y:zs) = (x,y) : pares zs -- Equivalencia -- ============ -- La propiedad es prop_equivalencia :: (Positive Integer) -> Bool prop_equivalencia (Positive n) = trenDePotencias n == trenDePotencias2 n -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> let n = 2*10^5 in trenDePotencias (read (replicate n '2')) == 2^n -- True -- (2.11 secs, 2,224,301,136 bytes) -- λ> let n = 2*10^5 in trenDePotencias2 (read (replicate n '2')) == 2^n -- True -- (2.08 secs, 2,237,749,216 bytes) -- Definición de esPuntoFijoTrenDePotencias -- ======================================== esPuntoFijoTrenDePotencias :: Integer -> Bool esPuntoFijoTrenDePotencias n = trenDePotencias n == n -- Definición de puntosFijosTrenDePotencias -- ======================================== puntosFijosTrenDePotencias :: [Integer] puntosFijosTrenDePotencias = filter esPuntoFijoTrenDePotencias [1..] -- Definición de tablaTrenDePotencias -- ================================== tablaTrenDePotencias :: Integer -> Integer -> IO () tablaTrenDePotencias a b = sequence_ [printf cabecera x y | (x,y) <- trenes] where trenes = [(n,trenDePotencias n) | n <- [a..b]] m1 = show (1 + length (show b)) m2 = show (length (show (maximum (map snd trenes)))) cabecera = concat ["|% ",m1,"d | %", m2,"d |\n"] -- Comprobación -- ============ -- La propiedad es prop_puntosFijos :: Positive Integer -> Property prop_puntosFijos (Positive n) = x < 24547284284866560000000000 ==> not (esPuntoFijoTrenDePotencias x) where x = 2593 + n -- La comprobación es -- λ> quickCheck prop_puntosFijos -- +++ OK, passed 100 tests. |
[/expand]