Números perfectos

Un números entero positivo es perfecto es igual a la suma de sus divisores, excluyendo el propio número. Por ejemplo, 6 es un número perfecto porque sus divisores propios son 1, 2 y 3; y 6 = 1 + 2 + 3.

Definir la función

   perfectos :: Integer -> [Integer]

1	perfectos :: Integer -> [Integer]

tal que perfectos n es la lista de todos los números perfectos menores o iguales que n. Por ejemplo,

   perfectos 500     ==  [6,28,496]
   perfectos (10^5)  ==  [6,28,496,8128]

1 2	perfectos 500 == [6,28,496] perfectos (10^5) == [6,28,496,8128]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Math.NumberTheory.ArithmeticFunctions (sigma)
import Test.QuickCheck

-- 1ª solución
-- ===========

perfectos1 :: Integer -> [Integer]
perfectos1 n =
  [x | x <- [1..n],
       esPerfecto1 x]

-- (esPerfecto x) se verifica si x es un número perfecto. Por ejemplo,
--    esPerfecto 6  ==  True
--    esPerfecto 8  ==  False
esPerfecto1 :: Integer -> Bool
esPerfecto1 x =
  sumaDivisores1 x - x == x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
--    sumaDivisores 12                 ==  28
--    sumaDivisores 25                 ==  31
sumaDivisores1 :: Integer -> Integer
sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,5,3,15,2,10,6,30,4,20,12,60]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución
-- ===========

-- Sustituyendo la definición de sumaDivisores de la solución anterior por
-- cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)
-- se obtiene una nueva definición deperfectos. La usada en la
-- definición anterior es la menos eficiente y la que se usa en la
-- siguiente definición es la más eficiente.

perfectos2 :: Integer -> [Integer]
perfectos2 n =
  [x | x <- [1..n],
       esPerfecto2 x]

esPerfecto2 :: Integer -> Bool
esPerfecto2 x =
  sumaDivisores2 x - x == x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

-- 3ª solución
-- ===========

perfectos3 :: Integer -> [Integer]
perfectos3 n = filter esPerfecto2 [1..n]

-- 4ª solución
-- ===========

perfectos4 :: Integer -> [Integer]
perfectos4 = filter esPerfecto2 . enumFromTo 1

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_perfectos :: Positive Integer -> Bool
prop_perfectos (Positive n) =
  all (== perfectos1 n)
      [perfectos2 n,
       perfectos3 n,
       perfectos4 n]

-- La comprobación es
--    λ> quickCheck prop_perfectos
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> perfectos1 (4*10^3)
--    [6,28,496]
--    (4.64 secs, 1,606,883,384 bytes)
--    λ> perfectos2 (4*10^3)
--    [6,28,496]
--    (0.02 secs, 9,167,208 bytes)
--
--    λ> perfectos2 (2*10^6)
--    [6,28,496,8128]
--    (3.32 secs, 5,120,880,728 bytes)
--    λ> perfectos3 (2*10^6)
--    [6,28,496,8128]
--    (2.97 secs, 5,040,880,632 bytes)
--    λ> perfectos4 (2*10^6)
--    [6,28,496,8128]
--    (2.80 secs, 5,040,880,608 bytes)

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

-- ===========

perfectos1 :: Integer -> [Integer]

perfectos1 n =

[x | x <- [1..n],

esPerfecto1 x]

-- (esPerfecto x) se verifica si x es un número perfecto. Por ejemplo,

-- esPerfecto 6 == True

-- esPerfecto 8 == False

esPerfecto1 :: Integer -> Bool

esPerfecto1 x =

sumaDivisores1 x - x == x

-- (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

-- sumaDivisores 12 == 28

-- sumaDivisores 25 == 31

sumaDivisores1 :: Integer -> Integer

sumaDivisores1 n = sum (divisores1 n)

-- (divisores x) es la lista de los divisores de x. Por ejemplo,

-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

-- Sustituyendo la definición de sumaDivisores de la solución anterior por

-- cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)

-- se obtiene una nueva definición deperfectos. La usada en la

-- definición anterior es la menos eficiente y la que se usa en la

-- siguiente definición es la más eficiente.

perfectos2 :: Integer -> [Integer]

perfectos2 n =

[x | x <- [1..n],

esPerfecto2 x]

esPerfecto2 :: Integer -> Bool

esPerfecto2 x =

sumaDivisores2 x - x == x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- 3ª solución

-- ===========

perfectos3 :: Integer -> [Integer]

perfectos3 n = filter esPerfecto2 [1..n]

-- 4ª solución

-- ===========

perfectos4 :: Integer -> [Integer]

perfectos4 = filter esPerfecto2 . enumFromTo 1

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_perfectos :: Positive Integer -> Bool

prop_perfectos (Positive n) =

all (== perfectos1 n)

[perfectos2 n,

perfectos3 n,

perfectos4 n]

-- La comprobación es

-- λ> quickCheck prop_perfectos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> perfectos1 (4*10^3)

-- [6,28,496]

-- (4.64 secs, 1,606,883,384 bytes)

-- λ> perfectos2 (4*10^3)

-- [6,28,496]

-- (0.02 secs, 9,167,208 bytes)

-- λ> perfectos2 (2*10^6)

-- [6,28,496,8128]

-- (3.32 secs, 5,120,880,728 bytes)

-- λ> perfectos3 (2*10^6)

-- [6,28,496,8128]

-- (2.97 secs, 5,040,880,632 bytes)

-- λ> perfectos4 (2*10^6)

-- [6,28,496,8128]

-- (2.80 secs, 5,040,880,608 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy import divisor_sigma

# 1ª solución
# ===========

# divisores(n) es la lista de los divisores del número n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,
#    sumaDivisores(12)                ==  28
#    sumaDivisores(25)                ==  31
def sumaDivisores1(n: int) -> int:
    return sum(divisores1(n))

# esPerfecto(x) se verifica si x es un número perfecto. Por ejemplo,
#    esPerfecto(6)  ==  True
#    esPerfecto(8)  ==  False
def esPerfecto1(x: int) -> bool:
    return sumaDivisores1(x) - x == x

def perfectos1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if esPerfecto1(x)]

# 2ª solución
# ===========

# Sustituyendo la definición de sumaDivisores de la solución anterior por
# cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)
# se obtiene una nueva definición deperfectos. La usada en la
# definición anterior es la menos eficiente y la que se usa en la
# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:
    return divisor_sigma(n, 1)

def esPerfecto2(x: int) -> bool:
    return sumaDivisores2(x) - x == x

def perfectos2(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if esPerfecto2(x)]

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_perfectos(n):
    assert perfectos1(n) == perfectos2(n)

# La comprobación es
#    src> poetry run pytest -q numeros_perfectos.py
#    1 passed in 1.43s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('perfectos1(10**4)')
#    2.97 segundos
#    >>> tiempo('perfectos2(10**4)')
#    0.57 segundos

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from sympy import divisor_sigma

# 1ª solución

# ===========

# divisores(n) es la lista de los divisores del número n. Por ejemplo,

# divisores(30) == [1,2,3,5,6,10,15,30]

def divisores1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if n % x == 0]

# sumaDivisores(x) es la suma de los divisores de x. Por ejemplo,

# sumaDivisores(12) == 28

# sumaDivisores(25) == 31

def sumaDivisores1(n: int) -> int:

return sum(divisores1(n))

# esPerfecto(x) se verifica si x es un número perfecto. Por ejemplo,

# esPerfecto(6) == True

# esPerfecto(8) == False

def esPerfecto1(x: int) -> bool:

return sumaDivisores1(x) - x == x

def perfectos1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if esPerfecto1(x)]

# 2ª solución

# ===========

# Sustituyendo la definición de sumaDivisores de la solución anterior por

# cada una de las del ejercicio [Suma de divisores](https://bit.ly/3S9aonQ)

# se obtiene una nueva definición deperfectos. La usada en la

# definición anterior es la menos eficiente y la que se usa en la

# siguiente definición es la más eficiente.

def sumaDivisores2(n: int) -> int:

return divisor_sigma(n, 1)

def esPerfecto2(x: int) -> bool:

return sumaDivisores2(x) - x == x

def perfectos2(n: int) -> list[int]:

return [x for x in range(1, n + 1) if esPerfecto2(x)]

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_perfectos(n):

assert perfectos1(n) == perfectos2(n)

# La comprobación es

# src> poetry run pytest -q numeros_perfectos.py

# 1 passed in 1.43s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('perfectos1(10**4)')

# 2.97 segundos

# >>> tiempo('perfectos2(10**4)')

# 0.57 segundos

El código se encuentra en GitHub.

Números perfectos

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico