Menu Close

La conjetura de Rodolfo

El pasado 1 de enero, Claudio Meller publicó el artículo La conjetura de Rodolfo que afirma que

Todos los números naturales se pueden números pueden expresarse como la suma de un capicúa y un capicúa especial (siendo los capicúas especiales los números que al quitarles los ceros finales son capicúas; por ejemplo, 32300, 50500 y 78987).

Definir las funciones

   descomposiciones               :: Integer -> [(Integer, Integer)]
   contraejemplosConjeturaRodolfo :: [Integer]

tales que

  • (descomposiciones x) es la lista de las descomposiciones de x como la suma de un capicúa y un capicúa especial. Por ejemplo,
     descomposiciones 1980  ==  [(99,1881),(979,1001)]
     descomposiciones 2016  ==  [(575,1441),(606,1410)]
     descomposiciones 1971  ==  [(161,1810),(1771,200),(1881,90)]
  • contraejemplosConjeturaRodolfo es la lista de contraejemplos de la conjetura de Rodolfo; es decir, de los números que no pueden expresarse com la suma de un capicúa y un capicúa especial. Por ejemplo,
     λ> take 12 contraejemplosConjeturaRodolfo
     [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
     λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
     [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

Soluciones

import Data.List (nub)
 
descomposiciones :: Integer -> [(Integer, Integer)]
descomposiciones x =
  reducida [(y,z) | y <- takeWhile (<= x) capicuas
                  , let z = x - y
                  , esCapicuaG z]
 
-- capicuas es la sucesión de los números capicúas. Por ejemplo,
--    λ> take 45 capicuas
--    [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
--     141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
--     303,313,323,333,343,353]
-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".
capicuas :: [Integer]
capicuas = capicuasImpares `mezcla` capicuasPares
 
-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,  
--    λ> take 17 capicuasPares
--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
  [read (ns ++ reverse ns) | n <- [0..]
                           , let ns = show n]   
 
-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,  
--    λ> take 20 capicuasImpares
--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
  [1..9] ++ [read (ns ++ [z] ++ reverse ns)
            | n <- [1..]
            , let ns = show n
            , z <- "0123456789"]   
 
-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | otherwise = y : mezcla us ys
 
-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
--    esCapicua 353   ==  True
--    esCapicua 3553  ==  True
--    esCapicua 3535  ==  False
esCapicua :: Integer -> Bool
esCapicua x =
  xs == reverse xs
  where xs = show x
 
esCapicuaG :: Integer -> Bool
esCapicuaG x =
  x == 0 || esCapicua (sinCerosFinales x)
 
--    sinCerosFinales 3405000  ==  3405
sinCerosFinales :: Integer -> Integer
sinCerosFinales x =
  read (reverse (dropWhile (== '0') (reverse (show x))))
 
reducida :: [(Integer, Integer)] -> [(Integer, Integer)]
reducida ps =
  nub [(x,y) | (x,y) <- ps
             , x <= y]
 
--    λ> take 12 contraejemplosConjeturaRodolfo
--    [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
--    λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
--    [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]
contraejemplosConjeturaRodolfo :: [Integer]
contraejemplosConjeturaRodolfo =
  [x | x <- [0..]
  , null (descomposiciones x)]
Medio

5 soluciones de “La conjetura de Rodolfo

  1. paumacpar

    descomposiciones :: Integer -> [(Integer,Integer)]
    descomposiciones n =
      [(p,x) | x <- [n,n-1..1]
             , let p = n-x
             , esCapicuaEspecial x n
             , esCapicua p]
     
    esCapicuaEspecial :: Integer -> Integer -> Bool
    esCapicuaEspecial x n
      | x > (div n 2) =
        esCapicua x || esCapicua (sinCerosFinales x)
      | otherwise     =
        (sinCerosFinales x /= x) && (esCapicua (sinCerosFinales x))
     
    sinCerosFinales :: Integer -> Integer
    sinCerosFinales 0 = 0
    sinCerosFinales n =
      (read . reverse . dropWhile (== '0') . reverse . show) n
     
    esCapicua :: Integer -> Bool
    esCapicua x = (read . reverse . show) x == x
     
    contraejemplosConjeturaRodolfo :: [Integer]
    contraejemplosConjeturaRodolfo = aux2 [1..]
      where aux2 (x:xs)
              | null (descomposiciones x) = x : aux2 xs
              | otherwise                   = aux2 xs
  2. enrnarbej

    -- Usaremos la definicion de capicuas realizada en un ejercicio anterior
     
    descomposicionesA2 :: Integer -> [(Integer, Integer)]
    descomposicionesA2 n =
      [(x,y) | x <- xs
             , let y = n-x
             , if y `elem` xs
               then x <= y
               else esEspecial y xs]
      where xs = takeWhile (< n) capicuas
     
    esEspecial :: Integer -> [Integer] -> Bool
    esEspecial n xs =
      (until (k -> k `mod` 10 /= 0) ( `div` 10) n) `elem` xs
     
    contraejemplosConjeturaRodolfoA2 :: [Integer]
    contraejemplosConjeturaRodolfoA2 =
      filter (null . descomposicionesA2) [2..]
  3. Chema Cortés

    import Data.Tuple (swap)
    import Data.List (nubBy)
     
    descomposiciones :: Integer -> [(Integer, Integer)]
    descomposiciones n =
      nubBy f [(a, n-a) | a <- takeWhile (<= n) capicuas
                        , esCapicuaEspecial (n-a)]
      where f t u = t == u || t == swap u
     
    contraejemplosConjeturaRodolfo :: [Integer]
    contraejemplosConjeturaRodolfo =
      [i | i <- [1..], null (descomposiciones i)]
     
    esCapicuaEspecial :: Integer -> Bool
    esCapicuaEspecial = (==) <$> id <*> reverse
                             <$> dropWhile (=='0') . reverse . show
  4. albcercid

    descomposiciones :: Integer -> [(Integer, Integer)]
    descomposiciones x =
      [(a, x-a) | a <- takeWhile (x>=) capicuas,
                  spCap (x-a),
                  not (isCap (x-a) && a > x-a) ]
      where spCap x | x == 0        = True
                    | mod x 10 /= 0 = isCap x
                    | otherwise     = spCap (div x 10)
            isCap x = show x == reverse (show x)
     
    contraejemplosConjeturaRodolfo :: [Integer]
    contraejemplosConjeturaRodolfo =
      [x | x <- [0..]
         , null (descomposiciones x)]
  5. Juanjo Ortega (juaorture)
    import Data.List
     
    descomposiciones :: Integer -> [(Integer, Integer)]
    descomposiciones x =
      sinSimetricos [(a,b) | a <- takeWhile (<=x) capicuas
                           , let b = x - a
                           , esCapicuaEspecial b]
     
    esCapicua :: Integer -> Bool
    esCapicua x = xs == reverse xs
      where xs = show x
     
    capicuas :: [Integer]
    capicuas = [a | a <- [0..]
                    , esCapicua a]
     
    esCapicuaEspecial :: Integer -> Bool
    esCapicuaEspecial x = esCapicua x || xs == reverse xs
      where xs = show (read (reverse (show x)) :: Integer)
     
    simetrico :: (a,b) -> (b,a)
    simetrico (a,b) = (b,a)
     
    sinSimetricos :: Eq a => [(a,a)] -> [(a,a)]
    sinSimetricos [x] = [x]
    sinSimetricos xs  = xs \ drop (length ys `div` 2) ys
      where ys = intersect xs (map simetrico xs)
     
    contraejemplosConjeturaRodolfo :: [Integer]
    contraejemplosConjeturaRodolfo =
      [a | a <- [0..]
         , null $ descomposiciones a]

Escribe tu solución

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