Menu Close

Números duffinianos

Los números duffinianos, llamados así por Richard Duffy, son los números compuestos n que son coprimos con la suma de sus divisores; es decir, n y la suma de los divisores de n no tienen ningún factor primo común.

Por ejemplo, 35 es un número duffiniano ya que la suma de sus divisores es 1 + 5 + 7 + 35 = 48 que es coprimo con 35.

Definir las funciones

   esDuffiniano :: Integer -> Bool
   duffinianos :: [Integer]

tales que

  • (esDuffiniano n) se verifica si n es duffiniano. Por ejemplo,
     esDuffiniano 35    ==  True
     esDuffiniano 2021  ==  True
     esDuffiniano 11    ==  False
     esDuffiniano 12    ==  False
     esDuffiniano (product [1..2*10^4])  ==  False
  • duffinianos es la sucesión de los números duffinianos. Por ejemplo,
     take 12 duffinianos  ==  [4,8,9,16,21,25,27,32,35,36,39,49]
     length (takeWhile (< 10^5) duffinianos)  ==  24434

Comprobar con QuickCheck que los números de la forma p^k, con p un primo mayor que 2 y k un entero mayor que 1, son duffinianos.

Soluciones

import Data.List (genericLength, group)
import Data.Numbers.Primes (isPrime, primeFactors, primes)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
duffinianos :: [Integer]
duffinianos = filter esDuffiniano [1..]
 
esDuffiniano :: Integer -> Bool
esDuffiniano n =
  n > 1 &&
  not (isPrime n) &&
  gcd n (sumaDivisores n) == 1
 
-- (sumaDivisores n) es la suma de los divisores de n. Por ejemplo.
--      sumaDivisores 35  ==  48
sumaDivisores :: Integer -> Integer
sumaDivisores = sum . divisores
 
-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--      divisores 35  ==  [1,5,7,35]
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..n]
                 , n `mod` x == 0]
 
-- 2ª solución
-- ===========
 
duffinianos2 :: [Integer]
duffinianos2 = filter esDuffiniano2 [1..]
 
esDuffiniano2 :: Integer -> Bool
esDuffiniano2 n =
  n > 1 &&
  not (isPrime n) &&
  gcd n (sumaDivisores2 n) == 1
 
-- Si la descomposición de x en factores primos es
--    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
-- entonces la suma de los divisores de x es
--    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1
--   ------------------- . ------------------- ... -------------------
--        p(1)-1                p(2)-1                  p(n)-1
-- Ver la demostración en http://bit.ly/2zUXZPc
 
-- (sumaDivisores2 n) es la suma de los divisores de n. Por ejemplo.
--      sumaDivisores2 35  ==  48
sumaDivisores2 :: Integer -> Integer
sumaDivisores2 x =
  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]
 
-- (factorizacion x) es la lista de las bases y exponentes de la
-- descomposición prima de x. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion = map primeroYlongitud . group . primeFactors
 
-- (primeroYlongitud xs) es el par formado por el primer elemento de xs
-- y la longitud de xs. Por ejemplo,
--    primeroYlongitud [3,2,5,7] == (3,4)
primeroYlongitud :: [a] -> (a,Integer)
primeroYlongitud (x:xs) = (x, 1 + genericLength xs)
primeroYlongitud _      = error "No tiene elementos"
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> esDuffiniano (product [1..11])
--    False
--    (14.09 secs, 7,983,535,608 bytes)
--    λ> esDuffiniano2 (product [1..11])
--    False
--    (0.01 secs, 125,760 bytes)
--
--    λ> head (dropWhile (<10^4) duffinianos)
--    10000
--    (13.45 secs, 8,872,967,976 bytes)
--    λ> head (dropWhile (<10^4) duffinianos2)
--    10000
--    (0.15 secs, 280,668,240 bytes)
--
--    λ> length (takeWhile (<10^4) duffinianos)
--    2370
--    (13.43 secs, 8,966,138,016 bytes)
--    λ> length (takeWhile (<10^4) duffinianos2)
--    2370
--    (0.15 secs, 286,120,048 bytes)
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_duffinianos :: Int -> Int -> Property
prop_duffinianos n k =
  n >= 0 && k > 1 ==> esDuffiniano2 (p^k)
  where p = primes !! n
 
-- La comprobación es
--    λ> quickCheck prop_duffinianos
--    +++ 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>

4 soluciones de “Números duffinianos

  1. Rubén Muñoz Mkrtchian
     
    import Data.Numbers.Primes
    import Data.List
     
    esDuffiniano :: Integer -> Bool
    esDuffiniano n
      | isPrime n = False
      | otherwise = gcd n (sum (divisores n)) == 1
      where divisores n = [x | x <- [1..n], n `rem` x == 0]
     
    duffinianos :: [Integer]
    duffinianos = filter esDuffiniano [4..]
  2. Inés Mora Caro
    import Test.QuickCheck
    import Data.List
    import Data.Char
    import Data.Numbers.Primes
     
     
    -- Un número (compuesto, nunca primo) es duffiniano si n y la suma de sus
    -- divisores son coprimos, es decir, no tienen ningún factor primo común.
    -- Esta definición es equivalente a decir que su máximo común divisor es 1.
     
    esDuffiniano :: Integer -> Bool
    esDuffiniano n | isPrime n = False 
                   | otherwise = gcd (sum (divisores n)) n == 1
     
    divisores n = [x | x <- xs, n `mod` x == 0]
          where xs = [1..n]
     
    duffinianos :: [Integer]
    duffinianos = filter esDuffiniano [4..]
    -- empezamos por 4 porque es el primer número compuesto y 1+2+4 es 7 que es
    -- primo y por ende coprimo con 4.
     
     
    -- Acabo de ver que la solución de mi compañero Rubén casi coincide, añado lo siguiente:
     
    -- Comprobar con QuickCheck que los números de la forma p^k, con p un primo
    -- mayor que 2 y k un entero mayor que 1, son duffinianos:
     
    prop :: Integer -> Bool
    prop n | isPrime n || n < 2 ||
                  (head (primeFactors n) /= last (primeFactors n)) = True
           | otherwise = esDuffiniano n
     
    -- λ> quickCheck prop
    -- +++ OK, passed 100 tests.
  3. Ángel Ruiz
    import Data.List           (inits,group)
    import Test.QuickCheck
    import Data.Numbers.Primes (primes,isPrime,primeFactors)
     
    -- (sumDivisores n) es la suma de los divisores de n. Por ejemplo,
    --     sumDivisores 35    ==  48
    --     sumDivisores 2021  ==  2112
     
    -- 1ª definición
    sumDivisores1 :: Integer -> Integer
    sumDivisores1 n = sum [x | x <- [1..n], n `mod` x == 0]
     
    -- 2ª definición
    sumDivisores2 :: Integer -> Integer
    sumDivisores2 n = n + sum [x | x <- [1..a], n `mod` x == 0]
      where a = n `div` 2
     
    -- 3ª definición
    sumDivisores3 :: Integer -> Integer
    sumDivisores3 =
      sum
      . map (product . concat)
      . prodCart
      . map (inits)
      . group
      . primeFactors
     
    -- (prodCart xss) es el producto cartesiano entre los elementos de xss.
    -- Por ejemplo,
    --    prodCart [[1],[2]]      ==  [[1,2]]
    --    prodCart [[1,2],[3,4]]  ==  [[1,3],[1,4],[2,3],[2,4]]
    prodCart :: [[a]] -> [[a]]
    prodCart = foldr f [[]]
       where f xs xss = [x:ys | x <- xs, ys <- xss]
     
    -- 4ª definición
    sumDivisores4 :: Integer -> Integer
    sumDivisores4 = product . map sumSerieGeoK . factorizacion
     
    -- (factorizacion n) es la lista de las bases y exponentes de la
    -- factorización prima de n. Por ejemplo,
    --    factorizacion 12  ==  [(2,2),(3,1)]
    --    factorizacion 35  ==  [(5,1),(7,1)]
    factorizacion :: Integer -> [(Integer,Int)]
    factorizacion = map (xs@(y:_) -> (y,length xs)) . group . primeFactors
     
    -- (sumSerieGeoK (p,k)) es la suma de los primeros (k+1) elementos de la
    -- serie geométrica de razón p. Por ejemplo,
    --    sumSerieGeoK (3,2)  ==  13
    --    sumSerieGeoK (2,4)  ==  31
    sumSerieGeoK :: (Integer,Int) -> Integer
    sumSerieGeoK (p,1) = p + 1
    sumSerieGeoK (p,k) = (p^(k+1) - 1) `div` (p - 1)
     
    -- Comparación de eficiencia
    -- =========================
     
    --    λ> length (takeWhile (< 10^3) (map sumDivisores1 [1..]))
    --    359
    --    (0.33 secs, 13,512,992 bytes)
    --    λ> length (takeWhile (< 10^3) (map sumDivisores2 [1..]))
    --    359
    --    (0.19 secs, 7,020,504 bytes)
    --    λ> length (takeWhile (< 10^3) (map sumDivisores3 [1..]))
    --    359
    --    (0.07 secs, 4,674,624 bytes)
    --    λ> length (takeWhile (< 10^3) (map sumDivisores4 [1..]))
    --    359
    --    (0.05 secs, 3,163,792 bytes)
    --
    --    λ> length (takeWhile (< 10^4) (map sumDivisores3 [1..]))
    --    3119
    --    (0.53 secs, 70,667,712 bytes)
    --    λ> length (takeWhile (< 10^4) (map sumDivisores4 [1..]))
    --    3119
    --    (0.36 secs, 51,518,880 bytes)
     
    -- Equivalencia de las soluciones
    -- ==============================
     
    -- La propiedad es
    prop_equiv :: Positive Integer -> Bool
    prop_equiv (Positive n) = (s1 == s2) && (s2 == s3) && (s3 == s4)
      where s1 = sumDivisores1 n
            s2 = sumDivisores2 n
            s3 = sumDivisores3 n
            s4 = sumDivisores4 n
     
    -- La comprobación es
    --    λ> quickCheck prop_equiv
    --    +++ OK, passed 100 tests.
     
    -- Definición
    -- ==========
     
    -- En lo que sigue usaremos la 4ª definición.
    sumDivisores :: Integer -> Integer
    sumDivisores = sumDivisores4
     
    -- 1ª definición
    esDuffiniano1 :: Integer -> Bool
    esDuffiniano1 1 = False
    esDuffiniano1 n
      | isPrime n   = False
      | otherwise   = gcd n (sumDivisores n) == 1
     
    -- 2ª definición (sin argumentos)
    esDuffiniano2 :: Integer -> Bool
    esDuffiniano2 =
      (<*>) ((&&) . (== 1) . ((<*>) gcd sumDivisores))
      ((<*>) ((&&) . (/= 1)) (not . isPrime))
     
    -- Definición
    -- ==========
     
    -- En lo que sigue usaremos la 1ª definición.
    esDuffiniano :: Integer -> Bool
    esDuffiniano = esDuffiniano1
     
    duffinianos :: [Integer]
    duffinianos = filter esDuffiniano [1..]
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_pk :: NonNegative Int -> Positive Integer -> Property
    prop_pk (NonNegative n) (Positive k) = k > 1 ==> esDuffiniano (p^k)
      where p = primes !! n
     
    -- La comprobación es
    --    λ> quickCheck prop_pk
    --    +++ OK, passed 100 tests.
  4. Alejandro García Alcaide
    import Data.Numbers.Primes
     
    -- LOS NÚMEROS DUFFINIANOS
    -- En primer lugar, definimos la función factores de un número. Por ejemplo:
    -- factores 10 = [1,2,5,10]
    factores :: Integer -> [Integer]
    factores n = [x | x <- [1..n], mod n x == 0]
     
    -- Ahora, definimos la función máximo común divisor.
    mcd :: Integer -> Integer -> [Integer]
    mcd m n = [x | x <- [1..m], elem x (factores n), elem x (factores m)]
     
    -- Por la definición de números duffinianos, tenemos que cualquier número primo
    -- nunca podrá ser de este tipo. Por tanto, la función esDuffiniano quedará
    -- definida de la siguiente forma:
    esDuffiniano :: Integer -> Bool
    esDuffiniano n | isPrime n = False
                   | otherwise =  mcd n (sum (factores n)) == [1]
     
    -- Así, la función duffinianos quedará así:
    duffiniano :: [Integer]
    duffiniano = [x | x <- [4..], esDuffiniano x]
     
     
    -- Dado que los números 1,2 y 3 son números primos (y, por la definición
    -- anterior, nunca serán duffinianos), podemos quitarlos del recorrido de la
    -- variable x, de la siguiente forma: x <- [4..], en vez de: x <- [1..]

Leave a Reply

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