Menu Close

El 2019 es un número 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,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 las funciones

   numerosDeLaSuerte  :: [Int]
   esNumeroDeLaSuerte :: Int -> Bool

tales que

  • numerosDeLaSuerte es la sucesión de 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 !! 277
     2019
     λ> numerosDeLaSuerte !! 2000
     19309
  • (esNumeroDeLaSuerte n) que se verifica si n es un número de la suerte. Por ejemplo,
   esNumeroDeLaSuerte 15    ==  True
   esNumeroDeLaSuerte 16    ==  False
   esNumeroDeLaSuerte 2019  ==  True

Soluciones

-- 1ª definición de numerosDeLaSuerte 
numerosDeLaSuerte :: [Int]
numerosDeLaSuerte = criba 3 [1,3..]
  where
    criba i (n:s:xs) =
      n : criba (i + 1) (s : [x | (k, x) <- zip [i..] xs
                                , rem k s /= 0])
 
-- 2ª definición de numerosDeLaSuerte 
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 
 
-- Comparación de eficiencia
-- =========================
 
--    λ> numerosDeLaSuerte2 !! 200
--    1387
--    (9.25 secs, 2,863,983,232 bytes)
--    λ> numerosDeLaSuerte !! 200
--    1387
--    (0.06 secs, 10,263,880 bytes)
 
-- Definición de esNumeroDeLaSuerte
esNumeroDeLaSuerte :: Int -> Bool
esNumeroDeLaSuerte n =
  n == head (dropWhile (<n) numerosDeLaSuerte)

Pensamiento

Ya es sólo brocal el pozo;
púlpito será mañana;
pasado mañana, trono.

Antonio Machado

2 soluciones de “El 2019 es un número de la suerte

  1. frahidzam
    numerosDeLaSuerte :: [Int]
    numerosDeLaSuerte = 1 : aux 2 [3,5..]
      where aux k (n:s) = n : aux (k+1) (quitan n (n-k) s)
     
    quitan :: Int -> Int -> [Int] -> [Int]
    quitan n 1 (a:s) = quitan n n s
    quitan n m (a:s) = a : quitan n (m-1) s
     
    esNumeroDeLaSuerte :: Int -> Bool
    esNumeroDeLaSuerte n =
      elem n (takeWhile (<=n) numerosDeLaSuerte)
  2. javmarcha1
    import Data.List
     
    numerosDeLaSuerte :: [Int]
    numerosDeLaSuerte =
      nub (concat [eliminatodos 2 (take n impares) | n <- potencias4])
     
    potencias4 :: [Int]  
    potencias4 = [4^n | n <- [1..]]
     
    impares :: [Int]
    impares = [x | x <- [1..] , odd x]
     
    eliminatodos :: Int -> [Int] -> [Int]
    eliminatodos x xs
      | length xs < x = xs
      | otherwise     = elimina (xs !! (x-1)) xs `intersect`
                        eliminatodos (x+1) (elimina (xs !! (x-1)) xs)
     
    elimina :: Int -> [Int] -> [Int]
    elimina x xs = xs  borrar x xs
     
    borrar :: Int -> [Int] -> [Int]
    borrar x xs = [ y | y <- xs , esMultiplo (posicion y xs) x]
     
    esMultiplo :: Int -> Int -> Bool
    esMultiplo x y = x `elem` multiplosmenores y x
     
    multiplosmenores :: Int -> Int -> [Int]
    multiplosmenores x y = [n*x | n <- [1..y], (n*x) <= y]
     
    posicion :: Int -> [Int] -> Int
    posicion x xs = head (elemIndices x xs) +1
     
    esNumeroDeLaSuerte :: Int -> Bool
    esNumeroDeLaSuerte n =
      n `elem` eliminatodos 2 (take (quot n 2 + 1) impares)

Leave a Reply to javmarcha1 Cancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.