Números superabundantes
El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1983 es
Sea n un número entero positivo. Sea σ(n) la suma de los divisores positivos de n (incluyendo al 1 y al n). Se dice que un entero m ≥ 1 es superabundante (P. Erdös, 1944) si ∀k ∈ {1, 2, …, m-1}, σ(m)/m > σ(k)/k. Demostrar que esisten infinitos números superabundantes.
Definir la lista
1 |
superabundantes :: [Integer] |
cuyos elementos son los números superabundantes. Por ejemplo,
1 2 |
take 7 superabundantes == [1,2,4,6,12,24,36] superabundantes !! 25 == 166320 |
Soluciones
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 |
import Data.Numbers.Primes (primeFactors) import Data.List (genericLength, group) import Data.Ratio ((%)) -- 1ª solución -- =========== superabundantes :: [Integer] superabundantes = filter esSuperabundante [1..] -- (esSuperabundante n) se verifica si n es superabundante. Por ejemplo, -- esSuperabundante 4 == True -- esSuperabundante 5 == False -- esSuperabundante 6 == True esSuperabundante :: Integer -> Bool esSuperabundante n = and [k * n' > n * sumaDivisores k | k <- [1..n-1]] where n' = sumaDivisores n -- (sumaDivisores n) es la suma de los divisores de n. Por ejemplo. -- sumaDivisores 35 == 48 sumaDivisores :: Integer -> Integer sumaDivisores x = product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x] -- (factorizacion x) es la lista de las bases y exponentes de la -- descomposición prima de x. Por ejemplo, -- factorizacion 600 == [(2,3),(3,1),(5,2)] factorizacion :: Integer -> [(Integer,Integer)] factorizacion = map primeroYlongitud . group . primeFactors -- (primeroYlongitud xs) es el par formado por el primer elemento de xs -- y la longitud de xs. Por ejemplo, -- primeroYlongitud [3,2,5,7] == (3,4) primeroYlongitud :: [a] -> (a,Integer) primeroYlongitud (x:xs) = (x, 1 + genericLength xs) primeroYlongitud _ = error "No tiene elementos" -- 2ª solución -- =========== superabundantes2 :: [Integer] superabundantes2 = [n | (n,a,b) <- zip3 [1..] cocientes maximosCocientes, a == b] -- cocientes es la lista de los cocientes σ(k)/k. Por ejemplo, -- λ> take 7 cocientes -- [1 % 1,3 % 2,4 % 3,7 % 4,6 % 5,2 % 1,8 % 7] cocientes :: [Rational] cocientes = [sumaDivisores n % n | n <- [1..]] -- maximosCocientes es la lista de los máximos de los cocientes -- σ(k)/k. Por ejemplo, -- λ> take 7 maximosCocientes -- [1 % 1,3 % 2,3 % 2,7 % 4,7 % 4,2 % 1,2 % 1] maximosCocientes :: [Rational] maximosCocientes = scanl1 max cocientes -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> superabundantes !! 22 -- 27720 -- (6.72 secs, 11,453,705,704 bytes) -- λ> superabundantes2 !! 22 -- 27720 -- (0.54 secs, 902,054,096 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
2 Comentarios