{"id":1946,"date":"2016-01-04T06:00:17","date_gmt":"2016-01-04T04:00:17","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1946"},"modified":"2016-05-01T20:08:05","modified_gmt":"2016-05-01T18:08:05","slug":"2016-es-un-numero-practico","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/2016-es-un-numero-practico\/","title":{"rendered":"2016 es un n\u00famero pr\u00e1ctico"},"content":{"rendered":"

Un entero positivo n es un n\u00famero pr\u00e1ctico<\/strong><\/a> si todos los enteros positivos menores que \u00e9l se pueden expresar como suma de distintos divisores de n. Por ejemplo, el 12 es un n\u00famero pr\u00e1ctico, ya que todos los enteros positivos menores que 12 se pueden expresar como suma de divisores de 12 (1, 2, 3, 4 y 6) sin usar ning\u00fan divisor m\u00e1s de una vez en cada suma:<\/p>\n

\n    1 = 1\n    2 = 2\n    3 = 3\n    4 = 4\n    5 = 2 + 3\n    6 = 6\n    7 = 1 + 6\n    8 = 2 + 6\n    9 = 3 + 6\n   10 = 4 + 6\n   11 = 1 + 4 + 6\n<\/pre>\n
En cambio, 14 no es un n\u00famero pr\u00e1ctico ya que 6 no se puede escribir como suma, con sumandos distintos, de divisores de 14.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n   esPractico :: Integer -> Bool\n<\/pre>\n
tal que (esPractico n) se verifica si n es un n\u00famero pr\u00e1ctico. Por ejemplo,<\/p>\n
\n   esPractico 12                                      ==  True\n   esPractico 14                                      ==  False\n   esPractico 2016                                    ==  True\n   esPractico 42535295865117307932921825928971026432  ==  True\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.List (genericLength, group, nub, sort, subsequences)\nimport Data.Numbers.Primes (primeFactors)\nimport Graphics.Gnuplot.Simple\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nesPractico1 :: Integer -> Bool\nesPractico1 n =\n    takeWhile ( [Integer]\ndivisores n = [k | k <- [1..n-1], n `mod` k == 0]\n\n-- (sumas xs) es la lista ordenada de n\u00fameros que se pueden obtener como\n-- sumas de elementos de xs sin usar ning\u00fan elemento m\u00e1s de una vez en\n-- cada suma. Por ejemplo,  \n--    sumas [1,2,3]  ==  [0,1,2,3,4,5,6]\n--    sumas [1,2,7]  ==  [0,1,2,3,7,8,9,10]\nsumas :: [Integer] -> [Integer]\nsumas xs = sort (nub (map sum (subsequences xs)))\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nesPractico2 :: Integer -> Bool\nesPractico2 n = all (esSumable (divisores n)) [1..n-1]\n\n-- (esSumable xs n) se verifica si n se puede escribir como una suma de\n-- elementos distintos de la lista creciente xs. Por ejemplo,\n--    esSumable [1,2,7] 8  ==  True\n--    esSumable [1,2,7] 6  ==  False\n--    esSumable [1,2,7] 4  ==  False\n--    esSumable [1,2,7] 2  ==  True\n--    esSumable [1,2,7] 0  ==  True\nesSumable :: [Integer] -> Integer -> Bool\nesSumable _ 0  = True\nesSumable [] _ = False\nesSumable (x:xs) n = x <= n && (esSumable xs (n-x) || esSumable xs n)\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\n-- Usando la caracterizaci\u00f3n de Stewart y Sierpi\u0144ski: un entero n >= 2\n-- es pr\u00e1ctico syss para su factorizaci\u00f3n prima\n--    n = p(1)^e(1) * p(2)*e(2) *...* p(k)^e(k)\n-- se cumple que p(1) = 2 y, para cada i de 2 a k se cumple que\n--                         1+e(j) \n--                i-1  p(j)       - 1\n--    p(i) <= 1 +  \u220f  ----------------\n--                j=1     p(j) - 1\n\nesPractico3 :: Integer -> Bool\nesPractico3 1 = True\nesPractico3 n = \n    x == 2 &&\n    and [p <= 1 + c | (p,c) <- zip bases cotas]\n    where xss       = factorizacion n\n          (x:bases) = map fst xss\n          cotas     = scanl1 (*) [(p^(1+e)-1) `div` (p-1) | (p,e) <- xss]\n\n-- (factorizacion n) es la factorizaci\u00f3n de n. Por ejemplo, \n--    factorizacion  600  ==  [(2,3),(3,1),(5,2)]\n--    factorizacion 1400  ==  [(2,3),(5,2),(7,1)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n    [(head xs,genericLength xs) | xs <- group (primeFactors n)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> length [n | n <- [1..400], esPractico1 n]\n--    92\n--    (40.21 secs, 8,378,539,464 bytes)\n--    \u03bb> length [n | n <- [1..400], esPractico2 n]\n--    92\n--    (8.29 secs, 1,109,669,760 bytes)\n--    \u03bb> length [n | n <- [1..400], esPractico3 n]\n--    92\n--    (0.02 secs, 0 bytes)\n<\/pre>\n
Referencias<\/h4>\n
Basado en el art\u00edculo de Gaussianos Feliz Navidad y Feliz A\u00f1o (n\u00famero pr\u00e1ctico) 2016<\/a>.<\/p>\n
Otras referencias<\/p>\n