Menu Close

Números que no son sumas de progresiones aritméticas de diferencia uno

El número 3 es la suma de números enteros positivos en progresión aritmética de diferencia uno (ya que es 1+2) y también lo es el 5 (ya que es 2+3) y el 6 (ya que es (1+2+3), pero el 4 no lo es.

Definir la función

   noSonSumasDePADeDiferenciaUno :: [Integer]

cuyos elementos son los números que no se pueden escribir como de progresiones aritméticas de diferencia uno, con al menos dos términos, de números enteros positivos. Por ejemplo,

   noSonSumasDePADeDiferenciaUno !! 2  ==  4
   length (show (noSonSumasDePADeDiferenciaUno !! (10^7))) == 3010300

Soluciones

import Data.List (foldr1)
 
-- 1ª solución
-- ===========
 
noSonSumasDePADeDiferenciaUno :: [Integer]
noSonSumasDePADeDiferenciaUno =
  diferencia [1..] sonSumasDePADeDiferenciaUno
 
-- sonSumasDePADeDiferenciaUno es la lista de los números que se pueden
-- escribir como sumas de progresiones aritméticas de diferencia uno,
-- con al menos dos términos, de números enteros positivos. Por ejemplo,
--    λ> take 10 sonSumasDePADeDiferenciaUno
--    [3,5,6,7,9,10,11,12,13,14]
sonSumasDePADeDiferenciaUno :: [Integer]
sonSumasDePADeDiferenciaUno =
  mezclaTodas [sumasDePADeDiferenciaUno a | a <- [1..]]
 
-- (sumasDePADeDiferenciaUno a) es la lista de las sumas de la
-- progresión aritmética de término inicial a y diferencia uno. Por
-- ejemplo,
--    take 7 (sumasDePADeDiferenciaUno 1)  ==  [3,6,10,15,21,28,36]
--    take 7 (sumasDePADeDiferenciaUno 2)  ==  [5,9,14,20,27,35,44]
--    take 7 (sumasDePADeDiferenciaUno 3)  ==  [7,12,18,25,33,42,52]
sumasDePADeDiferenciaUno :: Integer -> [Integer]
sumasDePADeDiferenciaUno a =
  tail (scanl1 (+) [a,a+1..])
 
-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo,
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
--    [2,3,4,5,6,7,8,9,10,11]
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
--    [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys
 
-- (mezcla xs ys) es la lista obtenida mezclando las dos lista infinitas
-- ordenadas crecientes xs e ys. Por ejemplo,
--    λ> take 20 (mezcla [1,3..] [2,5..])
--    [1,2,3,5,7,8,9,11,13,14,15,17,19,20,21,23,25,26,27,29]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys
 
-- (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)
 
-- 2ª solución
-- ===========
 
-- Observando el siguiente cálculo
--    λ> take 10 noSonSumasDePADeDiferenciaUno
--    [1,2,4,8,16,32,64,128,256,512]
noSonSumasDePADeDiferenciaUno2 :: [Integer]
noSonSumasDePADeDiferenciaUno2 = [2^k | k <- [0..]]
 
-- 3ª solución
-- ===========
 
noSonSumasDePADeDiferenciaUno3 :: [Integer]
noSonSumasDePADeDiferenciaUno3 =
  iterate (*2) 1
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> noSonSumasDePADeDiferenciaUno !! 14
--    16384
--    (36.00 secs, 28,609,441,984 bytes)
--    λ> noSonSumasDePADeDiferenciaUno2 !! 14
--    16384
--    (0.01 secs, 102,712 bytes)
--    λ> noSonSumasDePADeDiferenciaUno3 !! 14
--    16384
--    (0.00 secs, 102,432 bytes)
--
--    λ> length (show (noSonSumasDePADeDiferenciaUno3 !! (3*10^5)))
--    90309
--    (2.78 secs, 5,770,583,328 bytes)
--    λ> length (show (noSonSumasDePADeDiferenciaUno2 !! (3*10^5)))
--    90309
--    (0.09 secs, 60,840,304 bytes)
--
--    λ> length (show (noSonSumasDePADeDiferenciaUno2 !! (10^7)))
--    3010300
--    (3.55 secs, 2,030,646,392 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>

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.