Un número es ordenado si cada uno de sus dígitos es menor o igual el siguiente dígito. Por ejemplo, 116 es un número creciente y su cuadrado es 13456, que también es ordenado. En cambio, 115 es ordenado pero su cuadrado es 13225 que no es ordenado.
Definir la lista
numerosOrdenadosConCuadradosOrdenados :: [Integer] |
cuyos elementos son los números ordenados cuyos cuadrados también lo son. Por ejemplo,
λ> take 20 numerosOrdenadosConCuadradosOrdenados [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117] λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (10^6))) 1411 λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (5*10^6))) 3159 |
Soluciones
import Data.List -- 1ª solución -- =========== numerosOrdenadosConCuadradosOrdenados :: [Integer] numerosOrdenadosConCuadradosOrdenados = filter numeroOrdenadoConCuadradoOrdenado [0..] -- (numeroOrdenadoConCuadradoOrdenado n) se verifica si n es un número -- ordenado cuyo cuadrado también lo es. Por ejemplo, -- numeroOrdenadoConCuadradoOrdenado 116 == True -- numeroOrdenadoConCuadradoOrdenado 115 == False numeroOrdenadoConCuadradoOrdenado :: Integer -> Bool numeroOrdenadoConCuadradoOrdenado n = ordenado n && ordenado (n^2) -- (ordenado n) se verifica si n es un número ordenado. Por ejemplo, -- ordenado 115 == True -- ordenado 151 == False ordenado :: Integer -> Bool ordenado n = and [x <= y | (x,y) <- zip xs (tail xs)] where xs = show n -- 2ª solución -- =========== -- Se basa en la observación de los sisuientes cálculos con la primera -- solución -- λ> take 30 numerosOrdenadosConCuadradosOrdenados -- [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117, -- 167,334,335,337,367,667,1667,3334,3335,3337] -- λ> take 21 (dropWhile (<= 117) numerosOrdenadosConCuadradosOrdenados) -- [167,334,335,337,367,667, -- 1667,3334,3335,3337,3367,3667,6667, -- 16667,33334,33335,33337,33367,33667,36667,66667] -- -- Se observa que a partir del 167 todos los elementos son de 4 tipos -- como se ve en la siguente tabla -- |-------+--------+--------+--------+--------| -- | | Tipo A | Tipo B | Tipo C | Tipo D | -- |-------+--------+--------+--------+--------| -- | 167 | 16¹7 | | | | -- | 334 | | 3²4 | | | -- | 335 | | | 3²5 | | -- | 337 | | | | 3²6⁰7 | -- | 367 | | | | 3¹6¹7 | -- | 667 | | | | 3⁰6²7 | -- | 1667 | 16²7 | | | | -- | 3334 | | 3³4 | | | -- | 3335 | | | 3³5 | | -- | 3337 | | | | 3³6⁰7 | -- | 3367 | | | | 3²6¹7 | -- | 3667 | | | | 3¹6²7 | -- | 6667 | | | | 3⁰6³7 | -- | 16667 | 16³7 | | | | -- | 33334 | | 3⁴4 | | | -- | 33335 | | | 3⁴5 | | -- | 33337 | | | | 3⁴6⁰7 | -- | 33367 | | | | 3³6¹7 | -- | 33667 | | | | 3²6²7 | -- | 36667 | | | | 3¹6³7 | -- | 66667 | | | | 3⁰6⁴7 | -- |-------+--------+--------+--------+--------| -- donde el exponente en cad dígito indica el número de repeticiones de -- dicho dígito. numerosOrdenadosConCuadradosOrdenados2 :: [Integer] numerosOrdenadosConCuadradosOrdenados2 = [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117] ++ map read (concat [['1' : replicate n '6' ++ "7", replicate (n+1) '3' ++ "4", replicate (n+1) '3' ++ "5"] ++ [replicate a '3' ++ replicate b '6' ++ "7" | b <- [0..n+1], let a = (n+1) - b] | n <- [1..]]) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> numerosOrdenadosConCuadradosOrdenados !! 50 -- 1666667 -- (2.35 secs, 2,173,983,096 bytes) -- λ> numerosOrdenadosConCuadradosOrdenados2 !! 50 -- 1666667 -- (0.01 secs, 125,296 bytes) -- Comprobación de equivalencia -- ============================ -- La comprobación es -- λ> take 50 numerosOrdenadosConCuadradosOrdenados == take 50 numerosOrdenadosConCuadradosOrdenados2 -- True |
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>