Menu Close

Día: 24 mayo, 2021

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

   esEspecial :: Integer -> Bool

tal que (esEspecial x) se verifica si x es especial. Por ejemplo,

   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

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>