Sucesiones sin progresiones aritméticas de longitud 3
Tres números x, y, z está en progresión aritmética (PA) si existe un d tal que y = x+d y z = y+d. Por ejemplo, 1, 3, 5 están en PA ya que 3 = 1+2 y 5 = 3+2.
Se considera la sucesión donde cada uno de sus términos es el número natural tal que no está en PA con cualesquiera dos términos anteriores de la sucesión. Por ejemplo, si representamos por f(n) el n-ésimo término de la sucesión, entonces
1 2 3 4 5 6 7 8 9 10 11 12 |
f(0) = 0, que es el menor número natural; f(1) = 1, que es el menor número natural que no está en la sucesión; f(2) = 3, ya que [0, 1, 2] están en PA y [0, 1, 3] no están en PA; f(3) = 4, ya que [0, 1, 4], [0, 3, 4] y [1, 3, 4] no están en PA; f(4) = 9, ya que se descartan + el 5 porque [1, 3, 5] están en PA + el 6 porque [0, 3, 6] están en PA + el 7 porque [1, 4, 7] están en PA + el 8 porque [0, 4, 8] estan en PA y se acepta el 9 porque no están en PA niguna de [0,1,9], [0,3,9], [0,4,9], [1,3,9], [1,4,9], [3,4,9]. |
Definir la sucesión
1 |
sucesionSin3enPA :: [Integer] |
donde cada uno de sus términos es el menor número natural tal que no está en PA con cualesquiera dos términos anteriores de la sucesión. Por ejemplo,
1 2 3 4 |
λ> take 20 sucesionSin3enPA [0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85] λ> sucesionSin3enPA !! 250 3270 |
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 |
import Data.List ((\\), delete, tails) -- 1ª solución -- =========== sucesionSin3enPA :: [Integer] sucesionSin3enPA = aux [] where aux xs = x : aux (x:xs) where x = head (noEnPAConDos xs) noEnPAConDos :: [Integer] -> [Integer] noEnPAConDos xs = [z | z <- [0..] , z `notElem` xs , and [z - y /= y - x | x <- xs , y <- dropWhile (<= x) xs]] -- 2ª solución -- =========== -- Si x, y, z están en progresión aritmética, entonces -- y = (x + z) / 2 -- Por tanto, -- z = 2 * y - x -- -- Teniendo en cuenta la relación auterior se define (aux xs ys) tal que -- xs es la lista de los términos actuales de la sucesión e ys es la -- lista de los números que no están en PA con cualesquieras dos de xs. sucesionSin3enPA2 :: [Integer] sucesionSin3enPA2 = aux [] [0..] where aux xs (y:ys) = y : aux (y:xs) (ys \\ [2 * y - x | x <- xs]) -- 3º solución -- =========== sucesionSin3enPA3 :: [Integer] sucesionSin3enPA3 = 0 : aux [1] where aux (x:xs) = x : aux (xs ++ [3*x,3*x+1]) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sucesionSin3enPA !! 70 -- 741 -- (7.97 secs, 5,444,053,240 bytes) -- λ> sucesionSin3enPA2 !! 70 -- 741 -- (0.03 secs, 35,781,952 bytes) -- λ> sucesionSin3enPA3 !! 70 -- 741 -- (0.01 secs, 192,864 bytes) -- -- λ> sucesionSin3enPA2 !! 350 -- 7410 -- (9.46 secs, 10,119,851,016 bytes) -- λ> sucesionSin3enPA3 !! 350 -- 7410 -- (0.01 secs, 1,931,296 bytes) |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
Quien se vive se pierde, Abel decía.
¡Oh, distancia, distancia!, que la estrella
que nadie toca, guía.
¿Quién navegó sin ella?Antonio Machado
2 Comentarios