Suma de los números amigos menores que n
Dos números amigos son dos números enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.
Definir la función
sumaAmigosMenores :: Integer -> Integer
tal que (sumaAmigosMenores n) es la suma de los números amigos menores que n. Por ejemplo,
sumaAmigosMenores 2000 == 2898 sumaAmigosMenores (10^5) == 852810
1. Soluciones en Haskell
import Data.List (genericLength, group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primeFactors) import Test.Hspec (Spec, describe, hspec, it, shouldBe) import Test.QuickCheck -- 1ª solución -- -- =========== sumaAmigosMenores1 :: Integer -> Integer sumaAmigosMenores1 n = sum [x+y | (x,y) <- amigosMenores1 n] -- (amigosMenores1 n) es la lista de los pares de números amigos (con la -- primera componente menor que la segunda) que son menores que n. Por -- ejemplo, -- amigosMenores1 2000 == [(220,284),(1184,1210)] amigosMenores1 :: Integer -> [(Integer,Integer)] amigosMenores1 n = takeWhile (\(_,y) -> y < n) sucesionAmigos1 sucesionAmigos1 :: [(Integer,Integer)] sucesionAmigos1 = [(x,y) | x <- [1..], let y = sumaDivisoresPropios1 x, y > x, sumaDivisoresPropios1 y == x] -- (sumaDivisoresPropios1 x) es la suma de los divisores propios de -- x. Por ejemplo, -- sumaDivisoresPropios1 220 == 284 -- sumaDivisoresPropios1 284 == 220 sumaDivisoresPropios1 :: Integer -> Integer sumaDivisoresPropios1 = sum . divisoresPropios1 -- (divisoresPropios1 x) es la lista de los divisores propios de x. Por -- ejemplo, -- divisoresPropios1 220 == [1,2,4,5,10,11,20,22,44,55,110] -- divisoresPropios1 284 == [1,2,4,71,142] divisoresPropios1 :: Integer -> [Integer] divisoresPropios1 x = [n | n <- [1..x-1], x `mod` n == 0] -- 2ª solución -- -- =========== sumaAmigosMenores2 :: Integer -> Integer sumaAmigosMenores2 n = sum [x+y | (x,y) <- amigosMenores2 n] amigosMenores2 :: Integer -> [(Integer,Integer)] amigosMenores2 n = takeWhile (\(_,y) -> y < n) sucesionAmigos2 sucesionAmigos2 :: [(Integer,Integer)] sucesionAmigos2 = [(x,y) | x <- [1..], let y = sumaDivisoresPropios2 x, y > x, sumaDivisoresPropios2 y == x] sumaDivisoresPropios2 :: Integer -> Integer sumaDivisoresPropios2 = sum . divisoresPropios2 divisoresPropios2 :: Integer -> [Integer] divisoresPropios2 x = filter ((== 0) . mod x) [1..x-1] -- 3ª solución -- -- =========== sumaAmigosMenores3 :: Integer -> Integer sumaAmigosMenores3 n = sum [x+y | (x,y) <- amigosMenores3 n] amigosMenores3 :: Integer -> [(Integer,Integer)] amigosMenores3 n = takeWhile (\(_,y) -> y < n) sucesionAmigos3 sucesionAmigos3 :: [(Integer,Integer)] sucesionAmigos3 = [(x,y) | x <- [1..], let y = sumaDivisoresPropios3 x, y > x, sumaDivisoresPropios3 y == x] sumaDivisoresPropios3 :: Integer -> Integer sumaDivisoresPropios3 = sum . divisoresPropios3 divisoresPropios3 :: Integer -> [Integer] divisoresPropios3 = init . nub . sort . map product . subsequences . primeFactors -- 4ª solución -- -- =========== sumaAmigosMenores4 :: Integer -> Integer sumaAmigosMenores4 n = sum [x+y | (x,y) <- amigosMenores4 n] amigosMenores4 :: Integer -> [(Integer,Integer)] amigosMenores4 n = takeWhile (\(_,y) -> y < n) sucesionAmigos4 sucesionAmigos4 :: [(Integer,Integer)] sucesionAmigos4 = [(x,y) | x <- [1..], let y = sumaDivisoresPropios4 x, y > x, sumaDivisoresPropios4 y == x] sumaDivisoresPropios4 :: Integer -> Integer sumaDivisoresPropios4 = sum . divisoresPropios4 divisoresPropios4 :: Integer -> [Integer] divisoresPropios4 = init . sort . map (product . concat) . productoCartesiano . map inits . group . primeFactors -- (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- λ> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss] -- 5ª solución -- -- =========== sumaAmigosMenores5 :: Integer -> Integer sumaAmigosMenores5 n = sum [x+y | (x,y) <- amigosMenores5 n] amigosMenores5 :: Integer -> [(Integer,Integer)] amigosMenores5 n = takeWhile (\(_,y) -> y < n) sucesionAmigos5 sucesionAmigos5 :: [(Integer,Integer)] sucesionAmigos5 = [(x,y) | x <- [1..], let y = sumaDivisoresPropios5 x, y > x, sumaDivisoresPropios5 y == x] sumaDivisoresPropios5 :: Integer -> Integer sumaDivisoresPropios5 = sum . divisoresPropios5 divisoresPropios5 :: Integer -> [Integer] divisoresPropios5 = init . sort . map (product . concat) . sequence . map inits . group . primeFactors -- 6ª solución -- -- =========== sumaAmigosMenores6 :: Integer -> Integer sumaAmigosMenores6 n = sum [x+y | (x,y) <- amigosMenores6 n] amigosMenores6 :: Integer -> [(Integer,Integer)] amigosMenores6 n = takeWhile (\(_,y) -> y < n) sucesionAmigos6 sucesionAmigos6 :: [(Integer,Integer)] sucesionAmigos6 = [(x,y) | x <- [1..], let y = sumaDivisoresPropios6 x, y > x, sumaDivisoresPropios6 y == x] sumaDivisoresPropios6 :: Integer -> Integer sumaDivisoresPropios6 = sum . init . map (product . concat) . mapM inits . group . primeFactors -- 7ª solución -- -- =========== sumaAmigosMenores7 :: Integer -> Integer sumaAmigosMenores7 n = sum [x+y | (x,y) <- amigosMenores7 n] amigosMenores7 :: Integer -> [(Integer,Integer)] amigosMenores7 n = takeWhile (\(_,y) -> y < n) sucesionAmigos7 sucesionAmigos7 :: [(Integer,Integer)] sucesionAmigos7 = [(x,y) | x <- [1..], let y = sumaDivisoresPropios7 x, y > x, sumaDivisoresPropios7 y == x] -- Si la descomposición de x en factores primos es -- x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n) -- entonces la suma de los divisores de x es -- p(1)^(e(1)+1) - 1 p(2)^(e(2)+1) - 1 p(n)^(e(2)+1) - 1 -- ------------------- . ------------------- ... ------------------- -- p(1)-1 p(2)-1 p(n)-1 -- Ver la demostración en http://bit.ly/2zUXZPc sumaDivisoresPropios7 :: Integer -> Integer sumaDivisoresPropios7 x = product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x] - x -- (factorizacion x) es la lista de las bases y exponentes de la -- descomposición prima de x. Por ejemplo, -- factorizacion 600 == [(2,3),(3,1),(5,2)] factorizacion :: Integer -> [(Integer,Integer)] factorizacion = map primeroYlongitud . group . primeFactors -- (primeroYlongitud xs) es el par formado por el primer elemento de xs -- y la longitud de xs. Por ejemplo, -- primeroYlongitud [3,2,5,7] == (3,4) primeroYlongitud :: [a] -> (a,Integer) primeroYlongitud (x:xs) = (x, 1 + genericLength xs) -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Integer -> Integer) -> Spec specG sumaAmigosMenores = do it "e1" $ sumaAmigosMenores 1000 `shouldBe` 504 spec :: Spec spec = do describe "def. 1" $ specG sumaAmigosMenores1 describe "def. 2" $ specG sumaAmigosMenores2 describe "def. 3" $ specG sumaAmigosMenores3 describe "def. 4" $ specG sumaAmigosMenores4 describe "def. 5" $ specG sumaAmigosMenores5 describe "def. 6" $ specG sumaAmigosMenores6 describe "def. 7" $ specG sumaAmigosMenores7 -- La verificación es -- λ> verifica -- 7 examples, 0 failures -- Equivalencia de definiciones -- ============================ -- La propiedad es prop_sumaAmigosMenores :: Positive Integer -> Bool prop_sumaAmigosMenores (Positive n) = all (== sumaAmigosMenores1 n) [sumaAmigosMenores2 n, sumaAmigosMenores3 n, sumaAmigosMenores4 n, sumaAmigosMenores5 n, sumaAmigosMenores6 n, sumaAmigosMenores7 n ] -- La comprobación es -- λ> quickCheck prop_sumaAmigosMenores -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sumaAmigosMenores1 6000 -- 19026 -- (10.37 secs, 5,261,392,352 bytes) -- λ> sumaAmigosMenores2 6000 -- 19026 -- (3.86 secs, 3,161,700,400 bytes) -- λ> sumaAmigosMenores3 6000 -- 19026 -- (0.15 secs, 308,520,248 bytes) -- λ> sumaAmigosMenores4 6000 -- 19026 -- (0.23 secs, 271,421,184 bytes) -- λ> sumaAmigosMenores5 6000 -- 19026 -- (0.13 secs, 230,042,112 bytes) -- λ> sumaAmigosMenores6 6000 -- 19026 -- (0.12 secs, 202,638,880 bytes) -- λ> sumaAmigosMenores7 6000 -- 19026 -- (0.13 secs, 159,022,448 bytes) -- -- λ> sumaAmigosMenores3 (10^5) -- 852810 -- (4.83 secs, 10,726,377,728 bytes) -- λ> sumaAmigosMenores4 (10^5) -- 852810 -- (4.79 secs, 7,832,234,120 bytes) -- λ> sumaAmigosMenores5 (10^5) -- 852810 -- (2.79 secs, 6,837,118,464 bytes) -- λ> sumaAmigosMenores6 (10^5) -- 852810 -- (2.39 secs, 6,229,730,472 bytes) -- λ> sumaAmigosMenores7 (10^5) -- 852810 -- (2.65 secs, 5,170,949,168 bytes)
2. Soluciones en Python
from functools import reduce from itertools import count, islice, takewhile from operator import mul from timeit import Timer, default_timer from typing import Iterator from hypothesis import given from hypothesis import strategies as st from sympy import divisor_sigma, factorint, proper_divisors # 1ª solución # =========== # divisoresPropios1(x) es la lista de los divisores propios de x. Por # ejemplo, # divisoresPropios1(220) == [1,2,4,5,10,11,20,22,44,55,110] # divisoresPropios1(284) == [1,2,4,71,142] def divisoresPropios1(x: int) -> list[int]: return [n for n in range(1, x) if x % n == 0] # sumaDivisoresPropios1(x) es la suma de los divisores propios de # x. Por ejemplo, # sumaDivisoresPropios1(220) == 284 # sumaDivisoresPropios1(284) == 220 def sumaDivisoresPropios1(x: int) -> int: return sum(divisoresPropios1(x)) # sucesionAmigos1() genera los pares de números amigos con la primera # componente menor que la segunda. Por ejemplo, # >>> list(islice(sucesionAmigos1(), 4)) # [(220, 284), (1184, 1210), (2620, 2924), (5020, 5564)] def sucesionAmigos1() -> Iterator[tuple[int, int]]: return ((x,y) for x in count(1) if (y := sumaDivisoresPropios1(x)) > x and sumaDivisoresPropios1(y) == x) # amigosMenores1(n) es la lista de los pares de números amigos (con la # primera componente menor que la segunda) que son menores que n. Por # ejemplo, # amigosMenores1(2000) == [(220,284),(1184,1210)] def amigosMenores1(n: int) -> list[tuple[int, int]]: return list(takewhile(lambda par: par[1] < n, sucesionAmigos1())) def sumaAmigosMenores1(n: int) -> int: return sum(x + y for x, y in amigosMenores1(n)) # 2ª solución # =========== def divisoresPropios2(x: int) -> list[int]: return proper_divisors(x) def sumaDivisoresPropios2(x: int) -> int: return sum(divisoresPropios2(x)) def sucesionAmigos2() -> Iterator[tuple[int, int]]: return ((x,y) for x in count(1) if (y := sumaDivisoresPropios2(x)) > x and sumaDivisoresPropios2(y) == x) def amigosMenores2(n: int) -> list[tuple[int, int]]: return list(takewhile(lambda par: par[1] < n, sucesionAmigos2())) def sumaAmigosMenores2(n: int) -> int: return sum(x + y for x, y in amigosMenores2(n)) # 3ª solución # =========== # Si la descomposición de x en factores primos es # x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n) # entonces la suma de los divisores de x es # p(1)^(e(1)+1) - 1 p(2)^(e(2)+1) - 1 p(n)^(e(2)+1) - 1 # ------------------- . ------------------- ... ------------------- # p(1)-1 p(2)-1 p(n)-1 # Ver la demostración en http://bit.ly/2zUXZPc # producto(xs) es el producto de los elementos de xs. Por ejemplo, # producto([2, 3, 5]) == 30 def producto(xs: list[int]) -> int: return reduce(mul, xs) # sumaDivisoresPropios3(x) es la suma de los divisores propios de # x. Por ejemplo, # sumaDivisoresPropios3(220) == 284 # sumaDivisoresPropios3(284) == 220 def sumaDivisoresPropios3(x: int) -> int: return producto([(p**(e+1)-1) // (p-1) for (p,e) in factorint(x).items()]) - x def sucesionAmigos3() -> Iterator[tuple[int, int]]: return ((x,y) for x in count(2) if (y := sumaDivisoresPropios3(x)) > x and sumaDivisoresPropios3(y) == x) def amigosMenores3(n: int) -> list[tuple[int, int]]: return list(takewhile(lambda par: par[1] < n, sucesionAmigos3())) def sumaAmigosMenores3(n: int) -> int: return sum(x + y for x, y in amigosMenores3(n)) # 4ª solución # =========== # sumaDivisoresPropios4(x) es la suma de los divisores propios de # x. Por ejemplo, # sumaDivisoresPropios4(220) == 284 # sumaDivisoresPropios4(284) == 220 def sumaDivisoresPropios4(x: int) -> int: return divisor_sigma(x, 1) - x def sucesionAmigos4() -> Iterator[tuple[int, int]]: return ((x,y) for x in count(2) if (y := sumaDivisoresPropios4(x)) > x and sumaDivisoresPropios4(y) == x) def amigosMenores4(n: int) -> list[tuple[int, int]]: return list(takewhile(lambda par: par[1] < n, sucesionAmigos4())) def sumaAmigosMenores4(n: int) -> int: return sum(x + y for x, y in amigosMenores4(n)) # Verificación # ============ def test_sumaAmigosMenores() -> None: for sumaAmigosMenores in [sumaAmigosMenores1, sumaAmigosMenores2, sumaAmigosMenores3, sumaAmigosMenores4]: assert sumaAmigosMenores(2000) == 2898 print("Verificado") # La verificación es # >>> test_sumaAmigosMenores() # Verificado # Comprobación de la equivalencia de las definiciones # =================================================== # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_sumaAmigosMenores_equiv(n: int) -> None: r = sumaAmigosMenores1(n) assert sumaAmigosMenores2(n) == r assert sumaAmigosMenores3(n) == r assert sumaAmigosMenores4(n) == r # La comprobación es # >>> test_sumaAmigosMenores_equiv() # >>> # 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('sumaAmigosMenores1(6000)') # 1.25 segundos # >>> tiempo('sumaAmigosMenores1(7000)') # 3.82 segundos # >>> tiempo('sumaAmigosMenores2(7000)') # 0.16 segundos # >>> tiempo('sumaAmigosMenores3(7000)') # 0.08 segundos # >>> tiempo('sumaAmigosMenores4(7000)') # 0.80 segundos # # >>> tiempo('sumaAmigosMenores2(90000)') # 1.61 segundos # >>> tiempo('sumaAmigosMenores3(90000)') # 0.93 segundos