Menu Close

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

   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>

5 soluciones de “Números ordenados con cuadrados ordenados

  1. Rubén Muñoz Mkrtchian
    numerosOrdenadosConCuadradosOrdenados :: [Integer]
    numerosOrdenadosConCuadradosOrdenados = [n | n <- [0..], all ordenado [n,n^2]]
      where ordenado = creciente . show
            creciente [_] = True
            creciente (x:y:zs) = x <= y && creciente (y:zs)
    • José A. Alonso

      Con esta definición no se puede calcular todos los ejemplos, para ello se necesita una más eficiente. Por ejemplo,

      λ> length (show (numerosOrdenadosConCuadradosOrdenados !! 60))
      8
      (15.73 secs, 17,942,621,432 bytes)
      λ> length (show (numerosOrdenadosConCuadradosOrdenados2 !! 60))
      8
      (0.01 secs, 127,064 bytes)

      donde el primer ejemplo es con esta definición y el segundo con otra.

  2. Joaquín Infante Rodríguez
    import Data.List
     
    listaOrdenada :: [Integer] -> Bool
    listaOrdenada []  = True
    listaOrdenada [x] = True
    listaOrdenada (x:y:xs) = x<=y && listaOrdenada (y:xs)
     
    numeroOrdenado :: Integer -> Bool
    numeroOrdenado n = listaOrdenada ([read [x] | x<-show n])
     
    numerosOrdenadosConCuadradosOrdenados :: [Integer]
    numerosOrdenadosConCuadradosOrdenados = [x | x<-[0..], numeroOrdenado x && numeroOrdenado (x^2)]
  3. Mercedes Vega Gallo
    -- Al realizar los cálculos con la función "aux" nos damos cuenta de que, si
    -- bien procede correctamente, no resulta ser muy efectiva al operar con
    -- números grandes. Sin embargo, fue esta función la que me permitió
    -- identificar un patrón en el resultado que parecía repetirse. Por tanto, me
    -- ayudo de este patrón para dar solución al problema. La función "aux"
    -- únicamente me servirá para dar los primeros 27 elementos de la lista.
     
     
    -- La función "aux" nos devuelve la lista de los elementos ordenados cuyos cuadrados también lo son.          
    aux :: [Integer]
    aux = filter p [0..]
      where p x = q x && q (x^2)
            q = creciente . show 
     
    -- La función "creciente xs" se verifica si la lista xs es creciente, es decir,
    -- si está ordenada.                                              
    creciente :: [Char] -> Bool
    creciente [_] = True
    creciente (y:x:xs) = y<=x && creciente (x:xs)
     
     
    -- Respuesta definitiva:
     
    numerosOrdenadosConCuadradosOrdenados :: [Integer]
    numerosOrdenadosConCuadradosOrdenados = take 27 aux ++ serie [334,335,337,367,667,1667]
     
    -- La función "serie xs" nos devuelve una lista formada por elementos de la
    -- serie definida por xs.
    serie :: [Integer] -> [Integer]               
    serie xs = map numero $ aux (map digitos xs)
      where aux xs = (map (3:) (init xs) ++ añade (last xs)) ++ aux (map (3:) (init xs)++ añade (last xs))
     
    -- La función "digitos x" nos devuelve la lista de los dígitos de x.
    digitos :: Integer -> [Integer]
    digitos x = [read [a] | a <- show x]        
     
    -- La función "numero xs" transforma la lista xs en un número.
    numero :: [Integer] -> Integer
    numero xs = sum [a*b |(a,b)<-zip (reverse xs)  (map (10^) [0..])]
     
    -- La función "añade xs" devuelve una lista formada, a su vez, por dos listas
    -- con modificaciones a partir de xs.
    añade :: [Integer]->[[Integer]]
    añade xs = [[6]++tail xs, [1,6]++tail xs]
     
     
    -- Esta función es bastante más efectiva y con ella podemos calcular los dos
    -- últimos ejemplos:
     
    --λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (10^6)))
    --1411
    --(0.76 secs, 552,309,200 bytes)
    --λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (5*10^6)))
    --3159
    --(2.11 secs, 2,197,889,200 bytes)
     
    -- ¡Qué curioso!
  4. Inés Mora Caro
     
    -- Un número es ordenado si cada uno de sus dígitos es menor o igual
    -- que el siguiente dígito.
     
    -- Definir la lista cuyos elementos son los números ordenados cuyos
    -- cuadrados también lo son.
     
    numerosOrdenadosConCuadradosOrdenados :: [Integer]
    numerosOrdenadosConCuadradosOrdenados = [x | x <- [0..],
                                                 esCuadradoOrdenado x,
                                                 esCuadradoOrdenado (x^2)]
     
    listaDigitos :: Integer -> [Integer]
    listaDigitos x = [read [x] ::Integer | x <- show x]
     
     
    esCuadradoOrdenado :: Integer -> Bool
    esCuadradoOrdenado x = and $ take 2 $
                            True:[False |
                            (x,y) <- (zip (listDigit) (tail (listDigit))), x>y]
                                  where listDigit = listaDigitos x
     
     
    -- Una forma menos eficiente:
    esCuadradoOrdenado2 :: Integer -> Bool
    esCuadradoOrdenado2 x = null $ dropWhile (==True) $
                            map ((x,y) -> x <= y)
                                (zip (listDigit) (tail (listDigit)))
                                         where listDigit = listaDigitos x

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.