Ir al contenido principal

Números belgas

Un número n es k-belga si la sucesión cuyo primer elemento es k y cuyos elementos se obtienen sumando reiteradamente las cifras de n contiene a n. Por ejemplo,

  • El 18 es 0-belga, porque a partir del 0 vamos a ir sumando sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1, 9, 10, 18, ... Como se alcanza el 18, resulta que el 18 es 0-belga.
  • El 19 no es 1-belga, porque a partir del 1 vamos a ir sumando sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1, 10, 11, 20, 21, ... Como no se alcanza el 19, resulta que el 19 no es 1-belga.

Definir la función

esBelga :: Int -> Int -> Bool

tal que (esBelga k n) se verifica si n es k-belga. Por ejemplo,

esBelga 0 18                              ==  True
esBelga 1 19                              ==  False
esBelga 0 2016                            ==  True
[x | x <- [0..30], esBelga 7 x]           ==  [7,10,11,21,27,29]
[x | x <- [0..30], esBelga 10 x]          ==  [10,11,20,21,22,24,26]
length [n | n <- [1..9000], esBelga 0 n]  ==  2857

Comprobar con QuickCheck que para todo número entero positivo n, si k es el resto de n entre la suma de los dígitos de n, entonces n es k-belga.

Soluciones

import Data.Char (digitToInt)
import Test.QuickCheck

-- 1ª solución
-- ===========

esBelga1 :: Int -> Int -> Bool
esBelga1 k n =
    n == head (dropWhile (<n) (scanl (+) k (cycle (digitos n))))

digitos :: Int -> [Int]
digitos n = map digitToInt (show n)

-- 2ª solución
-- ===========

esBelga2 :: Int -> Int -> Bool
esBelga2 k n =
    k <= n && n == head (dropWhile (<n) (scanl (+) (k + q * s) ds))
    where ds = digitos n
          s  = sum ds
          q  = (n - k) `div` s

-- Comparación de eficiencia
-- =========================

--    λ> length [n | n <- [1..9000], esBelga1 0 n]
--    2857
--    (2.95 secs, 1,115,026,728 bytes)
--    λ> length [n | n <- [1..9000], esBelga2 0 n]
--    2857
--    (0.10 secs, 24,804,480 bytes)

-- Equivalencia
-- ============

-- La propiedad es
prop_equivalencia :: Int -> Int -> Property
prop_equivalencia k n =
    n > 0 ==> esBelga1 k n == esBelga2 k n

-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

-- Verificación de la propiedad
-- ============================

-- La propiedad es
prop_Belga :: Int -> Property
prop_Belga n =
    n > 0 ==> esBelga2 k n
    where k = n `mod` sum (digitos n)

-- La comprobación es
--    λ> quickCheck prop_Belga
--    +++ OK, passed 100 tests.

Referencias

Basado en el artículo Números belgas del blog Números y hoja de cálculo de Antonio Roldán Martínez.