Números de la suerte

José A. Alonso

16-12-2016

Un número de la suerte es un número natural que se genera por una criba, similar a la criba de Eratóstenes, como se indica a continuación:

Se comienza con la lista de los números enteros a partir de 1:

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

Se eliminan los números de dos en dos

1,  3,  5,  7,  9,   11,   13,   15,   17,   19,   21,   23,   25...

Como el segundo número que ha quedado es 3, se eliminan los números restantes de tres en tres:

1,  3,      7,  9,         13,   15,         19,   21,         25...

Como el tercer número que ha quedado es 7, se eliminan los números restantes de siete en siete:

1,  3,      7,  9,         13,   15,               21,         25...

Este procedimiento se repite indefinidamente y los supervivientes son los números de la suerte:

1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79

Definir la sucesión

numerosDeLaSuerte :: [Int]

cuyos elementos son los números de la suerte. Por ejemplo,

λ> take 20 numerosDeLaSuerte
[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79]
λ> numerosDeLaSuerte !! 1500
13995

Soluciones

-- 1ª definición
numerosDeLaSuerte :: [Int]
numerosDeLaSuerte = criba 3 [1,3..]
  where
    criba i (n:s:xs) =
      n : criba (i + 1) (s : [x | (n, x) <- zip [i..] xs
                                , rem n s /= 0])

-- 2ª definición
numerosDeLaSuerte2 :: [Int]
numerosDeLaSuerte2 =  1 : criba 2 [1, 3..]
  where criba k xs = z : criba (k + 1) (aux xs)
          where z = xs !! (k - 1 )
                aux ws = us ++ aux vs
                  where (us, _:vs) = splitAt (z - 1) ws