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]

1 2	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)]

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]

λ> 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)]

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)]

5 Comentarios

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

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

Responder

-- 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..]

-- 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..]

Responder

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

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

Responder

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)]

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)]

Responder

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]

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]

Responder

La conjetura de Rodolfo

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico