La función indicatriz de Euler
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, φ(36) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.
Definir la función
phi :: Integer -> Integer
tal que (phi n) es igual a φ(n). Por ejemplo,
phi 36 == 12 map phi [10..20] == [4,10,4,12,6,8,8,16,6,18,8] phi (3^10^5) `mod` (10^9) == 681333334
Comprobar con QuickCheck que, para todo n > 0, φ(10ⁿ) tiene n dígitos.
Soluciones
import Data.List (genericLength, group) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck -- 1ª definición -- ============= phi1 :: Integer -> Integer phi1 n = genericLength [x | x <- [1..n], gcd x n == 1] -- 2ª definición -- ============= phi2 :: Integer -> Integer phi2 n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n] factorizacion :: Integer -> [(Integer,Integer)] factorizacion n = [(head xs,genericLength xs) | xs <- group (primeFactors n)] -- 3ª definición -- ============= phi3 :: Integer -> Integer phi3 n = product [(x-1) * product xs | (x:xs) <- group (primeFactors n)] -- Comparación de eficiencia -- ========================= -- λ> phi1 (2*10^6) -- 800000 -- (4.48 secs, 1071406224 bytes) -- λ> phi2 (2*10^6) -- 800000 -- (0.01 secs, 1553372 bytes) -- λ> phi3 (2*10^6) -- 800000 -- (0.01 secs, 1602152 bytes) -- -- λ> and [length (show (phi1 (2*10^n))) == n | n <- [1..6]] -- True -- (4.91 secs, 1177179016 bytes) -- λ> and [length (show (phi2 (2*10^n))) == n | n <- [1..6]] -- True -- (0.01 secs, 1038132 bytes) -- λ> and [length (show (phi3 (2*10^n))) == n | n <- [1..6]] -- True -- (0.01 secs, 1038072 bytes) -- Verificación de la propiedad -- ============================ -- La propiedad es prop_phi :: Integer -> Property prop_phi n = n > 0 ==> genericLength (show (phi2 (10^n))) == n -- La comprobación es -- λ> quickCheck prop_phi -- +++ OK, passed 100 tests.