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
1 |
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,
1 2 3 |
(noSonSumasDePADeDiferencia 3) !! 4 == 6 (noSonSumasDePADeDiferencia 3) !! 100 == 6848 (noSonSumasDePADeDiferencia 9) !! 200 == 6752 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
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>