Números ordenados con cuadrados ordenados
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 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