Sucesiones de sumas digitales

José A. Alonso

26-03-2021

La sucesión de las sumas digitales definida por un número a es sucesión a(n) tal que a(0) = a y a(n+1) es la suma de a(n) y los dígitos de a(n). Por ejemplo, los primeros términos de la sucesión de las sumas digitales definida por 1 son

   1,2,4,8,16,23,28,38,49,62,70,77,91,101,103,107,...

Se observa que el menor número que no pertenece a la sucesión anterior es 3. Los primeros términos de la sucesión de las sumas digitales definida por 3 son

   3,6,12,15,21,24,30,33,39,51,57,69,84,96,111,114,...

Se observa que el menor número que no pertenece a las 2 anteriores es 5. Los primeros términos de la sucesión de las sumas digitales definida por 5 son

   5,10,11,13,17,25,32,37,47,58,71,79,95,109,119,130,...

Se observa que el menor número que no pertenece a las 3 sucesiones anteriores es 7. Los primeros términos de la sucesión de las sumas digitales definida por 7 son

   7,14,19,29,40,44,52,59,73,83,94,107,115,122,127,137,...

Se observa que el menor número que no pertenece a las 4 anteriores es 9. Los primeros términos de la sucesión de las sumas digitales definida por 9 son

   9,18,27,36,45,54,63,72,81,90,99,117,126,135,144,153,...

Se observa que el menor número que no pertenece a las 5 sucesiones anteriores es 20. Los primeros términos de la sucesión de las sumas digitales definida por 20 son

   20,22,26,34,41,46,56,67,80,88,104,109,119,130,134,142,...

Definir la función

   sucesionSucesionesSumasDigitales :: [[Integer]]

tal que sus elementos son las sucesiones de sumas parciales tal que el primer elemento de cada sucesión es el menor elemento que no pertenece a las sucesiones anteriores. Por ejemplo,

   λ> map (take 4) (take 8 sucesionSucesionesSumasDigitales)
   [[1,2,4,8],[3,6,12,15],[5,10,11,13],[7,14,19,29],
    [9,18,27,36],[20,22,26,34],[31,35,43,50],[42,48,60,66]]
   λ> take 10 (sucesionSucesionesSumasDigitales3 !! 1000)
   [10199,10219,10232,10240,10247,10261,10271,10282,10295,10312]

Soluciones

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

sucesionSucesionesSumasDigitales :: [[Integer]]
sucesionSucesionesSumasDigitales =
  map aux [1..]
  where aux 1 = sucesionSumasDigitales 1
        aux n = sucesionSumasDigitales m
          where m = head [a | a <- [1..],
                              all (a `noPertenece`)
                                  [aux k | k <- [1..n-1]]]

-- (sucesionSumasDigitales a) es la sucesión de las sumas digitales
-- definida por un número a. Por ejemplo,
--    λ> take 16 (sucesionSumasDigitales 1)
--    [1,2,4,8,16,23,28,38,49,62,70,77,91,101,103,107]
--    λ> take 16 (sucesionSumasDigitales 3)
--    [3,6,12,15,21,24,30,33,39,51,57,69,84,96,111,114]
--    λ> take 16 (sucesionSumasDigitales 5)
--    [5,10,11,13,17,25,32,37,47,58,71,79,95,109,119,130]
--    λ> take 16 (sucesionSumasDigitales 7)
--    [7,14,19,29,40,44,52,59,73,83,94,107,115,122,127,137]
--    λ> take 16 (sucesionSumasDigitales 9)
--    [9,18,27,36,45,54,63,72,81,90,99,117,126,135,144,153]
--    λ> take 16 (sucesionSumasDigitales 20)
--    [20,22,26,34,41,46,56,67,80,88,104,109,119,130,134,142]
sucesionSumasDigitales :: Integer -> [Integer]
sucesionSumasDigitales a =
  iterate siguienteSumaDigital a

-- (siguienteSumaDigital a) es el siguiente de a en la sucesión de sumas
-- digitales. Por ejemplo,
--    siguienteSumaDigital 23 == 28
siguienteSumaDigital :: Integer -> Integer
siguienteSumaDigital a =
  a + sum (digitos a)

-- (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]

-- (noPertenece x ys) se verifica si x no pertenece a la lista infinita
-- ordenada creciente ys. Por ejemplo,
--    noPertenece 2 [1,3..] == True
--    noPertenece 5 [1,3..] == False
noPertenece :: Integer -> [Integer] -> Bool
noPertenece x ys =
  x < head (dropWhile (<x) ys)

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

sucesionSucesionesSumasDigitales2 :: [[Integer]]
sucesionSucesionesSumasDigitales2 =
  map sucesionSumasDigitales autonumeros

-- (autonumero n) se verifica si n es un autonúmero; es decir, números
-- que no se pueden escribir como la suma de un número k y los dígitos
-- de k. Por ejemplo,
--    autonumero 5  == True
--    autonumero 21 == False
autonumero :: Integer -> Bool
autonumero n =
  all (/=n) [k + sum (digitos k) | k <- [1..n]]

-- autonumeros es la lista de los autonúmeros. Por ejemplo,
--    λ> take 20 autonumeros
--    [1,3,5,7,9,20,31,42,53,64,75,86,97,108,110,121,132,143,154,165]
autonumeros :: [Integer]
autonumeros = filter autonumero [1..]

-- 3ª solución
-- ===========

sucesionSucesionesSumasDigitales3 :: [[Integer]]
sucesionSucesionesSumasDigitales3 = aux [1..]
  where aux xs = sucesion xs : aux (diferencia xs (sucesion xs))
        sucesion xs = sucesionSumasDigitales (head xs)

-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas
-- crecientes xs e ys. Por ejemplo,
--    λ> take 8 (diferencia [1..] [2,4..])
--    [1,3,5,7,9,11,13,15]
diferencia :: [Integer] -> [Integer] -> [Integer]
diferencia (x:xs) (y:ys)
  | x == y    = diferencia xs ys
  | otherwise = x : diferencia xs (y:ys)