La función indicatriz de Euler
La indicatriz de Euler (también 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
|
1 |
phi :: Integer -> Integer |
tal que phi n es igual a φ(n). Por ejemplo,
|
1 2 3 4 |
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 length (show (phi (10^(10^5)))) == 100000 |
Comprobar con QuickCheck que, para todo n > 0, φ(10^n) tiene n dígitos.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 108 109 |
module La_funcion_indicatriz_de_Euler where import Data.List (genericLength, group) import Data.Numbers.Primes (primeFactors) import Math.NumberTheory.ArithmeticFunctions (totient) import Test.QuickCheck (Positive (Positive), quickCheck) import Test.Hspec (Spec, describe, hspec, it, shouldBe) -- 1ª solución -- =========== phi1 :: Integer -> Integer phi1 n = genericLength [x | x <- [1..n], gcd x n == 1] -- 2ª solució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ª solución -- ============= phi3 :: Integer -> Integer phi3 n = product [(x-1) * product xs | (x:xs) <- group (primeFactors n)] -- 4ª solución -- ============= phi4 :: Integer -> Integer phi4 = totient -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Integer -> Integer) -> Spec specG phi = do it "e1" $ phi 36 `shouldBe` 12 it "e2" $ map phi [10..20] `shouldBe` [4,10,4,12,6,8,8,16,6,18,8] spec :: Spec spec = do describe "def. 1" $ specG phi1 describe "def. 2" $ specG phi2 describe "def. 3" $ specG phi3 describe "def. 4" $ specG phi4 -- La verificación es -- λ> verifica -- -- 8 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_phi :: Positive Integer -> Bool prop_phi (Positive n) = all (== phi1 n) [phi2 n, phi3 n, phi4 n] -- La comprobación es -- λ> quickCheck prop_phi -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> phi1 (2*10^6) -- 800000 -- (2.49 secs, 2,117,853,856 bytes) -- λ> phi2 (2*10^6) -- 800000 -- (0.02 secs, 565,664 bytes) -- -- λ> length (show (phi2 (10^100000))) -- 100000 -- (2.80 secs, 5,110,043,208 bytes) -- λ> length (show (phi3 (10^100000))) -- 100000 -- (4.81 secs, 7,249,353,896 bytes) -- λ> length (show (phi4 (10^100000))) -- 100000 -- (0.78 secs, 1,467,573,768 bytes) -- Verificación de la propiedad -- ============================ -- La propiedad es prop_phi2 :: Positive Integer -> Bool prop_phi2 (Positive n) = genericLength (show (phi4 (10^n))) == n -- La comprobación es -- λ> quickCheck prop_phi2 -- +++ OK, passed 100 tests. |
|
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 |
from functools import reduce from math import gcd from operator import mul from sys import set_int_max_str_digits from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st from sympy import factorint, totient set_int_max_str_digits(10**6) # 1ª solución # =========== def phi1(n: int) -> int: return len([x for x in range(1, n+1) if gcd(x, n) == 1]) # 2ª solución # =========== def producto(xs: list[int]) -> int: return reduce(mul, xs, 1) def phi2(n: int) -> int: factores = factorint(n) return producto([(p-1)*p**(e-1) for p, e in factores.items()]) # 3ª solución # ============= def phi3(n: int) -> int: return totient(n) # Verificación # ============ def test_phi() -> None: for phi in [phi1, phi2, phi3]: assert phi(36) == 12 assert list(map(phi, range(10, 21))) == [4,10,4,12,6,8,8,16,6,18,8] print("Verificado") # La verificación es # >>> test_phi() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_phi_equiv(n: int) -> None: r = phi1(n) assert phi2(n) == r assert phi3(n) == r # La comprobación es # >>> test_phi_equiv() # >>> # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('phi1(9*10**6)') # 2.09 segundos # >>> tiempo('phi2(9*10**6)') # 0.00 segundos # >>> tiempo('phi3(9*10**6)') # 0.00 segundos # # >>> tiempo('phi2(10**1000000)') # 3.55 segundos # >>> tiempo('phi3(10**1000000)') # 3.37 segundos # Verificación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_phi_prop(n: int) -> None: assert len(str(phi2(10**n))) == n # La comprobación es # >>> test_phi_prop() # >>> # Comprobación de todas las propiedades # ===================================== # La comprobación es # src> poetry run pytest -v La_funcion_indicatriz_de_Euler.py # ===== test session starts ===== # test_phi PASSED # test_phi_equiv PASSED # test_phi_prop PASSED # ===== passed in 0.55s ===== |