Menu Close

Paridad del número de divisores

José A. Alonso,

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)$
Medio
, , , , , , , , , ,

7 soluciones de “Paridad del número de divisores”

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