Sucesiones de sumas digitales

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,...

1	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,...

1	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,...

1	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,...

1	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,...

1	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,...

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

Definir la función

   sucesionSucesionesSumasDigitales :: [[Integer]]

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

λ> 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)

-- 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)

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>

import Data.List (union)

-- Este comentario es una continuación directa del anterior. Tras mucho tiempo
-- de búsqueda, parece que los primeros elementos de cada elemento de la
-- sucesión siguen el siguiente patrón:
--   + Los primeros 4 elementos son [1,3,5,7]
--   + A partir de la lista [9,20..108], realizamos lo siguiente:
--       + Comenzamos sumando a dicha lista 101 para llegar a [110,121..209].
--         A continuación volvemos a sumar 101 y así sucesivamente hasta
--         llegar al primer elemento mayor que 1000.
--       + Una vez hemos obtenido la lista [9,20..1006], eliminamos el
--         primer elemento y esta vez sumamos 1001 hasta llegar al primer
--         elemento mayor que 10000.
--       + En general, siempre eliminamos el primer elemento y vamos sumando
--         10^k + 1 hasta llegar al primer elemento mayor que 10^(k+1).

lista :: [Integer]
lista = [1,3,5,7] ++ [9,20..108] ++ aux 2 [9,20..108]
  where aux k xs = ys ++ aux (k+1) (union (tail xs) ys)
          where ys = takeWhile (< 10^(k+1)+11) (concat (aplica 9 (map (+m)) xs))
                m = 1 + 10^k
                aplica 1 f xs = [f xs]
                aplica n f xs = f xs : aplica (n-1) f (f xs)

sucesionSucesionesSumasDigitalesOpt :: [[Integer]]
sucesionSucesionesSumasDigitalesOpt = map sucesionDefinidaPor lista

-- Comparación de eficiencia:
-- =========================
--
-- λ> take 10 (sucesionSucesionesSumasDigitales !! 1000)
-- [10199,10219,10232,10240,10247,10261,10271,10282,10295,10312]
-- (2.42 secs, 1,466,733,640 bytes)
--
-- λ> take 10 (sucesionSucesionesSumasDigitalesOpt !! 1000)
-- [10199,10219,10232,10240,10247,10261,10271,10282,10295,10312]
-- (0.02 secs, 801,752 bytes)

import Data.List (union)

-- Este comentario es una continuación directa del anterior. Tras mucho tiempo

-- de búsqueda, parece que los primeros elementos de cada elemento de la

-- sucesión siguen el siguiente patrón:

-- + Los primeros 4 elementos son [1,3,5,7]

-- + A partir de la lista [9,20..108], realizamos lo siguiente:

-- + Comenzamos sumando a dicha lista 101 para llegar a [110,121..209].

-- A continuación volvemos a sumar 101 y así sucesivamente hasta

-- llegar al primer elemento mayor que 1000.

-- + Una vez hemos obtenido la lista [9,20..1006], eliminamos el

-- primer elemento y esta vez sumamos 1001 hasta llegar al primer

-- elemento mayor que 10000.

-- + En general, siempre eliminamos el primer elemento y vamos sumando

-- 10^k + 1 hasta llegar al primer elemento mayor que 10^(k+1).

lista :: [Integer]

lista = [1,3,5,7] ++ [9,20..108] ++ aux 2 [9,20..108]

where aux k xs = ys ++ aux (k+1) (union (tail xs) ys)

where ys = takeWhile (< 10^(k+1)+11) (concat (aplica 9 (map (+m)) xs))

m = 1 + 10^k

aplica 1 f xs = [f xs]

aplica n f xs = f xs : aplica (n-1) f (f xs)

sucesionSucesionesSumasDigitalesOpt :: [[Integer]]

sucesionSucesionesSumasDigitalesOpt = map sucesionDefinidaPor lista

-- Comparación de eficiencia:

-- =========================

-- λ> take 10 (sucesionSucesionesSumasDigitales !! 1000)

-- [10199,10219,10232,10240,10247,10261,10271,10282,10295,10312]

-- (2.42 secs, 1,466,733,640 bytes)

-- λ> take 10 (sucesionSucesionesSumasDigitalesOpt !! 1000)

-- [10199,10219,10232,10240,10247,10261,10271,10282,10295,10312]

-- (0.02 secs, 801,752 bytes)

Responder

Sucesiones de sumas digitales

Soluciones

Nuevas soluciones

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico