Descomposiciones como sumas de consecutivos
El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1966 es
- (a) Calcular el número de maneras de expresar 500 como suma de números naturales consecutivos.
- (b) Calcular el número de tales representaciones para n = 2^x·3^y·5^z, con x, y, z ∈ ℕ. ¿Cuántas de ellas están formadas por un único elemento?
- (c) Calcular el número de tales representaciones para un número natural n.
Definir las funciones
1 2 |
consecutivosConSuma :: Integer -> [(Integer,Integer)] nDeConsecutivosConSuma :: Integer -> Integer |
tales que
- (consecutivosConSuma n) es la lista de los extremos de las sucesiones de números naturales consecutivos cuya suma es n. Por ejemplo,
1 2 3 4 5 6 |
consecutivosConSuma 3 == [(0,2),(1,2),(3,3)] consecutivosConSuma 4 == [(4,4)] consecutivosConSuma 5 == [(2,3),(5,5)] consecutivosConSuma 6 == [(0,3),(1,3),(6,6)] consecutivosConSuma 15 == [(0,5),(1,5),(4,6),(7,8),(15,15)] maximum [length (consecutivosConSuma n) | n <- [1..1000]] == 16 |
- (nDeConsecutivosConSuma n) es la cantidad de sucesiones de números naturales consecutivos cuya suma es n. Por ejemplo,
1 2 3 4 5 6 7 |
nDeConsecutivosConSuma 3 == 3 nDeConsecutivosConSuma 4 == 1 nDeConsecutivosConSuma 5 == 2 nDeConsecutivosConSuma 6 == 3 nDeConsecutivosConSuma 15 == 5 maximum [nDeConsecutivosConSuma n | n <- [1..10^5]] == 49 nDeConsecutivosConSuma (product [1..17]) == 672 |
Usando las funciones anteriores, calcular las respuestas del problema de la Olimpiada.
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 |
import Data.List (genericLength, genericTake, group) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck (Positive(..), quickCheck) -- 1ª definición de consecutivosConSuma -- ===================================== consecutivosConSuma :: Integer -> [(Integer,Integer)] consecutivosConSuma n = [(x,y) | y <- [0..n], x <- [0..y], sum [x..y] == n] -- 2ª definición de consecutivosConSuma -- ===================================== consecutivosConSuma2 :: Integer -> [(Integer,Integer)] consecutivosConSuma2 n = [(x,y) | y <- [0..n], x <- [0..y], (x+y)*(y-x+1) == 2*n] -- 3ª definición de consecutivosConSuma -- ===================================== consecutivosConSuma3 :: Integer -> [(Integer,Integer)] consecutivosConSuma3 n | esTriangular n = (0, p n - 1) : [(p x, p y - 1) | (x,y) <- aux n] | otherwise = [(p x, p y - 1) | (x,y) <- aux n] where p x = posicion x triangulares aux n = [(x,y) | y <- zs, let x = y-n, x `elem` zs] where zs = genericTake (n+1) triangulares -- (esTriangular n) se verifica si n es un número triangular (es decir, -- existe un m tal que n es 1+2+···+m). Por ejemplo, -- esTriangular 6 == True -- esTriangular 8 == False esTriangular :: Integer -> Bool esTriangular n = n `pertenece` triangulares -- triangulares es la sucesión de los números triangulares. Por ejemplo, -- take 10 triangulares == [0,1,3,6,10,15,21,28,36,45] triangulares :: [Integer] triangulares = scanl1 (+) [0..] -- (pertenece x ys) se verifica si x pertenece a la lista infinita -- creciente ys. Por ejemplo, -- pertenece 11 [1,3..] == True -- pertenece 12 [1,3..] == False pertenece :: Ord a => a -> [a] -> Bool pertenece x ys = x == head (dropWhile (< x) ys) -- (posicion x ys) es la posición de x en la lista ys. Por ejemplo, -- posicion 7 [1,3..] == 4 posicion :: Eq a => a -> [a] -> Integer posicion x (y:ys) | x == y = 1 | otherwise = 1 + posicion x ys -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximum [length (consecutivosConSuma2 n) | n <- [1..200]] -- 9 -- (0.96 secs, 651,218,112 bytes) -- λ> maximum [length (consecutivosConSuma3 n) | n <- [1..200]] -- 9 -- (0.04 secs, 6,664,544 bytes) -- -- λ> maximum [length (consecutivosConSuma2 n) | n <- [1..300]] -- 9 -- (3.14 secs, 2,172,860,536 bytes) -- λ> maximum [length (consecutivosConSuma3 n) | n <- [1..300]] -- 9 -- (0.16 secs, 14,523,880 bytes) -- 1ª definición de nDeConsecutivosConSuma -- ======================================= nDeConsecutivosConSuma :: Integer -> Integer nDeConsecutivosConSuma = genericLength . consecutivosConSuma -- 2ª definición de nDeConsecutivosConSuma -- ======================================= nDeConsecutivosConSuma2 :: Integer -> Integer nDeConsecutivosConSuma2 = genericLength . consecutivosConSuma2 -- 3ª definición de nDeConsecutivosConSuma -- ======================================= nDeConsecutivosConSuma3 :: Integer -> Integer nDeConsecutivosConSuma3 = genericLength . consecutivosConSuma3 -- Cálculo de las respuestas -- ========================= -- El número de maneras de expresar 500 como suma de números naturales -- consecutivos se calcula con -- λ> nDeConsecutivosConSuma 500 -- 4 -- Por tanto, se puede expresar de 4 formas distintas. Dichas -- expresiones se pueden calcular consecutivos -- λ> consecutivosConSuma 500 -- [(8,32),(59,66),(98,102),(500,500)] -- Es decir, -- 500 = sum [8..32] -- 500 = sum [59..66] -- 500 = sum [98..102] -- 500 = sum [500..500] -- Para la segunda pregunta realizamos los siguientes cálculos -- λ> ts = [(x,y,z) | x <- [0..3], y <- [0..3], z <- [0..3]] -- λ> as = [nDeConsecutivosConSuma3 (2^x*3^y*5^z) | (x,y,z) <- ts] -- λ> as -- [2,2,3,4,3,5,6,8,3,7,9,12,4,8,12,16, -- 1,3,3,4,3,4,6,8,3,6,9,12,4,8,12,16, -- 1,2,3,4,2,4,7,8,4,6,9,12,4,8,12,16, -- 1,2,3,4,2,5,6,8,3,6,9,12,4,8,12,16] -- λ> bs = [(y+1)*(z+1) | (x,y,z) <- ts] -- λ> bs -- [1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16, -- 1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16, -- 1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16, -- 1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16] -- Casi todos elementos de as son iguales que los de bs y los que no lo -- son se diferencian en 1 como se observa en el siguiente cálculo -- λ> zipWith (-) as bs -- [1,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0, -- 0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0, -- 0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0, -- 0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0] -- Los que no son iguales se calcula con -- λ> [n | (x,y,z) <- ts, let n = 2^x*3^y*5^z, nDeConsecutivosConSuma3 n /= (y+1)*(z+1)] -- [1,3,15,45,10,6,300,36,120] -- Dichos elementos son los números triangulares (es decir, los son -- sumas de los primeros números naturales) como se comprueba con -- λ> [n | (x,y,z) <- ts, let n = 2^x*3^y*5^z, esTriangular n] -- [1,3,15,45,10,6,300,36,120] -- -- En definitiva, el número de representaciones de n = 2^x·3^y·5^z es -- + (y+1)*(z+1), si n no es triangular, -- + 1 + (y+1)*(z+1), si n es triangular, -- En el número n = 2^x·3^y·5^z, la parte 3^y·5^z es la parte impar de -- n y (y+1)*(z+1) es el número de divisores de la parte impar de n. Por -- tanto, el número de representaciones de n = 2^x·3^y·5^z es -- + el número de divisores de la parte impar de n, si n no es triangular, -- + uno más el número de divisores de la parte impar de n, si n es triangular, -- El cálculo de la segunda parte del apartado (b) es -- λ> [n | n <- [0..100], nDeConsecutivosConSuma3 n == 1] -- [2,4,8,16,32,64] -- que son las potencias de 2 con exponentes positivos. -- Finalmente, para el apartado (c), se puede generalizar el resultado -- anterior y el número de representaciones de n = 2^x·3^y·5^z es -- + el número de divisores de la parte impar de n, si n no es triangular, -- + uno más el número de divisores de la parte impar de n, si n es triangular, -- donde la parte impar de n es el número impar y tal que existe un -- número natural k tal que n = 2^k·y. -- Vamas a comprobar la conjetura haciendo la siguente definición y -- comprobando que es equivalente a la anterior. -- 4ª definición de nDeConsecutivosConSuma -- ======================================= nDeConsecutivosConSuma4 :: Integer -> Integer nDeConsecutivosConSuma4 n | esTriangular n = 1 + (numeroDivisores (parteImpar n)) | otherwise = numeroDivisores (parteImpar n) -- (parteImpar n) es la parte impar de n. Por ejemplo, -- parteImpar 60 == 15 parteImpar :: Integer -> Integer parteImpar n | odd n = n | otherwise = parteImpar (n `div` 2) -- (numeroDivisores n) es el número de divisores de n. Por ejemplo, -- numeroDivisores 12 == 6 -- numeroDivisores 14 == 4 numeroDivisores :: Integer -> Integer numeroDivisores = product . map ((+1) . genericLength) . group . primeFactors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_equivalencia :: Positive Integer -> Bool prop_equivalencia (Positive n) = nDeConsecutivosConSuma3 n == nDeConsecutivosConSuma4 n -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> nDeConsecutivosConSuma (product [1..6]) -- 6 -- (2.34 secs, 8,110,570,304 bytes) -- λ> nDeConsecutivosConSuma2 (product [1..6]) -- 6 -- (0.24 secs, 123,044,288 bytes) -- λ> nDeConsecutivosConSuma3 (product [1..6]) -- 6 -- (0.04 secs, 443,408 bytes) -- λ> nDeConsecutivosConSuma4 (product [1..6]) -- 6 -- (0.01 secs, 103,424 bytes) -- -- λ> nDeConsecutivosConSuma2 (product [1..7]) -- 12 -- (10.27 secs, 5,999,094,088 bytes) -- λ> nDeConsecutivosConSuma3 (product [1..7]) -- 12 -- (0.44 secs, 2,465,936 bytes) -- λ> nDeConsecutivosConSuma4 (product [1..7]) -- 12 -- (0.01 secs, 107,424 bytes) -- -- λ> nDeConsecutivosConSuma3 (product [1..8]) -- 12 -- (53.51 secs, 19,137,984 bytes) -- λ> nDeConsecutivosConSuma4 (product [1..8]) -- 12 -- (0.01 secs, 107,808 bytes) |
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>
Un comentario