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

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

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,  3,      7,  9,         13,   15,         19,   21,         25...

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,  3,      7,  9,         13,   15,               21,         25...

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,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79

1	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

1 2	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

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

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)

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

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)

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)

Responder

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)

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)

Responder

El 2019 es un número de la suerte

Soluciones

Pensamiento

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico