I1M2012: Suma de números monótonos
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de un problema propuesto para la Olimpiada Internacional de Matemáticas de 1982 cuyo enunciado es
Calcular la suma de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente o estrictamente decreciente.
Lo resolveremos generando las listas de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente monótona. Para ello nos basaremos en las listas de dígitos que forman una sucesión estrictamente monótona.
Comenzamos con los decrecientes:
- (listasDecrecientesDesde n) es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es n. Por ejemplo,
ghci> listasDecrecientesDesde 3
[[3],[3,2],[3,2,1],[3,2,1,0],[3,2,0],[3,1],[3,1,0],[3,0]]
1234listasDecrecientesDesde :: Integer -> [[Integer]]listasDecrecientesDesde 0 = [[0]]listasDecrecientesDesde n =[n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m] - listasDecrecientes es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es un dígito. Por ejemplo,
ghci> take 10 listasDecrecientes
[[0],[1],[1,0],[2],[2,1],[2,1,0],[2,0],[3],[3,2],[3,2,1]]
123listasDecrecientes :: [[Integer]]listasDecrecientes =concat [listasDecrecientesDesde n | n <- [0..9]] - (listaNumero xs) es el número correspondiente a la lista de dígitos xs. Por ejemplo,
listaNumero [3,2,5] == 325
12listaNumero :: [Integer] -> IntegerlistaNumero xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]] - numerosDecrecientes es la lista de los enteros positivos cuyos dígitos forman una sucesión estrictamente decreciente. Por ejemplo,
ghci> take 17 numerosDecrecientes
[0,1,10,2,21,210,20,3,32,321,3210,320,31,310,30,4,43]
12numerosDecrecientes :: [Integer]numerosDecrecientes = [listaNumero xs | xs <- listasDecrecientes]Análogamente se construyen los crecientes:
- (listasCrecientesDesde n) es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es n. Por ejemplo,
ghci> listasCrecientesDesde 6
[[6],[6,7],[6,7,8],[6,7,8,9],[6,7,9],[6,8],[6,8,9],[6,9]]
1234listasCrecientesDesde :: Integer -> [[Integer]]listasCrecientesDesde 9 = [[9]]listasCrecientesDesde n =[n] : [n:ys | m <- [n+1..9], ys <- listasCrecientesDesde m] - listascrecientes es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es un dígito. Por ejemplo,
ghci> take 5 listasCrecientes
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]
123listasCrecientes :: [[Integer]]listasCrecientes =concat [listasCrecientesDesde n | n <- [1..9]] - numerosCrecientes es la lista de los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente. Por ejemplo,
ghci> take 5 numerosCrecientes
[1,12,123,1234,12345]
12numerosCrecientes :: [Integer]numerosCrecientes = [listaNumero xs | xs <- listasCrecientes]Con las definiciones anteriores la solución es inmediata:
123solucion :: Integersolucion =sum (numerosCrecientes ++ numerosDecrecientes) - sum [1..9]El cálculo de la solución es
12ghci> solucion25617208995