Derivada aritmética
La derivada aritmética es una función definida sobre los números naturales por analogía con la regla del producto para el cálculo de las derivadas usada en análisis.
Para un número natural n su derivada D(n) se define por
|
1 2 3 4 |
D(0) = 0 D(1) = 0 D(p) = 1, si p es primo D(ab) = D(a)b + aD(b) (regla de Leibniz para derivar productos) |
Por ejemplo,
|
1 2 |
D(6) = D(2*3) = D(2)*3 + 2*D(3) = 1*3 + 2*1 = 5 D(12) = D(2*6) = D(2)*6 + 2*D(6) = 1*6 + 2*5 = 16 |
Definir la función
|
1 |
derivada :: Integer -> Integer |
tal que (derivada n) es la derivada aritmética de n. Por ejemplo,
|
1 2 3 |
derivada 6 == 5 derivada 12 == 16 maximum [derivada n | n <- [1..60000]] == 380928 |
Comprobar con QuickCheck que si x es un número entero positivo y su descomposición en factores primos es
|
1 |
x = p(1)^e(1) + p(2)^e(2) +...+ p(n)^e(n) |
entonces la derivada de x es
|
1 |
x * [e(1)/p(1) + e(2)/p(2) +...+ e(n)/p(n)] |
Nota: No usar en la definición la propiedad que hay que comprobar.
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 71 72 73 74 |
import Data.List (genericLength, group) import Data.Numbers.Primes (isPrime, primeFactors) import Test.QuickCheck -- 1ª solución -- =========== derivada :: Integer -> Integer derivada 0 = 0 derivada 1 = 0 derivada n | esPrimo n = 1 | otherwise = (derivada a) * b + a * (derivada b) where a = menorFactor n b = n `div` a -- (esPrimo n) se verifica si n es primo. Por ejemplo, -- esPrimo 5 == True -- esPrimo 6 == False esPrimo :: Integer -> Bool esPrimo 0 = False esPrimo 1 = False esPrimo n = n == menorFactor n -- (menorFactor n) es el menor divisor primo de n (con n >= 2). Por -- ejemplo, -- menorFactor 6 == 2 -- menorFactor 7 == 7 -- menorFactor 15 == 3 menorFactor :: Integer -> Integer menorFactor n | even n = 2 | otherwise = head [x | x <- [3,5..] , n `mod` x == 0] -- 2ª solución -- =========== derivada2 :: Integer -> Integer derivada2 0 = 0 derivada2 1 = 0 derivada2 n | isPrime n = 1 | otherwise = (derivada2 a) * b + a * (derivada2 b) where (a:_) = primeFactors n b = n `div` a -- Comparación de eficiencia -- ========================= -- λ> maximum [derivada n | n <- [1..10000]] -- 53248 -- (1.59 secs, 1,091,452,552 bytes) -- λ> maximum [derivada2 n | n <- [1..10000]] -- 53248 -- (0.17 secs, 457,819,120 bytes) -- Propiedad -- ========= -- La propiedad es prop_derivada :: Integer -> Property prop_derivada x = x > 0 ==> derivada x == sum [(x * e) `div` p | (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 n = [(head xs,genericLength xs) | xs <- group (primeFactors n)] -- Su comprobación es -- λ> quickCheck prop_derivada -- +++ OK, passed 100 tests. |
Referencias
- Arithmetic derivative en Wikipedia.
- Sucesión A003415 de OEIS.
Pensamiento
En ese jardín, Guiomar,
el mutuo jardín que inventan
dos corazones al par,
se funden y complementan
nuestras horas.Antonio Machado
No consigo hacer correctamente la propiedad.