Primos circulares
Un primo circular es un número tal que todas las rotaciones de dígitos producen números primos. Por ejemplo, 195 es un primo circular ya que las rotaciones de sus dígitos son 197, 971 y 719 y los tres números son primos.
Definir la lista
|
1 |
circulares :: [Integer] |
cuyo valor es la lista de los números primos circulares. Por ejemplo,
|
1 2 |
take 16 circulares == [2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,197] circulares !! 50 == 933199 |
Soluciones
|
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
import Data.Numbers.Primes (isPrime, primes) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== circulares1 :: [Integer] circulares1 = filter esCircular1 primes -- (esCircular1 n) se verifica si n es un número circular. Por ejemplo, -- esCircular1 197 == True -- esCircular1 157 == False esCircular1 :: Integer -> Bool esCircular1 = all (isPrime . read) . rotaciones1 . show -- (rotaciones1 xs) es la lista de las rotaciones obtenidas desplazando -- el primer elemento xs al final. Por ejemplo, -- rotaciones1 [2,3,5] == [[2,3,5],[3,5,2],[5,2,3]] rotaciones1 :: [a] -> [[a]] rotaciones1 xs = reverse (aux (length xs) [xs]) where aux 1 yss = yss aux n (ys:yss) = aux (n-1) (rota ys : ys :yss) -- 2ª solución -- =========== circulares2 :: [Integer] circulares2 = filter esCircular2 primes esCircular2 :: Integer -> Bool esCircular2 = all (isPrime . read) . rotaciones2 . show rotaciones2 :: [a] -> [[a]] rotaciones2 xs = take (length xs) (iterate rota xs) -- (rota xs) es la lista añadiendo el primer elemento de xs al -- final. Por ejemplo, -- rota [3,2,5,7] == [2,5,7,3] rota :: [a] -> [a] rota (x:xs) = xs ++ [x] -- 3ª solución -- =========== circulares3 :: [Integer] circulares3 = filter (all isPrime . rotaciones3) primes rotaciones3 :: Integer -> [Integer] rotaciones3 n = [read (take m (drop i (cycle s))) | i <- [1..m]] where s = show n m = length s -- 4ª definición -- ============= -- Nota. La 4ª definición es una mejora observando que para que n sea un -- número primo circular es necesario que todos los dígitos de n sean -- impares, salvo para n = 2. circulares4 :: [Integer] circulares4 = 2 : filter esCircular4 primes -- (esCircular4 n) se verifica si n es un número circular. Por ejemplo, -- esCircular4 197 == True -- esCircular4 157 == False esCircular4 :: Integer -> Bool esCircular4 n = digitosImpares n && all (isPrime . read) (rotaciones2 (show n)) -- (digitosImpares n) se verifica si todos los dígitos de n son -- impares. Por ejemplo, -- digitosImpares 7351 == True -- digitosImpares 7341 == False digitosImpares :: Integer -> Bool digitosImpares = all (`elem` "135679") . show -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_circulares :: Positive Int -> Bool prop_circulares (Positive n) = all (== circulares1 !! n) [circulares2 !! n, circulares3 !! n, circulares4 !! n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=50}) prop_circulares -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> circulares1 !! 46 -- 331999 -- (2.08 secs, 7,229,208,200 bytes) -- λ> circulares2 !! 46 -- 331999 -- (1.93 secs, 7,165,043,992 bytes) -- λ> circulares3 !! 46 -- 331999 -- (0.74 secs, 2,469,098,648 bytes) -- λ> circulares4 !! 46 -- 331999 -- (0.28 secs, 917,501,600 bytes) |
El código se encuentra en GitHub.