Menu Close

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

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

Definir la función

   noSonSumasDePADeDiferencia :: Integer -> [Integer]

tal que (noSonSumasDePADeDiferencia d) es la lista de los números no se pueden escribir como sumas de progresiones aritméticas de diferencia d, con al menos términos, de números enteros positivos. Por ejemplo,

   (noSonSumasDePADeDiferencia 3) !! 4    ==  6
   (noSonSumasDePADeDiferencia 3) !! 100  ==  6848
   (noSonSumasDePADeDiferencia 9) !! 200  ==  6752

Soluciones

import Data.List (foldr1)
 
-- 1ª solución
-- ===========
 
noSonSumasDePADeDiferencia :: Integer -> [Integer]
noSonSumasDePADeDiferencia d =
  diferencia [1..] (sonSumasDePADeDiferencia d)
 
-- (sonSumasDePADeDiferencia d) es la lista de los números que se pueden
-- escribir como sumas de progresiones aritméticas de diferencia d,
-- con al menos dos términos, de números enteros positivos. Por ejemplo,
--    λ> take 15 (sonSumasDePADeDiferencia 3)
--    [5,7,9,11,12,13,15,17,18,19,21,22,23,24,25]
sonSumasDePADeDiferencia :: Integer -> [Integer]
sonSumasDePADeDiferencia d =
  mezclaTodas [sumasDePADeDiferencia d a | a <- [1..]]
 
-- (sumasDePADeDiferencia a) es la lista de las sumas de la
-- progresión aritmética de término inicial a y diferencia . Por
-- ejemplo,
--    take 7 (sumasDePADeDiferencia 3 1)  ==  [5,12,22,35,51,70,92]
--    take 7 (sumasDePADeDiferencia 3 2)  ==  [7,15,26,40,57,77,100]
--    take 7 (sumasDePADeDiferencia 3 3)  ==  [9,18,30,45,63,84,108]
sumasDePADeDiferencia :: Integer -> Integer -> [Integer]
sumasDePADeDiferencia d a =
  tail (scanl1 (+) [a,a+d..])
 
-- (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  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)

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.