Números cíclicos
La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo,
- φ(15) = 8 ya que los números menores o iguales a 36 y coprimos con 36 son ocho: 1, 2, 4, 7, 8, 11, 13 y 14.
- φ(21) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 y 20.
Un número n es un número cíclico si n y φ(n) no tiene ningún divisor primo común. Por ejemplo, el número 15 es cíclico ya que 15 y 8 (que es φ(15)) no tiene ningún divisor primo común; en cambio, el número 21 no es cíclico ya 21 y 12 (que es φ(21)) son divisibles por 3.
Definir las funciones
1 2 |
esCiclico :: Integer -> Bool ciclicos :: [Integer] |
tales que
- (esCiclico n) se verifica si n es un número cíclico. Por ejemplo,
1 2 3 4 |
esCiclico 15 == True esCiclico 16 == False esCiclico 2021 == True esCiclico (product [1..10^4]) == False |
- ciclicos es la lista de los números cíclicos. Por ejemplo,
1 2 3 4 |
λ> take 20 ciclicos [2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53] λ> ciclicos !! (10^5) 336059 |
Comprobar con QuickCheck que todos los números primos mayores que 2 son cíclicos.
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 |
module Numeros_ciclicos where import Data.List (genericLength, group) import Data.Numbers.Primes (primeFactors, primes) import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª definición -- ============= ciclicos1 :: [Integer] ciclicos1 = filter esCiclico1 [2..] esCiclico1 :: Integer -> Bool esCiclico1 n = gcd n (phi1 n) == 1 -- (phi1 n) es igual a φ(n). Por ejemplo, -- phi1 15 == 8 -- phi1 21 == 12 -- phi1 2021 == 1932 phi1 :: Integer -> Integer phi1 n = genericLength [x | x <- [1..n], gcd x n == 1] -- 2ª definición -- ============= ciclicos2 :: [Integer] ciclicos2 = filter esCiclico2 [2..] esCiclico2 :: Integer -> Bool esCiclico2 n = gcd n (phi2 n) == 1 -- (phi2 n) es igual a φ(n). Por ejemplo, -- phi2 15 == 8 -- phi2 21 == 12 -- phi2 2021 == 1932 phi2 :: Integer -> Integer phi2 n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n] -- (factorizacion n) es la descomposición de n en factores primos como -- una lista de pares donde los primeros elementos son la base y los -- segundo son los exponentes. Por ejemplo, -- factorizacion 3000 == [(2,3),(3,1),(5,3)] -- ya que 3000 = 2^3*3*5^3 factorizacion :: Integer -> [(Integer,Integer)] factorizacion n = [(head xs,genericLength xs) | xs <- group (primeFactors n)] -- 3ª definición -- ============= ciclicos3 :: [Integer] ciclicos3 = filter esCiclico3 [2..] esCiclico3 :: Integer -> Bool esCiclico3 n = gcd n (phi3 n) == 1 -- (phi3 n) es igual a φ(n). Por ejemplo, -- phi3 15 == 8 -- phi3 21 == 12 -- phi3 2021 == 1932 phi3 :: Integer -> Integer phi3 n = product [(x-1) * product xs | (x:xs) <- group (primeFactors n)] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esCiclico1 (4*10^6) -- False -- (3.64 secs, 4,448,223,616 bytes) -- λ> esCiclico2 (4*10^6) -- False -- (0.01 secs, 116,144 bytes) -- λ> esCiclico3 (4*10^6) -- False -- (0.01 secs, 111,336 bytes) -- -- λ> esCiclico2 (product [1..3*10^4]) -- False -- (2.49 secs, 5,846,361,904 bytes) -- λ> esCiclico3 (product [1..3*10^4]) -- False -- (2.50 secs, 5,947,164,552 bytes) -- Verificación de la propiedad -- ============================ -- La propiedad es prop_ciclicos :: Int -> Property prop_ciclicos n = n > 1 ==> esCiclico3 (primes !! n) -- La comprobación es -- λ> quickCheck prop_ciclicos -- +++ OK, passed 100 tests. verificacion :: IO () verificacion = quickCheck prop_ciclicos |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Con la definición de ciclicos’ en mi ordenador no se puede calcular el último ejemplo.