Menu Close

Paridad del número de divisores

Definir la función

   nDivisoresPar :: Integer -> Bool

tal que (nDivisoresPar n) se verifica si n tiene un número par de divisores. Por ejemplo,

   nDivisoresPar 12                     ==  True
   nDivisoresPar 16                     ==  False
   nDivisoresPar (product [1..2*10^4])  ==  True

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primeFactors)
 
-- 1ª definición
-- =============
 
nDivisoresPar1 :: Integer -> Bool
nDivisoresPar1 = even . length . divisores
 
-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--    divisores 12  ==  [1,2,3,4,6,12]
--    divisores 16  ==  [1,2,4,8,16]
divisores :: Integer -> [Integer]
divisores n =
    [x | x <- [1..n], n `mod` x == 0]
 
-- 2ª definición
-- =============
 
nDivisoresPar2 :: Integer -> Bool
nDivisoresPar2 n =
    any odd (map length (group (primeFactors n)))
 
-- Comparación de eficiencia
-- =========================
 
--    λ> nDivisoresPar1 (10^7)
--    True
--    (14.18 secs, 2,078,736,992 bytes)
--    λ> nDivisoresPar2 (10^7)
--    True
--    (0.01 secs, 0 bytes)
--
--    λ> nDivisoresPar2 (product [1..2*10^4])
--    True
--    (2.30 secs, 1,003,013,112 bytes)

Solución en Maxima

/* concat(xs) es la lista obtenida concatenado los elementos de xss. Por
   ejemplo,
      concat([[1,3],[2,4],[5,7]])  ==  [1, 3, 2, 4, 5, 7]             */
concat (xs) := block ([r:[]],
  for x in reverse (xs) do r : append (x,r),
  r)$
 
nDivisoresPares (n) := block(
  [xs : concat (map (rest, ifactors (n))), p : false],
  for x in xs do p: oddp (x) or p,
  p)$

7 soluciones de “Paridad del número de divisores

  1. paocabper
    --Muy ineficiente.
    divisores n = [x | x <- [1..n], rem n x == 0]
    nDivisoresPar n = not (odd (length(divisores n)))
  2. erisan
    import Data.Numbers.Primes
    import Data.List
     
    nDivisoresPar :: Integer -> Bool
    nDivisoresPar x = any odd [length n | n <- group (primeFactors x)]
  3. abrdelrod

    Sabemos que si d es un divisor de n, n/d también lo será, luego los divisores pueden agruparse por pares cuyo producto es n. La única posibilidad, por tanto, de que n tenga un número impar de divisores es que exista un d divisor de n tal que d sea igual a n/d. Pero en ese caso se tiene n = d^2, de donde se deduce que n ha de ser cuadrado perfecto (nótese que a lo sumo puede haber uno, pues de lo contrario tendríamos que n es el cuadrado de dos números positivos distintos, lo cual es imposible).
    Sin embargo, buscar el número en la lista de cuadrados perfectos tampoco es mucho más eficiente. Pero si nos fijamos, un cuadrado perfecto se distingue del resto de números porque los exponentes de su factorización como producto de primos son todos pares. Luego si hay algún exponente impar en su factorización, automáticamente tendrá un número par de divisores. Por tanto:

    import Data.Numbers.Primes
    import Data.List
     
    nDivisoresPar :: Integer -> Bool
    nDivisoresPar = any odd . map length . group . primeFactors
  4. juamorrom1

    En esta definición se usa la siguiente propiedad: el número de divisores de un determinado número n se corresponde con la multiplicación de los exponentes de los factores primos de su factorización, sumando uno a todos estos exponentes. Por ejemplo:

    • Factorización de 100 = 2²5²
    • Cantidad de divisores de 100 = (2+1)*(2+1) = 9

    Efectivamente, los divisores de 100 son [1,2,4,5,10,20,25,50,100].

    nDivisoresPar :: Integer -> Bool
    nDivisoresPar n = even $ product $ exponentesFactorizacionMas1 n
     
    exponentesFactorizacionMas1 :: Integer -> [Integer]
    exponentesFactorizacionMas1 n = 
        [genericLength xs + 1 | xs <- group (factorizacion n)]
     
    factorizacion :: Integer -> [Integer]
    factorizacion n | n == 1    = []
                     | otherwise = x : factorizacion (div n x)
                     where x = menorFactor n
     
    menorFactor :: Integer -> Integer
    menorFactor n = head [x | x <- [2..], rem n x == 0]
  5. isrbelnun
    -- AVISO: No es eficiente
    nDivisoresPar :: Integer -> Bool
    nDivisoresPar n | even (nDivisores n) = True
                    | otherwise          = False
                      where nDivisores n = length [x | x <- [1..n], mod n x == 0]
  6. fracruzam

    Traducción en Maxima

    nDivisoresPares (n) := block(
      [xs:apply(append,map (rest,ifactors(n))),p:false],
      for x in xs do p: oddp(x) or p,
      p)
    • fracruzam

      Pequeña mejora en la eficiencia que hace la función en Maxima algo así como perezosa

      nDivisoresPares (n) := block(
        [xs:apply(append,map (rest,ifactors(n))),x,ys],
         x : first(xs),
        ys : rest(xs),
       unless oddp(x) or emptyp(ys) do (
          xs : ys,
          ys : rest(xs),
          x  : first(xs)),
        oddp(x))$

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.