Pares con múltiplos con igual número de divisores
Definir la función
paresNoDivisible :: [(Integer, Integer)]
tal que paresNoDivisible es la lista de los pares (n,k) tales que n < k y k no es divisible por n. Por ejemplo,
λ> take 10 paresNoDivisible [(2,3),(3,4),(2,5),(3,5),(4,5),(4,6),(5,6),(2,7),(3,7),(4,7)]
Se observa que en el resultado los pares se ordenan primero según su segundo elemento y los que tienen el mismo segundo elemento se ordenan por el primer elemento.
Un par especial es un par de enteros positivos (n,k) tales que existe algún s tal que \(s \times n\) y \(s \times k\) tienen el mismo número de divisores. Por ejemplo, (3,4) es un par especial ya que \(2 \times 3\) y \(2 \times 4\) tienen 4 divisores.
Comprobar con QuickCheck todos los elementos de paresNoDivisible son pares especiales.
Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2018.
Soluciones
import Data.List (genericLength, group) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck (Property, (==>), quickCheck) -- Definición de paresNoDivisible -- ============================== paresNoDivisible :: [(Integer, Integer)] paresNoDivisible = filter parNoDivisible pares -- pares es la lista de los pares de enteros positivos ordenados primero -- según su segundo elemento y los que tienen el mismo segundo elemento -- están ordenados por el primer elemento. Por ejemplo, -- λ> take 10 pares -- [(1,2),(1,3),(2,3),(1,4),(2,4),(3,4),(1,5),(2,5),(3,5),(4,5)] pares :: [(Integer, Integer)] pares = [(n,k) | k <- [1..] , n <- [1..k-1]] -- (parNoDivisible (n,k)) se verifica si n < k y k no es divisible por -- n. Por ejemplo, -- parNoDivisible (2,3) == True -- parNoDivisible (2,4) == False -- parNoDivisible (3,2) == False parNoDivisible :: (Integer, Integer) -> Bool parNoDivisible (n,k) = n < k && k `mod` n /= 0 -- Definiciones de parEspecial -- =========================== -- Para expresar la propiedad se define la función -- parEspecial :: (Integer, Integer) -> Bool -- tal que (parEspecial (n,k)) se verifica si existe algún s tal que s*n -- y s*k tienen el mismo número de divisores. Por ejemplo, {-# SCC "" #-} -- parEspecial (3,4) == True -- -- Nota: La función parEspecial es una función parcial ya que sólo -- termina para los pares especiales. -- 1ª definición de parEspecial -- ============================ parEspecial1 :: (Integer, Integer) -> Bool parEspecial1 (n,k) = n < k && not (null [s | s <- [1..] , numeroDivisores (s * n) == numeroDivisores (s * k)]) -- (numeroDivisores n) es el número de divisores de n. Por ejemplo, -- numeroDivisores 12 == 6 -- numeroDivisores 14 == 4 numeroDivisores :: Integer -> Integer numeroDivisores n = genericLength [x | x <- [1..n] , n `mod` x == 0] -- 2ª definición de parEspecial -- ============================ parEspecial2 :: (Integer, Integer) -> Bool parEspecial2 (n,k) = n < k && not (null [s | s <- [1..] , numeroDivisores2 (s * n) == numeroDivisores2 (s * k)]) -- (numeroDivisores2 n) es el número de divisores de n. Por ejemplo, -- numeroDivisores2 12 == 6 -- numeroDivisores2 14 == 4 numeroDivisores2 :: Integer -> Integer numeroDivisores2 = product . map ((+1) . genericLength) . group . primeFactors -- Comparación de eficiencia de definiciones de parEspecial -- -------------------------------------------------------- -- La comparación es -- λ> parEspecial1 (9,30) -- True -- (28.24 secs, 15,625,373,696 bytes) -- λ> parEspecial2 (9,30) -- True -- (0.06 secs, 58,698,264 bytes) -- En lo que sigue, usaremos la 2ª definición parEspecial :: (Integer, Integer) -> Bool parEspecial = parEspecial2 -- Propiedad -- ========= -- La propiedad es prop_paresNoDivisible :: Int -> Property prop_paresNoDivisible i = i >= 0 ==> parEspecial (paresNoDivisible !! i) -- La comprobación es -- λ> quickCheck prop_paresNoDivisible -- +++ OK, passed 100 tests.