Números que no son sumas de progresiones aritméticas de diferencia dos
El número 4 es la suma de números enteros positivos en progresión aritmética de diferencia dos (ya que es 1+3) y también lo es el 6 (ya que es 2+4) y el 9 (ya que es (1+3+5), pero el 5 no lo es.
Definir la función
1 |
noSonSumasDePADeDiferenciaDos :: [Integer] |
cuyos elementos son los números que no se pueden escribir como sumas de progresiones aritméticas de diferencia dos, con al menos dos términos, de números enteros positivos. Por ejemplo,
1 2 |
noSonSumasDePADeDiferenciaDos !! 3 == 5 noSonSumasDePADeDiferenciaDos !! (10^6) == 15485863 |
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
import Data.List (foldr1) import Data.Numbers.Primes (primes) -- 1ª solución -- =========== noSonSumasDePADeDiferenciaDos :: [Integer] noSonSumasDePADeDiferenciaDos = diferencia [1..] sonSumasDePADeDiferenciaDos -- sonSumasDePADeDiferenciaDos es la lista de los números que se pueden -- escribir como sumas de progresiones aritméticas de diferencia dos, -- con al menos dos términos, de números enteros positivos. Por ejemplo, -- λ> take 10 sonSumasDePADeDiferenciaDos -- [4,6,8,9,10,12,14,15,16,18] sonSumasDePADeDiferenciaDos :: [Integer] sonSumasDePADeDiferenciaDos = mezclaTodas [sumasDePADeDiferenciaDos a | a <- [1..]] -- (sumasDePADeDiferenciaDos a) es la lista de las sumas de la -- progresión aritmética de término inicial a y diferencia dos. Por -- ejemplo, -- take 7 (sumasDePADeDiferenciaDos 1) == [4,9,16,25,36,49,64] -- take 7 (sumasDePADeDiferenciaDos 2) == [6,12,20,30,42,56,72] -- take 7 (sumasDePADeDiferenciaDos 3) == [8,15,24,35,48,63,80] sumasDePADeDiferenciaDos :: Integer -> [Integer] sumasDePADeDiferenciaDos a = tail (scanl1 (+) [a,a+2..]) -- (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 15 noSonSumasDePADeDiferenciaDos -- [1,2,3,5,7,11,13,17,19,23,29,31,37,41,43] noSonSumasDePADeDiferenciaDos2 :: [Integer] noSonSumasDePADeDiferenciaDos2 = 1 : primes -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> noSonSumasDePADeDiferenciaDos !! 1000 -- 7919 -- (3.58 secs, 3,304,841,840 bytes) -- λ> noSonSumasDePADeDiferenciaDos2 !! 1000 -- 7919 -- (0.01 secs, 2,316,896 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>