{"id":5313,"date":"2019-12-31T05:30:22","date_gmt":"2019-12-31T03:30:22","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5313"},"modified":"2020-01-07T07:44:11","modified_gmt":"2020-01-07T05:44:11","slug":"derivada-aritmetica","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/derivada-aritmetica\/","title":{"rendered":"Derivada aritm\u00e9tica"},"content":{"rendered":"

La derivada aritm\u00e9tica<\/a> es una funci\u00f3n definida sobre los n\u00fameros naturales por analog\u00eda con la regla del producto para el c\u00e1lculo de las derivadas usada en an\u00e1lisis.<\/p>\n

Para un n\u00famero natural n su derivada D(n) se define por<\/p>\n

\n   D(0)  = 0\n   D(1)  = 0\n   D(p)  = 1, si p es primo\n   D(ab) = D(a)b + aD(b) (regla de Leibniz para derivar productos)\n<\/pre>\n
Por ejemplo,<\/p>\n
\n   D(6)  = D(2*3) = D(2)*3 + 2*D(3) = 1*3 + 2*1 =  5\n   D(12) = D(2*6) = D(2)*6 + 2*D(6) = 1*6 + 2*5 = 16\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   derivada :: Integer -> Integer\n<\/pre>\n
tal que (derivada n) es la derivada aritm\u00e9tica de n. Por ejemplo,<\/p>\n
\n   derivada  6  ==  5\n   derivada 12  ==  16\n   maximum [derivada n | n <- [1..60000]]  ==  380928\n<\/pre>\n
Comprobar con QuickCheck que si x es un n\u00famero entero positivo y su descomposici\u00f3n en factores primos es<\/p>\n
\n   x = p(1)^e(1) + p(2)^e(2) +...+ p(n)^e(n)\n<\/pre>\n
entonces la derivada de x es<\/p>\n
\n   x * [e(1)\/p(1) + e(2)\/p(2) +...+ e(n)\/p(n)]\n<\/pre>\n
Nota<\/em>: No usar en la definici\u00f3n la propiedad que hay que comprobar.<\/p>\n
Soluciones<\/h4>\n
\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (isPrime, primeFactors)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nderivada :: Integer -> Integer\nderivada 0 = 0\nderivada 1 = 0\nderivada n | esPrimo n = 1\n           | otherwise = (derivada a) * b + a * (derivada b)\n  where a = menorFactor n\n        b = n `div` a\n\n-- (esPrimo n) se verifica si n es primo. Por ejemplo,\n--    esPrimo 5  ==  True\n--    esPrimo 6  ==  False\nesPrimo :: Integer -> Bool\nesPrimo 0 = False\nesPrimo 1 = False\nesPrimo n = n == menorFactor n\n\n-- (menorFactor n) es el menor divisor primo de n (con n >= 2). Por\n-- ejemplo, \n--    menorFactor 6   ==  2\n--    menorFactor 7   ==  7\n--    menorFactor 15  ==  3\nmenorFactor :: Integer -> Integer\nmenorFactor n\n  | even n = 2\n  | otherwise = head [x | x <- [3,5..]\n                        , n `mod` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nderivada2 :: Integer -> Integer\nderivada2 0 = 0\nderivada2 1 = 0\nderivada2 n | isPrime n = 1\n            | otherwise = (derivada2 a) * b + a * (derivada2 b)\n  where (a:_) = primeFactors n\n        b     = n `div` a\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> maximum [derivada n | n <- [1..10000]]\n--    53248\n--    (1.59 secs, 1,091,452,552 bytes)\n--    \u03bb> maximum [derivada2 n | n <- [1..10000]]\n--    53248\n--    (0.17 secs, 457,819,120 bytes)\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_derivada :: Integer -> Property\nprop_derivada x =\n  x > 0 ==>\n  derivada x == sum [(x * e) `div` p | (p,e) <- factorizacion x]\n\n-- (factorizacion x) es la lista de las bases y exponentes de\n-- la descomposici\u00f3n prima de x. Por ejemplo,\n--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n  [(head xs,genericLength xs) | xs <- group (primeFactors n)]\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_derivada\n--    +++ OK, passed 100 tests.\n<\/pre>\n
Referencias<\/h4>\n