octubre 2022 – Página 4

Suma de múltiplos de 3 ó 5

PorJosé A. Alonso 10-octubre-202214-diciembre-2022

Definir la función

   euler1 :: Integer -> Integer

1	euler1 :: Integer -> Integer

tal que euler1 n es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,

   euler1 10      == 23
   euler1 (10^2)  == 2318
   euler1 (10^3)  == 233168
   euler1 (10^4)  == 23331668
   euler1 (10^5)  == 2333316668
   euler1 (10^10) == 23333333331666666668
   euler1 (10^20) == 2333333333333333333316666666666666666668
   euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668

euler1 10 == 23

euler1 (10^2) == 2318

euler1 (10^3) == 233168

euler1 (10^4) == 23331668

euler1 (10^5) == 2333316668

euler1 (10^10) == 23333333331666666668

euler1 (10^20) == 2333333333333333333316666666666666666668

euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668

Nota: Este ejercicio está basado en el problema 1 del Proyecto Euler

Soluciones

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

Soluciones en Haskell

import Data.List (nub, union)
import qualified Data.Set as S (fromAscList, union)
import Test.QuickCheck

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

euler1a :: Integer -> Integer
euler1a n =
  sum [x | x <- [1..n-1],
           multiplo x 3 || multiplo x 5]

-- (multiplo x y) se verifica si x es un múltiplo de y. Por ejemplo.
--    multiplo 12 3  ==  True
--    multiplo 14 3  ==  False
multiplo :: Integer -> Integer -> Bool
multiplo x y = mod x y == 0

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

euler1b :: Integer -> Integer
euler1b n =
  sum [x | x <- [1..n-1],
           gcd x 15 > 1]

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

euler1c :: Integer -> Integer
euler1c n =
  sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1]

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

euler1d :: Integer -> Integer
euler1d n =
  sum (nub ([3,6..n-1] ++ [5,10..n-1]))

-- 5ª solución                                                        --
-- ===========

euler1e :: Integer -> Integer
euler1e n =
  sum ([3,6..n-1] `union` [5,10..n-1])

-- 6ª solución                                                        --
-- ===========

euler1f :: Integer -> Integer
euler1f n =
  sum (S.fromAscList [3,6..n-1] `S.union` S.fromAscList [5,10..n-1])

-- 7ª solución                                                      --
-- ===========

euler1g :: Integer -> Integer
euler1g n =
  suma 3 n + suma 5 n - suma 15 n

-- (suma d x) es la suma de los múltiplos de d menores que x. Por
-- ejemplo,
--    suma 3 20  ==  63
suma :: Integer -> Integer -> Integer
suma d x = (a+b)*n `div` 2
    where a = d
          b = d * ((x-1) `div` d)
          n = 1 + (b-a) `div` d

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

-- La propiedad es
prop_euler1 :: Positive Integer -> Bool
prop_euler1 (Positive n) =
  all (== euler1a n)
      [euler1b n,
       euler1c n,
       euler1d n,
       euler1e n,
       euler1f n,
       euler1g n]

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

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

-- La comparación es
--    λ> euler1a (5*10^4)
--    583291668
--    (0.05 secs, 21,895,296 bytes)
--    λ> euler1b (5*10^4)
--    583291668
--    (0.05 secs, 26,055,096 bytes)
--    λ> euler1c (5*10^4)
--    583291668
--    (0.01 secs, 5,586,072 bytes)
--    λ> euler1d (5*10^4)
--    583291668
--    (2.83 secs, 7,922,304 bytes)
--    λ> euler1e (5*10^4)
--    583291668
--    (4.56 secs, 12,787,705,248 bytes)
--    λ> euler1f (5*10^4)
--    583291668
--    (0.01 secs, 8,168,584 bytes)
--    λ> euler1g (5*10^4)
--    583291668
--    (0.02 secs, 557,488 bytes)
--
--    λ> euler1a (3*10^6)
--    2099998500000
--    (2.72 secs, 1,282,255,816 bytes)
--    λ> euler1b (3*10^6)
--    2099998500000
--    (2.06 secs, 1,531,855,776 bytes)
--    λ> euler1c (3*10^6)
--    2099998500000
--    (0.38 secs, 305,127,480 bytes)
--    λ> euler1f (3*10^6)
--    2099998500000
--    (0.54 secs, 457,358,232 bytes)
--    λ> euler1g (3*10^6)
--    2099998500000
--    (0.01 secs, 560,472 bytes)
--
--    λ> euler1c (10^7)
--    23333331666668
--    (1.20 secs, 1,015,920,024 bytes)
--    λ> euler1f (10^7)
--    23333331666668
--    (2.00 secs, 1,523,225,648 bytes)
--    λ> euler1g (10^7)
--    23333331666668
--    (0.01 secs, 561,200 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

import Data.List (nub, union)

import qualified Data.Set as S (fromAscList, union)

import Test.QuickCheck

-- 1ª solución

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

euler1a :: Integer -> Integer

euler1a n =

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

multiplo x 3 || multiplo x 5]

-- (multiplo x y) se verifica si x es un múltiplo de y. Por ejemplo.

-- multiplo 12 3 == True

-- multiplo 14 3 == False

multiplo :: Integer -> Integer -> Bool

multiplo x y = mod x y == 0

-- 2ª solución --

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

euler1b :: Integer -> Integer

euler1b n =

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

gcd x 15 > 1]

-- 3ª solución --

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

euler1c :: Integer -> Integer

euler1c n =

sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1]

-- 4ª solución --

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

euler1d :: Integer -> Integer

euler1d n =

sum (nub ([3,6..n-1] ++ [5,10..n-1]))

-- 5ª solución --

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

euler1e :: Integer -> Integer

euler1e n =

sum ([3,6..n-1] `union` [5,10..n-1])

-- 6ª solución --

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

euler1f :: Integer -> Integer

euler1f n =

sum (S.fromAscList [3,6..n-1] `S.union` S.fromAscList [5,10..n-1])

-- 7ª solución --

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

euler1g :: Integer -> Integer

euler1g n =

suma 3 n + suma 5 n - suma 15 n

-- (suma d x) es la suma de los múltiplos de d menores que x. Por

-- ejemplo,

-- suma 3 20 == 63

suma :: Integer -> Integer -> Integer

suma d x = (a+b)*n `div` 2

where a = d

b = d * ((x-1) `div` d)

n = 1 + (b-a) `div` d

-- Comprobación de equivalencia

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

-- La propiedad es

prop_euler1 :: Positive Integer -> Bool

prop_euler1 (Positive n) =

all (== euler1a n)

[euler1b n,

euler1c n,

euler1d n,

euler1e n,

euler1f n,

euler1g n]

-- La comprobación es

-- λ> quickCheck prop_euler1

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> euler1a (5*10^4)

-- 583291668

-- (0.05 secs, 21,895,296 bytes)

-- λ> euler1b (5*10^4)

-- 583291668

-- (0.05 secs, 26,055,096 bytes)

-- λ> euler1c (5*10^4)

-- 583291668

-- (0.01 secs, 5,586,072 bytes)

-- λ> euler1d (5*10^4)

-- 583291668

-- (2.83 secs, 7,922,304 bytes)

-- λ> euler1e (5*10^4)

-- 583291668

-- (4.56 secs, 12,787,705,248 bytes)

-- λ> euler1f (5*10^4)

-- 583291668

-- (0.01 secs, 8,168,584 bytes)

-- λ> euler1g (5*10^4)

-- 583291668

-- (0.02 secs, 557,488 bytes)

-- λ> euler1a (3*10^6)

-- 2099998500000

-- (2.72 secs, 1,282,255,816 bytes)

-- λ> euler1b (3*10^6)

-- 2099998500000

-- (2.06 secs, 1,531,855,776 bytes)

-- λ> euler1c (3*10^6)

-- 2099998500000

-- (0.38 secs, 305,127,480 bytes)

-- λ> euler1f (3*10^6)

-- 2099998500000

-- (0.54 secs, 457,358,232 bytes)

-- λ> euler1g (3*10^6)

-- 2099998500000

-- (0.01 secs, 560,472 bytes)

-- λ> euler1c (10^7)

-- 23333331666668

-- (1.20 secs, 1,015,920,024 bytes)

-- λ> euler1f (10^7)

-- 23333331666668

-- (2.00 secs, 1,523,225,648 bytes)

-- λ> euler1g (10^7)

-- 23333331666668

-- (0.01 secs, 561,200 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import gcd
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

# multiplo(x, y) se verifica si x es un múltiplo de y. Por ejemplo.
#    multiplo(12, 3)  ==  True
#    multiplo(14, 3)  ==  False
def multiplo(x: int, y: int) -> int:
    return x % y == 0

def euler1a(n: int) -> int:
    return sum(x for x in range(1, n)
               if (multiplo(x, 3) or multiplo(x, 5)))

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

def euler1b(n: int) -> int:
    return sum(x for x in range(1, n)
               if gcd(x, 15) > 1)

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

def euler1c(n: int) -> int:
    return sum(range(3, n, 3)) + \
           sum(range(5, n, 5)) - \
           sum(range(15, n, 15))

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

def euler1d(n: int) -> int:
    return sum(set(list(range(3, n, 3)) + list(range(5, n, 5))))

# 5ª solución                                                        --
# ===========

def euler1e(n: int) -> int:
    return sum(set(list(range(3, n, 3))) | set(list(range(5, n, 5))))

# 6ª solución                                                        --
# ===========

# suma(d, x) es la suma de los múltiplos de d menores que x. Por
# ejemplo,
#    suma(3, 20)  ==  63
def suma(d: int, x: int) -> int:
    a = d
    b = d * ((x - 1) // d)
    n = 1 + (b - a) // d
    return (a + b) * n // 2

def euler1f(n: int) -> int:
    return suma(3, n) + suma(5, n) - suma(15, n)

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_euler1(n: int) -> None:
    r = euler1a(n)
    assert euler1b(n) == r
    assert euler1c(n) == r
    assert euler1d(n) == r
    assert euler1e(n) == r

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

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

def tiempo(e: str) -> None:
    """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('euler1a(10**7)')
#    1.49 segundos
#    >>> tiempo('euler1b(10**7)')
#    0.93 segundos
#    >>> tiempo('euler1c(10**7)')
#    0.07 segundos
#    >>> tiempo('euler1d(10**7)')
#    0.42 segundos
#    >>> tiempo('euler1e(10**7)')
#    0.69 segundos
#    >>> tiempo('euler1f(10**7)')
#    0.00 segundos
#
#    >>> tiempo('euler1c(10**8)')
#    0.72 segundos
#    >>> tiempo('euler1f(10**8)')
#    0.00 segundos

100

101

102

103

from math import gcd

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución

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

# multiplo(x, y) se verifica si x es un múltiplo de y. Por ejemplo.

# multiplo(12, 3) == True

# multiplo(14, 3) == False

def multiplo(x: int, y: int) -> int:

return x % y == 0

def euler1a(n: int) -> int:

return sum(x for x in range(1, n)

if (multiplo(x, 3) or multiplo(x, 5)))

# 2ª solución --

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

def euler1b(n: int) -> int:

return sum(x for x in range(1, n)

if gcd(x, 15) > 1)

# 3ª solución --

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

def euler1c(n: int) -> int:

return sum(range(3, n, 3)) + \

sum(range(5, n, 5)) - \

sum(range(15, n, 15))

# 4ª solución --

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

def euler1d(n: int) -> int:

return sum(set(list(range(3, n, 3)) + list(range(5, n, 5))))

# 5ª solución --

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

def euler1e(n: int) -> int:

return sum(set(list(range(3, n, 3))) | set(list(range(5, n, 5))))

# 6ª solución --

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

# suma(d, x) es la suma de los múltiplos de d menores que x. Por

# ejemplo,

# suma(3, 20) == 63

def suma(d: int, x: int) -> int:

a = d

b = d * ((x - 1) // d)

n = 1 + (b - a) // d

return (a + b) * n // 2

def euler1f(n: int) -> int:

return suma(3, n) + suma(5, n) - suma(15, n)

# Comprobación de equivalencia

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

# La propiedad es

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

def test_euler1(n: int) -> None:

r = euler1a(n)

assert euler1b(n) == r

assert euler1c(n) == r

assert euler1d(n) == r

assert euler1e(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_multiplos_de_3_o_5.py

# 1 passed in 0.16s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""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('euler1a(10**7)')

# 1.49 segundos

# >>> tiempo('euler1b(10**7)')

# 0.93 segundos

# >>> tiempo('euler1c(10**7)')

# 0.07 segundos

# >>> tiempo('euler1d(10**7)')

# 0.42 segundos

# >>> tiempo('euler1e(10**7)')

# 0.69 segundos

# >>> tiempo('euler1f(10**7)')

# 0.00 segundos

# >>> tiempo('euler1c(10**8)')

# 0.72 segundos

# >>> tiempo('euler1f(10**8)')

# 0.00 segundos

El código se encuentra en GitHub.

Números abundantes impares

PorJosé A. Alonso 7-octubre-202214-diciembre-2022

Definir la lista

  abundantesImpares :: [Integer]

1	abundantesImpares :: [Integer]

cuyos elementos son los números abundantes impares. Por ejemplo,

   λ> take 12 abundantesImpares
   [945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615]

1 2	λ> take 12 abundantesImpares [945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615]

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
-- ===========

abundantesImpares1 :: [Integer]
abundantesImpares1 = [x | x <- [1,3..], numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por
-- ejemplo,
--    numeroAbundante 5  == False
--    numeroAbundante 12 == True
--    numeroAbundante 28 == False
--    numeroAbundante 30 == True
numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 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
-- ===========

abundantesImpares2 :: [Integer]
abundantesImpares2 = filter numeroAbundante1 [1,3..]

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

-- Sustituyendo la definición de numeroAbundante1 de las soluciones
-- anteriores por cada una de las del ejercicio "Números abundantes"
-- https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes
-- impares. La usada en las definiciones anteriores es la menos
-- eficiente y la que se usa en la siguiente definición es la más eficiente.

abundantesImpares3 :: [Integer]
abundantesImpares3 = filter numeroAbundante3 [1,3..]

numeroAbundante3 :: Integer -> Bool
numeroAbundante3 x =
  x < sumaDivisores3 x - x

sumaDivisores3 :: Integer -> Integer
sumaDivisores3 = sigma 1

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

-- La propiedad es
prop_abundantesImpares :: Positive Int -> Bool
prop_abundantesImpares (Positive n) =
  all (== take n abundantesImpares1)
      [take n abundantesImpares2,
       take n abundantesImpares3]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_abundantesImpares
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> abundantesImpares1 !! 5
--    4095
--    (2.07 secs, 841,525,368 bytes)
--    λ> abundantesImpares2 !! 5
--    4095
--    (2.06 secs, 841,443,112 bytes)
--    λ> abundantesImpares3 !! 5
--    4095
--    (0.01 secs, 550,776 bytes)

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

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

abundantesImpares1 :: [Integer]

abundantesImpares1 = [x | x <- [1,3..], numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por

-- ejemplo,

-- numeroAbundante 5 == False

-- numeroAbundante 12 == True

-- numeroAbundante 28 == False

-- numeroAbundante 30 == True

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 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

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

abundantesImpares2 :: [Integer]

abundantesImpares2 = filter numeroAbundante1 [1,3..]

-- 3ª solución

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

-- Sustituyendo la definición de numeroAbundante1 de las soluciones

-- anteriores por cada una de las del ejercicio "Números abundantes"

-- https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes

-- impares. La usada en las definiciones anteriores es la menos

-- eficiente y la que se usa en la siguiente definición es la más eficiente.

abundantesImpares3 :: [Integer]

abundantesImpares3 = filter numeroAbundante3 [1,3..]

numeroAbundante3 :: Integer -> Bool

numeroAbundante3 x =

x < sumaDivisores3 x - x

sumaDivisores3 :: Integer -> Integer

sumaDivisores3 = sigma 1

-- Comprobación de equivalencia

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

-- La propiedad es

prop_abundantesImpares :: Positive Int -> Bool

prop_abundantesImpares (Positive n) =

all (== take n abundantesImpares1)

[take n abundantesImpares2,

take n abundantesImpares3]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_abundantesImpares

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> abundantesImpares1 !! 5

-- 4095

-- (2.07 secs, 841,525,368 bytes)

-- λ> abundantesImpares2 !! 5

-- 4095

-- (2.06 secs, 841,443,112 bytes)

-- λ> abundantesImpares3 !! 5

-- 4095

-- (0.01 secs, 550,776 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
# ===========

def abundantesImpares1(n: int) -> list[int]:
    return [x for x in range(1, n, 2) if numeroAbundante1(x)]

# 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))

# numeroAbundante(n) se verifica si n es un número abundante. Por
# ejemplo,
#    numeroAbundante(5)  == False
#    numeroAbundante(12) == True
#    numeroAbundante(28) == False
#    numeroAbundante(30) == True
def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - x

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

def abundantesImpares2(n: int) -> list[int]:
    return list(filter(numeroAbundante1, range(1, n, 2)))

# 3ª solución
# ===========
#
# Sustituyendo la definición de numeroAbundante1 de las soluciones
# anteriores por cada una de las del ejercicio "Números abundantes"
# https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes
# impares. La usada en las definiciones anteriores es la menos
# eficiente y la que se usa en la siguiente definición es la más eficiente.

def abundantesImpares3(n: int) -> list[int]:
    return list(filter(numeroAbundante3, range(1, n, 2)))

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

def numeroAbundante3(x: int) -> bool:
    return x < sumaDivisores3(x) - x

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_abundantesImpares(n: int) -> None:
    r = abundantesImpares1(n)
    assert abundantesImpares2(n) == r
    assert abundantesImpares3(n) == r

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

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

def tiempo(e: str) -> None:
    """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('abundantesImpares1(10000)[5]')
#    1.25 segundos
#    >>> tiempo('abundantesImpares2(10000)[5]')
#    1.22 segundos
#    >>> tiempo('abundantesImpares3(10000)[5]')
#    0.33 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

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

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

return [x for x in range(1, n, 2) if numeroAbundante1(x)]

# 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))

# numeroAbundante(n) se verifica si n es un número abundante. Por

# ejemplo,

# numeroAbundante(5) == False

# numeroAbundante(12) == True

# numeroAbundante(28) == False

# numeroAbundante(30) == True

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - x

# 2ª solución

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

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

return list(filter(numeroAbundante1, range(1, n, 2)))

# 3ª solución

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

# Sustituyendo la definición de numeroAbundante1 de las soluciones

# anteriores por cada una de las del ejercicio "Números abundantes"

# https://bit.ly/3xSlWDU se obtiene una nueva definición de abundantes

# impares. La usada en las definiciones anteriores es la menos

# eficiente y la que se usa en la siguiente definición es la más eficiente.

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

return list(filter(numeroAbundante3, range(1, n, 2)))

def sumaDivisores3(n: int) -> int:

return divisor_sigma(n, 1)

def numeroAbundante3(x: int) -> bool:

return x < sumaDivisores3(x) - x

# Comprobación de equivalencia

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

# La propiedad es

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

def test_abundantesImpares(n: int) -> None:

r = abundantesImpares1(n)

assert abundantesImpares2(n) == r

assert abundantesImpares3(n) == r

# La comprobación es

# src> poetry run pytest -q numeros_abundantes_impares.py

# 1 passed in 1.42s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""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('abundantesImpares1(10000)[5]')

# 1.25 segundos

# >>> tiempo('abundantesImpares2(10000)[5]')

# 1.22 segundos

# >>> tiempo('abundantesImpares3(10000)[5]')

# 0.33 segundos

El código se encuentra en GitHub.

Todos los abundantes hasta n son pares

PorJosé A. Alonso 6-octubre-202225-septiembre-2022

Definir la función

   todosPares :: Integer -> Bool

1	todosPares :: Integer -> Bool

tal que todosPares n se verifica si todos los números abundantes menores o iguales que n son pares. Por ejemplo,

   todosPares 10    ==  True
   todosPares 100   ==  True
   todosPares 1000  ==  False

todosPares 10 == True

todosPares 100 == True

todosPares 1000 == False

Soluciones en Haskell

module Todos_los_abundantes_hasta_n_son_pares where

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

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

todosPares1 :: Integer -> Bool
todosPares1 n = and [even x | x <- numerosAbundantesMenores1 n]

-- (numerosAbundantesMenores n) es la lista de números abundantes
-- menores o iguales que n. Por ejemplo,
--    numerosAbundantesMenores 50  ==  [12,18,20,24,30,36,40,42,48]
--    numerosAbundantesMenores 48  ==  [12,18,20,24,30,36,40,42,48]
numerosAbundantesMenores1 :: Integer -> [Integer]
numerosAbundantesMenores1 n =
  [x | x <- [1..n],
      numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por
-- ejemplo,
--    numeroAbundante 5  == False
--    numeroAbundante 12 == True
--    numeroAbundante 28 == False
--    numeroAbundante 30 == True
numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 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 numerosAbundantesMenores de la solución
-- anterior por cada una de las del ejercicio anterior se obtiene una
-- nueva definición de todosPares. 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.

todosPares2 :: Integer -> Bool
todosPares2 n = and [even x | x <- numerosAbundantesMenores2 n]

numerosAbundantesMenores2 :: Integer -> [Integer]
numerosAbundantesMenores2 n =
  [x | x <- [1..n],
      numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool
numeroAbundante2 x =
  x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

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

todosPares3 :: Integer -> Bool
todosPares3 1 = True
todosPares3 n | numeroAbundante1 n = even n && todosPares3 (n-1)
              | otherwise          = todosPares3 (n-1)

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

todosPares4 :: Integer -> Bool
todosPares4 n = all even (numerosAbundantesMenores1 n)

-- 5ª solución
-- ===========

todosPares5 :: Integer -> Bool
todosPares5 = all even . numerosAbundantesMenores1

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

-- La propiedad es
prop_todosPares :: Positive Integer -> Bool
prop_todosPares (Positive n) =
  all (== todosPares1 n)
      [todosPares2 n,
       todosPares3 n,
       todosPares4 n,
       todosPares5 n]

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

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

-- La comparación es
--    λ> todosPares1 (10^3)
--    False
--    (0.22 secs, 91,257,744 bytes)
--    λ> todosPares2 (10^3)
--    False
--    (0.01 secs, 2,535,656 bytes)
--    λ> todosPares3 (10^3)
--    False
--    (0.03 secs, 11,530,528 bytes)
--    λ> todosPares4 (10^3)
--    False
--    (0.24 secs, 91,231,144 bytes)
--    λ> todosPares5 (10^3)
--    False
--    (0.22 secs, 91,231,208 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

module Todos_los_abundantes_hasta_n_son_pares where

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

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

todosPares1 :: Integer -> Bool

todosPares1 n = and [even x | x <- numerosAbundantesMenores1 n]

-- (numerosAbundantesMenores n) es la lista de números abundantes

-- menores o iguales que n. Por ejemplo,

-- numerosAbundantesMenores 50 == [12,18,20,24,30,36,40,42,48]

-- numerosAbundantesMenores 48 == [12,18,20,24,30,36,40,42,48]

numerosAbundantesMenores1 :: Integer -> [Integer]

numerosAbundantesMenores1 n =

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

numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por

-- ejemplo,

-- numeroAbundante 5 == False

-- numeroAbundante 12 == True

-- numeroAbundante 28 == False

-- numeroAbundante 30 == True

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 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 numerosAbundantesMenores de la solución

-- anterior por cada una de las del ejercicio anterior se obtiene una

-- nueva definición de todosPares. 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.

todosPares2 :: Integer -> Bool

todosPares2 n = and [even x | x <- numerosAbundantesMenores2 n]

numerosAbundantesMenores2 :: Integer -> [Integer]

numerosAbundantesMenores2 n =

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

numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool

numeroAbundante2 x =

x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- 3ª solución

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

todosPares3 :: Integer -> Bool

todosPares3 1 = True

todosPares3 n | numeroAbundante1 n = even n && todosPares3 (n-1)

| otherwise = todosPares3 (n-1)

-- 4ª solución

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

todosPares4 :: Integer -> Bool

todosPares4 n = all even (numerosAbundantesMenores1 n)

-- 5ª solución

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

todosPares5 :: Integer -> Bool

todosPares5 = all even . numerosAbundantesMenores1

-- Comprobación de equivalencia

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

-- La propiedad es

prop_todosPares :: Positive Integer -> Bool

prop_todosPares (Positive n) =

all (== todosPares1 n)

[todosPares2 n,

todosPares3 n,

todosPares4 n,

todosPares5 n]

-- La comprobación es

-- λ> quickCheck prop_todosPares

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> todosPares1 (10^3)

-- False

-- (0.22 secs, 91,257,744 bytes)

-- λ> todosPares2 (10^3)

-- False

-- (0.01 secs, 2,535,656 bytes)

-- λ> todosPares3 (10^3)

-- False

-- (0.03 secs, 11,530,528 bytes)

-- λ> todosPares4 (10^3)

-- False

-- (0.24 secs, 91,231,144 bytes)

-- λ> todosPares5 (10^3)

-- False

-- (0.22 secs, 91,231,208 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))

# numeroAbundante(n) se verifica si n es un número abundante. Por
# ejemplo,
#    numeroAbundante(5)  == False
#    numeroAbundante(12) == True
#    numeroAbundante(28) == False
#    numeroAbundante(30) == True
def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - x

# numerosAbundantesMenores(n) es la lista de números abundantes menores
# o iguales que n. Por ejemplo,
#    numerosAbundantesMenores(50)  ==  [12,18,20,24,30,36,40,42,48]
#    numerosAbundantesMenores(48)  ==  [12,18,20,24,30,36,40,42,48]
def numerosAbundantesMenores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if numeroAbundante1(x)]

def todosPares1(n: int) -> bool:
    return False not in [x % 2 == 0 for x in numerosAbundantesMenores1(n)]

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

# Sustituyendo la definición de numerosAbundantesMenores de la solución
# anterior por cada una de las del ejercicio anterior se obtiene una
# nueva definición de todosPares. 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 numeroAbundante2(x: int) -> bool:
    return x < sumaDivisores2(x) - x

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

def todosPares2(n: int) -> bool:
    return False not in [x % 2 == 0 for x in numerosAbundantesMenores2(n)]

# 3ª solución
# ===========

def todosPares3(n: int) -> bool:
    return all(x % 2 == 0 for x in numerosAbundantesMenores1(n))

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_todosPares(n: int) -> None:
    assert todosPares1(n) == todosPares2(n) == todosPares3(n)

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

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

def tiempo(e: str) -> None:
    """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('todosPares1(1000)')
#    0.03 segundos
#    >>> tiempo('todosPares2(1000)')
#    0.05 segundos
#    >>> tiempo('todosPares3(1000)')
#    0.02 segundos
#
#    >>> tiempo('todosPares1(10000)')
#    2.07 segundos
#    >>> tiempo('todosPares2(10000)')
#    0.47 segundos
#    >>> tiempo('todosPares3(10000)')
#    2.42 segundos

100

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))

# numeroAbundante(n) se verifica si n es un número abundante. Por

# ejemplo,

# numeroAbundante(5) == False

# numeroAbundante(12) == True

# numeroAbundante(28) == False

# numeroAbundante(30) == True

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - x

# numerosAbundantesMenores(n) es la lista de números abundantes menores

# o iguales que n. Por ejemplo,

# numerosAbundantesMenores(50) == [12,18,20,24,30,36,40,42,48]

# numerosAbundantesMenores(48) == [12,18,20,24,30,36,40,42,48]

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

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

def todosPares1(n: int) -> bool:

return False not in [x % 2 == 0 for x in numerosAbundantesMenores1(n)]

# 2ª solución

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

# Sustituyendo la definición de numerosAbundantesMenores de la solución

# anterior por cada una de las del ejercicio anterior se obtiene una

# nueva definición de todosPares. 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 numeroAbundante2(x: int) -> bool:

return x < sumaDivisores2(x) - x

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

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

def todosPares2(n: int) -> bool:

return False not in [x % 2 == 0 for x in numerosAbundantesMenores2(n)]

# 3ª solución

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

def todosPares3(n: int) -> bool:

return all(x % 2 == 0 for x in numerosAbundantesMenores1(n))

# Comprobación de equivalencia

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

# La propiedad es

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

def test_todosPares(n: int) -> None:

assert todosPares1(n) == todosPares2(n) == todosPares3(n)

# La comprobación es

# src> poetry run pytest -q todos_los_abundantes_hasta_n_son_pares.py

# 1 passed in 2.63s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""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('todosPares1(1000)')

# 0.03 segundos

# >>> tiempo('todosPares2(1000)')

# 0.05 segundos

# >>> tiempo('todosPares3(1000)')

# 0.02 segundos

# >>> tiempo('todosPares1(10000)')

# 2.07 segundos

# >>> tiempo('todosPares2(10000)')

# 0.47 segundos

# >>> tiempo('todosPares3(10000)')

# 2.42 segundos

El código se encuentra en GitHub.

Números abundantes menores o iguales que n

PorJosé A. Alonso 5-octubre-202225-septiembre-2022

Un número natural n se denomina abundante si es menor que la suma de sus divisores propios. Por ejemplo, 12 es abundante ya que la suma de sus divisores propios es 16 (= 1 + 2 + 3 + 4 + 6), pero 5 y 28 no lo son.

Definir la función

   numerosAbundantesMenores :: Integer -> [Integer]

1	numerosAbundantesMenores :: Integer -> [Integer]

tal que numerosAbundantesMenores n es la lista de números abundantes menores o iguales que n. Por ejemplo,

   numerosAbundantesMenores 50  ==  [12,18,20,24,30,36,40,42,48]
   numerosAbundantesMenores 48  ==  [12,18,20,24,30,36,40,42,48]
   length (numerosAbundantesMenores (10^6)) ==  247545

numerosAbundantesMenores 50 == [12,18,20,24,30,36,40,42,48]

numerosAbundantesMenores 48 == [12,18,20,24,30,36,40,42,48]

length (numerosAbundantesMenores (10^6)) == 247545

Soluciones en Haskell

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

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

numerosAbundantesMenores1 :: Integer -> [Integer]
numerosAbundantesMenores1 n =
  [x | x <- [1..n],
      numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por
-- ejemplo,
--    numeroAbundante 5  == False
--    numeroAbundante 12 == True
--    numeroAbundante 28 == False
--    numeroAbundante 30 == True
numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 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 numeroAbundante de la solución anterior por
-- cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)
-- se obtiene una nueva definición de numerosAbundantesMenores. 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.

numerosAbundantesMenores2 :: Integer -> [Integer]
numerosAbundantesMenores2 n =
  [x | x <- [1..n],
      numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool
numeroAbundante2 x =
  x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

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

numerosAbundantesMenores3 :: Integer -> [Integer]
numerosAbundantesMenores3 n =
  filter numeroAbundante2 [1..n]

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

numerosAbundantesMenores4 :: Integer -> [Integer]
numerosAbundantesMenores4 =
  filter numeroAbundante2 . enumFromTo 1

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

-- La propiedad es
prop_numerosAbundantesMenores :: Positive Integer -> Bool
prop_numerosAbundantesMenores (Positive n) =
  all (== numerosAbundantesMenores1 n)
      [numerosAbundantesMenores2 n,
       numerosAbundantesMenores3 n,
       numerosAbundantesMenores4 n]

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

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

-- La comparación es
--    λ> length (numerosAbundantesMenores1 (5*10^3))
--    1239
--    (5.49 secs, 2,508,692,808 bytes)
--    λ> length (numerosAbundantesMenores2 (5*10^3))
--    1239
--    (0.01 secs, 11,501,944 bytes)

--    λ> length (numerosAbundantesMenores2 (10^6))
--    247545
--    (1.48 secs, 2,543,048,024 bytes)
--    λ> length (numerosAbundantesMenores3 (10^6))
--    247545
--    (1.30 secs, 2,499,087,272 bytes)
--    λ> length (numerosAbundantesMenores4 (10^6))
--    247545
--    (1.30 secs, 2,499,087,248 bytes)

100

101

102

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

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

numerosAbundantesMenores1 :: Integer -> [Integer]

numerosAbundantesMenores1 n =

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

numeroAbundante1 x]

-- (numeroAbundante n) se verifica si n es un número abundante. Por

-- ejemplo,

-- numeroAbundante 5 == False

-- numeroAbundante 12 == True

-- numeroAbundante 28 == False

-- numeroAbundante 30 == True

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 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 numeroAbundante de la solución anterior por

-- cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)

-- se obtiene una nueva definición de numerosAbundantesMenores. 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.

numerosAbundantesMenores2 :: Integer -> [Integer]

numerosAbundantesMenores2 n =

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

numeroAbundante2 x]

numeroAbundante2 :: Integer -> Bool

numeroAbundante2 x =

x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- 3ª solución

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

numerosAbundantesMenores3 :: Integer -> [Integer]

numerosAbundantesMenores3 n =

filter numeroAbundante2 [1..n]

-- 4ª solución

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

numerosAbundantesMenores4 :: Integer -> [Integer]

numerosAbundantesMenores4 =

filter numeroAbundante2 . enumFromTo 1

-- Comprobación de equivalencia

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

-- La propiedad es

prop_numerosAbundantesMenores :: Positive Integer -> Bool

prop_numerosAbundantesMenores (Positive n) =

all (== numerosAbundantesMenores1 n)

[numerosAbundantesMenores2 n,

numerosAbundantesMenores3 n,

numerosAbundantesMenores4 n]

-- La comprobación es

-- λ> quickCheck prop_numerosAbundantesMenores

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (numerosAbundantesMenores1 (5*10^3))

-- 1239

-- (5.49 secs, 2,508,692,808 bytes)

-- λ> length (numerosAbundantesMenores2 (5*10^3))

-- 1239

-- (0.01 secs, 11,501,944 bytes)

-- λ> length (numerosAbundantesMenores2 (10^6))

-- 247545

-- (1.48 secs, 2,543,048,024 bytes)

-- λ> length (numerosAbundantesMenores3 (10^6))

-- 247545

-- (1.30 secs, 2,499,087,272 bytes)

-- λ> length (numerosAbundantesMenores4 (10^6))

-- 247545

-- (1.30 secs, 2,499,087,248 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))

# numeroAbundante(n) se verifica si n es un número abundante. Por
# ejemplo,
#    numeroAbundante(5)  == False
#    numeroAbundante(12) == True
#    numeroAbundante(28) == False
#    numeroAbundante(30) == True
def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - x

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

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

# Sustituyendo la definición de numeroAbundante de la solución anterior por
# cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)
# se obtiene una nueva definición de numerosAbundantesMenores. 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 numeroAbundante2(x: int) -> bool:
    return x < sumaDivisores2(x) - x

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

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_numerosAbundantesMenores(n: int) -> None:
    assert numerosAbundantesMenores1(n) == numerosAbundantesMenores2(n)

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

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

def tiempo(e: str) -> None:
    """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('len(numerosAbundantesMenores1(10**4))')
#    2.21 segundos
#    >>> tiempo('len(numerosAbundantesMenores2(10**4))')
#    0.55 segundos
#
#    >>> tiempo('len(numerosAbundantesMenores2(10**5))')
#    5.96 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))

# numeroAbundante(n) se verifica si n es un número abundante. Por

# ejemplo,

# numeroAbundante(5) == False

# numeroAbundante(12) == True

# numeroAbundante(28) == False

# numeroAbundante(30) == True

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - x

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

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

# 2ª solución

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

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

# cada una de las del ejercicio [Números abundantes](https://bit.ly/3xSlWDU)

# se obtiene una nueva definición de numerosAbundantesMenores. 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 numeroAbundante2(x: int) -> bool:

return x < sumaDivisores2(x) - x

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

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

# Comprobación de equivalencia

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

# La propiedad es

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

def test_numerosAbundantesMenores(n: int) -> None:

assert numerosAbundantesMenores1(n) == numerosAbundantesMenores2(n)

# La comprobación es

# src> poetry run pytest -q numeros_abundantes_menores_o_iguales_que_n.py

# 1 passed in 1.54s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""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('len(numerosAbundantesMenores1(10**4))')

# 2.21 segundos

# >>> tiempo('len(numerosAbundantesMenores2(10**4))')

# 0.55 segundos

# >>> tiempo('len(numerosAbundantesMenores2(10**5))')

# 5.96 segundos

El código se encuentra en GitHub

Números abundantes

PorJosé A. Alonso 4-octubre-202214-diciembre-2022

Definir la función

   numeroAbundante :: Int -> Bool

1	numeroAbundante :: Int -> Bool

tal que numeroAbundante n se verifica si n es un número abundante. Por ejemplo,

   numeroAbundante 5  == False
   numeroAbundante 12 == True
   numeroAbundante 28 == False
   numeroAbundante 30 == True
   numeroAbundante 100000000  ==  True
   numeroAbundante 100000001  ==  False

numeroAbundante 5 == False

numeroAbundante 12 == True

numeroAbundante 28 == False

numeroAbundante 30 == True

numeroAbundante 100000000 == True

numeroAbundante 100000001 == False

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
-- ===========

numeroAbundante1 :: Integer -> Bool
numeroAbundante1 x =
  x < sumaDivisores1 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 de numeroAbundante. 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.

numeroAbundante2 :: Integer -> Bool
numeroAbundante2 x =
  x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sigma 1

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

-- La propiedad es
prop_numeroAbundante :: Positive Integer -> Bool
prop_numeroAbundante (Positive n) =
  numeroAbundante1 n == numeroAbundante2 n

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

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

-- La comparación es
--    λ> numeroAbundante1 (5*10^6)
--    True
--    (2.55 secs, 1,000,558,840 bytes)
--    λ> numeroAbundante2 (5*10^6)
--    True
--    (0.00 secs, 555,408 bytes)

import Math.NumberTheory.ArithmeticFunctions (sigma)

import Test.QuickCheck

-- 1ª solución

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

numeroAbundante1 :: Integer -> Bool

numeroAbundante1 x =

x < sumaDivisores1 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 de numeroAbundante. 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.

numeroAbundante2 :: Integer -> Bool

numeroAbundante2 x =

x < sumaDivisores2 x - x

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 = sigma 1

-- Comprobación de equivalencia

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

-- La propiedad es

prop_numeroAbundante :: Positive Integer -> Bool

prop_numeroAbundante (Positive n) =

numeroAbundante1 n == numeroAbundante2 n

-- La comprobación es

-- λ> quickCheck prop_numeroAbundante

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> numeroAbundante1 (5*10^6)

-- True

-- (2.55 secs, 1,000,558,840 bytes)

-- λ> numeroAbundante2 (5*10^6)

-- True

-- (0.00 secs, 555,408 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))

def numeroAbundante1(x: int) -> bool:
    return x < sumaDivisores1(x) - 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 de numeroAbundante. 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 numeroAbundante2(x: int) -> bool:
    return x < sumaDivisores2(x) - x

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_numeroAbundante(n):
    assert numeroAbundante1(n) == numeroAbundante2(n)

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

# 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('numeroAbundante1(4 * 10**7)')
#    2.02 segundos
#    >>> tiempo('numeroAbundante2(4 * 10**7)')
#    0.00 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))

def numeroAbundante1(x: int) -> bool:

return x < sumaDivisores1(x) - 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 de numeroAbundante. 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 numeroAbundante2(x: int) -> bool:

return x < sumaDivisores2(x) - x

# Comprobación de equivalencia

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

# La propiedad es

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

def test_numeroAbundante(n):

assert numeroAbundante1(n) == numeroAbundante2(n)

# La comprobación es

# src> poetry run pytest -q numeros_abundantes.py

# 1 passed in 0.38s

# 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('numeroAbundante1(4 * 10**7)')

# 2.02 segundos

# >>> tiempo('numeroAbundante2(4 * 10**7)')

# 0.00 segundos

El código se encuentra en GitHub.

Meses: octubre 2022

Suma de múltiplos de 3 ó 5

Números abundantes impares

Todos los abundantes hasta n son pares

Números abundantes menores o iguales que n

Números abundantes

Entradas recientes

Buscar

Correo electrónico