Menu Close

Día: 4 febrero, 2021

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.

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>