Primos que contienen al 2016

3 Comentarios

1. Haskell

   import Data.Numbers.Primes (primes) import Data.List (isPrefixOf) primosCon2016 :: [Integer] primosCon2016 = [x | x <- primes, x > 12016, p (digitos x)] where p [] = False p xs = isPrefixOf [2,0,1,6] xs || p (tail xs) digitos n = [read [c] | c <- show n] -- *Main> primosCon2016 !! 111 -- 3020167 -- (9.84 secs, 5,375,659,288 bytes)

   1 2 3 4 5 6 7 8 9 10 11 12

   import Data.Numbers.Primes (primes) import Data.List (isPrefixOf)   primosCon2016 :: [Integer] primosCon2016 = [x | x <- primes, x > 12016, p (digitos x)]                 where p [] = False                       p xs = isPrefixOf [2,0,1,6] xs || p (tail xs)                       digitos n = [read [c] | c <- show n]   -- *Main> primosCon2016 !! 111 -- 3020167 -- (9.84 secs, 5,375,659,288 bytes)

   Responder

2. Mejor que revisar todos los primos resulta enumerar aquellos impares que contienen 2016 (de los que también podrían eliminarse los 5).

   Haskell

   import Data.Numbers.Primes import qualified Data.Heap as H data E2016 = E2016 { n :: ℤ -- Valor precalculado , f :: Bool -- Si hay que expandir rama B , a :: ℤ, p :: ℤ, b :: ℤ -- n = (a * 10000 + 2016) * 10^p + b } deriving (Show, Eq, Ord) mkE f a p b = E2016 (a * p + b) f a p b nextA E2016 {…} = mkE True (a + 10000) p b nextB E2016 {…} | b + 2 > p = mkE False a (10 * p) 1 | otherwise = mkE False a p (b + 2) -- pueden evitarse los 5 e2016 :: [ℤ] e2016 = next (H.singleton (mkE True 2016 1 0) :: H.MinHeap E2016) where next h = let Just (e@(E2016 n f _ _ _), y) = H.view h z = if f then H.insert (nextA e) y else y in n: next (H.insert (nextB e) z) primosCon2016A :: [ℤ] primosCon2016A = filter isPrime e2016 {- Comparando las dos soluciones aportadas: Revisando dígitos: 111 3020167 Mem: 5600 kbytes. Time: 0:04.86 500 20162029 Mem: 5580 kbytes. Time: 0:32.98 Enumerando aa2016bb: 111 3020167 Mem: 4136 kbytes. Time: 0:00.00 500 20162029 Mem: 4744 kbytes. Time: 0:00.03 1000 20201651 Mem: 4640 kbytes. Time: 0:00.06 2000 78920161 Mem: 6540 kbytes. Time: 0:00.18 4000 172016087 Mem: 10144 kbytes. Time: 0:00.50 8000 201666991 Mem: 10264 kbytes. Time: 0:01.23 16000 513720169 Mem: 21808 kbytes. Time: 0:03.09 -}

   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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

   import Data.Numbers.Primes import qualified Data.Heap as H   data E2016 = E2016 { n :: ℤ                 -- Valor precalculado                    , f :: Bool              -- Si hay que expandir rama B                    , a :: ℤ, p :: ℤ, b :: ℤ -- n = (a * 10000 + 2016) * 10^p + b                    } deriving (Show, Eq, Ord)   mkE f a p b = E2016 (a * p + b) f a p b   nextA E2016 {…} = mkE True (a + 10000) p b nextB E2016 {…} | b + 2 > p = mkE False a (10 * p) 1                 | otherwise = mkE False a p (b + 2) -- pueden evitarse los 5   e2016 :: [ℤ] e2016 = next (H.singleton (mkE True 2016 1 0) :: H.MinHeap E2016)   where next h = let Just (e@(E2016 n f _ _ _), y) = H.view h                      z = if f then H.insert (nextA e) y else y                  in  n: next (H.insert (nextB e) z)   primosCon2016A :: [ℤ] primosCon2016A = filter isPrime e2016   {-   Comparando las dos soluciones aportadas:   Revisando dígitos:     111     3020167     Mem:  5600 kbytes. Time: 0:04.86     500    20162029     Mem:  5580 kbytes. Time: 0:32.98   Enumerando aa2016bb:     111     3020167     Mem:  4136 kbytes. Time: 0:00.00     500    20162029     Mem:  4744 kbytes. Time: 0:00.03    1000    20201651     Mem:  4640 kbytes. Time: 0:00.06    2000    78920161     Mem:  6540 kbytes. Time: 0:00.18    4000   172016087     Mem: 10144 kbytes. Time: 0:00.50    8000   201666991     Mem: 10264 kbytes. Time: 0:01.23   16000   513720169     Mem: 21808 kbytes. Time: 0:03.09   -}

   Responder

3. Haskell

   import Data.Numbers.Primes (primes) import Data.List (isInfixOf) primosCon2016 :: [Integer] primosCon2016 = filter (isInfixOf "2016" . show) primes

   1 2 3 4 5

   import Data.Numbers.Primes (primes) import Data.List (isInfixOf)   primosCon2016 :: [Integer] primosCon2016 = filter (isInfixOf "2016" . show) primes

   Responder