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
|
1 |
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,
|
1 2 |
noSonSumasDePADeDiferenciaUno !! 2 == 4 length (show (noSonSumasDePADeDiferenciaUno !! (10^7))) == 3010300 |
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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
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>