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. |