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