Números de la suerte
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 |
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 |
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 |
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 |
1, 3, 7, 9, 13, 15, 21, 25... |
Este procedimiento se repite indefinidamente y los supervivientes son
los números de la suerte:
|
1 |
1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79 |
Definir la sucesión
|
1 |
numerosDeLaSuerte :: [Int] |
cuyos elementos son los números de la suerte. Por ejemplo,
|
1 2 3 4 |
λ> 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
-- 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 |