El cociente por 11 es igual a la suma de los cuadrados de sus cifras
El enunciado del problema 1 de la Olimpiada Internacional de Matemáticas de 1960 es el siguiente
Encontrar todos los números de tres cifras para los que al dividir el número entre 11 se obtiene la suma de los cuadrados de las cifras del número inicial.
Diremos que un número x es especial si al dividir x entre 11 se obtiene la suma de los cuadrados de las cifras de x.
Definir la función
1 |
esEspecial :: Integer -> Bool |
tal que (esEspecial x) se verifica si x es especial. Por ejemplo,
1 2 3 4 |
esEspecial 550 == True esEspecial 22 == False esEspecial 241 == False esEspecial (11^(10^8)) == False |
Usando la función esEspecial, calcular la respuesta al problema de la Olimpiada.
Calculando los números especiales menores que 10⁶, conjeturar que el conjunto de los números especiales es finito y comprobar la conjetura con QuickCheck.
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 |
import Test.QuickCheck (Positive(..), quickCheck) -- 1ª solución -- =========== esEspecial :: Integer -> Bool esEspecial x = x `mod` 11 == 0 && x `div` 11 == sum (map (^2) (digitos x)) -- head especiales == 550 especiales :: [Integer] especiales = filter esEspecial [11,22..] -- (digitos n) es la lista de los dígitos de n. Por ejemplo, -- digitos 325 == [3,2,5] digitos :: Integer -> [Integer] digitos a = [read [c] | c <-show a] -- Cálculo de la respuesta -- ======================= -- El cálculo es -- λ> filter esEspecial [100..999] -- [550,803] -- Por tanto, los números buscados son 550 y 803. -- Propiedad -- ========= -- Observando el siguiente cálculo -- λ> filter esEspecial [11,22..10^6] -- [550,803] -- se puede conjeturar que los únicos números especiales son 550 y -- 803. Lo vamos a comprobar con QuickCheck. -- La propiedad es prop_especiales :: Positive Integer -> Bool prop_especiales (Positive x) = x `elem` [550,803] || not (esEspecial x) -- La comprobación es -- λ> quickCheck prop_especiales -- +++ OK, passed 100 tests. -- 2ª solución -- =========== esEspecial2 :: Integer -> Bool esEspecial2 x = x `elem` [550,803] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esEspecial (11^(10^6)) -- False -- (2.22 secs, 4,675,669,056 bytes) -- λ> esEspecial2 (11^(10^6)) -- False -- (0.08 secs, 1,334,408 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>
3 Comentarios