Ir al contenido principal

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

trenDePotencias 2453  = 2^4*5^3     = 2000
trenDePotencias 24536 = 2^4*5^3*6^1 = 12000

Definir las funciones

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.
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,
esPuntoFijoTrenDePotencias 2592                        ==  True
esPuntoFijoTrenDePotencias 24547284284866560000000000  ==  True
  • puntosFijosTrenDePotencias es la lista de los puntso fijos de trenDePotencias. Por ejemplo,
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,
λ> 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

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.