PFH: La semana en Exercitium (7 de octubre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Números perfectos
- 2. Números abundantes
- 3. Números abundantes menores o iguales que n
- 4. Todos los abundantes hasta n son pares
- 5. Números abundantes impares
A continuación se muestran las soluciones.
1. 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
1 |
perfectos :: Integer -> [Integer] |
tal que perfectos n
es la lista de todos los números perfectos menores o iguales que n
. Por ejemplo,
1 2 |
perfectos 500 == [6,28,496] perfectos (10^5) == [6,28,496,8128] |
Soluciones en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
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.
2. Números abundantes
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
1 |
numeroAbundante :: Int -> Bool |
tal que numeroAbundante n
se verifica si n
es un número abundante. Por ejemplo,
1 2 3 4 5 6 |
numeroAbundante 5 == False numeroAbundante 12 == True numeroAbundante 28 == False numeroAbundante 30 == True numeroAbundante 100000000 == True numeroAbundante 100000001 == False |
Soluciones en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
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.
3. Números abundantes menores o iguales que n
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
1 |
numerosAbundantesMenores :: Integer -> [Integer] |
tal que numerosAbundantesMenores n
es la lista de números abundantes menores o iguales que n
. Por ejemplo,
1 2 3 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
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
4. Todos los abundantes hasta n son pares
Definir la función
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,
1 2 3 |
todosPares 10 == True todosPares 100 == True todosPares 1000 == False |
Soluciones en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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.
5. Números abundantes impares
Definir la lista
1 |
abundantesImpares :: [Integer] |
cuyos elementos son los números abundantes impares. Por ejemplo,
1 2 |
λ> take 12 abundantesImpares [945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615] |
Soluciones en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
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.