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 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
1 |
numerosOrdenadosConCuadradosOrdenados :: [Integer] |
cuyos elementos son los números ordenados cuyos cuadrados también lo son. Por ejemplo,
1 2 3 4 5 6 |
λ> 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
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 |
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>
Con esta definición no se puede calcular todos los ejemplos, para ello se necesita una más eficiente. Por ejemplo,
donde el primer ejemplo es con esta definición y el segundo con otra.