Ir al contenido principal

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

esCiclico :: Integer -> Bool
ciclicos  :: [Integer]

tales que

  • (esCiclico n) se verifica si n es un número cíclico. Por ejemplo,
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,
λ> 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

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