Sucesiones sin progresiones aritméticas de longitud 3

José A. Alonso

21-01-2020

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

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

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,

λ> 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

import Data.List ((\\), delete, tails)

-- 1ª solución
-- ===========

sucesionSin3enPA1 :: [Integer]
sucesionSin3enPA1 = 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.

sucesionSin3enPA :: [Integer]
sucesionSin3enPA = aux [] [0..]
  where
    aux xs (y:ys) = y : aux (y:xs) (ys \\ [2 * y - x | x <- xs])

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> sucesionSin3enPA1 !! 70
--    741
--    (7.97 secs, 5,444,053,240 bytes)
--    λ> sucesionSin3enPA !! 70
--    741
--    (0.03 secs, 35,781,952 bytes)