La derivada aritmética

34

La derivada de una función es una piedra angular de las matemáticas, la ingeniería, la física, la biología, la química y también una gran cantidad de otras ciencias. Hoy vamos a calcular algo solo relacionado tangencialmente: la derivada aritmética.

Definición

La derivada aritmética a(n)o n'se define aquí ( A003415 ) por una serie de propiedades que son similares a la derivada de una función.

  • a(0) = a(1) = 0,
  • a(p) = 1, donde pes cualquier primo, y
  • a(mn) = m*a(n) + n*a(m).

La tercera regla se basa en la regla del producto para la diferenciación de funciones: las funciones f(x)y g(x), (fg)' = f'g + fg'. Así que con los números, (ab)' = a'b + ab'.

También es de destacar que, dado que la derivada aritmética se puede extender a los números negativos a través de esta simple relación a(-n) = -a(n), la entrada puede ser negativa.

Reglas

  • Escriba un programa o función que, dado cualquier número entero n, devuelva la derivada aritmética de n.
  • Las entradas serán , para evitar problemas con los tamaños enteros y los números demasiado grandes para tener en cuenta una cantidad de tiempo razonable. Su algoritmo aún debería ser capaz de calcular teóricamente la derivada aritmética de números fuera de este rango.-230 < n < 230
  • Se permiten incorporados para matemática simbólica, factorización prima y diferenciación.

Ejemplos

> a(1)
0
> a(7)
1
> a(14)   # a(7)*2 + a(2)*7 = 1*2 + 1*7 = 9
9
> a(-5)   # a(-5) = -a(5) = -1
-1
> a(8)    # a(8) = a(2**3) = 3*2**2 = 12
12
> a(225)  # a(225) = a(9)*25 + a(25)*9 = 6*25 + 10*9 = 150 + 90 = 240
240
> a(299792458)  # a(299792458) = a(2)*149896229 + a(7)*42827494 + a(73)*4106746 + a(293339)*1022 = 1*149896229 + 1*42827494 + 1*4106746 + 1*1022 = 149896229 + 42827494 + 4106746 + 1022 = 196831491
196831491

Como siempre, si el problema no está claro, hágamelo saber. ¡Buena suerte y buen golf!

Sherlock9
fuente
¿Qué, exactamente, es primeen a(prime)? ¿Es solo un número primo?
Stackstuck
Además, no entiendo cómo descompuso el último ejemplo.
Stackstuck
@Stackstuck Sí, es primordial. He editado para mayor claridad. Además, agregué el último ejemplo para que sea más claro.
Sherlock9

Respuestas:

10

MATL , 12 bytes

|1>?GtYf/s}0

Pruébalo en línea!

Explicación

Considere un entero a con | a |> 1, y deje que los factores primos (posiblemente repetidos) de | a | ser f 1 , ..., f n . Entonces el resultado deseado es un · (1 / f 1 + ... + 1 / f n ).

|1>     % take input's absolute value. Is it greater than 1?
?       % if so:
  Gt    %   push input twice
  Yf    %   prime factors. For negative input uses its absolute value
  /     %   divide element-wise
  s     %   sum of the array
}       % else:
  0     %   push 0
Luis Mendo
fuente
¿No es la suma de los factores primos de 1 igual a 0? ¿O eso no funciona en MATL?
wythagoras
@wythagoras Realmente 1da 1como su descomposición de números "primos". Es un resultado extraño (una matriz vacía sería más significativa). Pero así es como funciona Matlab. Y también CJam. Entonces, ¿supongo que debe haber una buena razón para producir 1en ese caso? ¿Qué piensas? He tenido la tentación de redefinir la Yffunción para generar una matriz vacía 1, pero no estaba seguro
Luis Mendo
1
Pyth da una matriz vacía, fwiw.
isaacg
@isaacg ¡Gracias! Tal vez cambie eso
Luis Mendo
Lo mismo en Mathematica (fue casi un problema una vez)
CalculatorFeline
7

Python, 59 bytes

f=lambda n,p=2:+(n*n>1)and(n%p and f(n,p+1)or p*f(n/p)+n/p)

Una función recursiva. En entradas grandes, se queda sin profundidad de pila en los sistemas típicos a menos que lo ejecute con algo como Python apilable .

La definición recursiva se implementa directamente, contando para buscar factores primos candidatos. Dado que f(prime)=1, si ntiene un primo pcomo factor, tenemos f(n) == p*f(n/p)+n/p.

xnor
fuente
¿No necesita entrada e impresión? Al menos cuando ejecuto esto (Python 2), no obtengo ningún resultado.
wythagoras
@wythagoras Por defecto, las funciones están permitidas como una alternativa a los programas. Además, este desafío dice "programa o función".
xnor
7

Jalea, 8 7 bytes

-1 byte por @Dennis

ÆfḟṠ³:S

Utiliza la misma fórmula que todos los demás. Sin embargo, hay un pequeño truco con el que lidiar 0.

o¬AÆfİS×     Main link. Inputs: n
o¬             Logical OR of n with its logical NOT
               That is, 0 goes to 1 and everything else goes to itself.
  A            Then take the absolute value
   Æf          get its list of prime factors
     İ         divide 1 by those
      S        sum
       ×       and multiply by the input.

Probarlo aquí .

lirtosiast
fuente
¿Puedes por favor agregar una explicación? Me gusta que las respuestas tengan explicaciones antes de votarlas.
Sherlock9
@ Sherlock9 Hecho.
lirtosiast el
Veo que su respuesta ha sido cuestionada y la explicación está desactualizada. ¿Podrías arreglar eso? Gracias: D
Sherlock9
5

Python 2, 87 78 76 74 bytes

a=b=input()
d=2
s=0
while d<=abs(b):
    if a%d==0:
        a=a/d
        s+=b/d
    else:
        d+=1
print s

Mejoras gracias a @Maltysen:

a=b=input()
d=2
s=0
while d<=abs(b):
    if a%d==0:a/=d;s+=b/d
    else:d+=1
print s

Mejora adicional por dos bytes:

a=b=input()
d=2
s=0
while abs(a)>1:
    if a%d<1:a/=d;s+=b/d
    else:d+=1
print s

Mejora adicional gracias a @xnor:

a=b=input()
d=2
s=0
while a*a>1:
    if a%d<1:a/=d;s+=b/d
    else:d+=1
print s

Explicación

La derivada aritmética de aes igual a aveces la suma de los recíprocos de los factores primos de a. No se necesita ninguna excepción para 1 ya que la suma de los recíprocos de los factores primos de 1 es cero.

Wythagoras
fuente
abs(a)>1puede ser a*a>1.
xnor
@xnor Sí, gracias.
wythagoras
Reemplace la línea 2 cond,s = 2,0
Agnishom Chattopadhyay
@AgnishomChattopadhyay Ambos son 8 bytes en total.
wythagoras
4

Haskell, 203 90 bytes

Gracias @nimi!

Todavía no tengo idea de qué muescas causan qué interpretación, esta es la más corta que logré hasta ahora, y como siempre, estoy seguro de que se puede jugar mucho más. Voy a intentarlo de nuevo por la noche.

n#(x:_)|y<-div n x=x*a y+y*a x;_#_=1
a n|n<0= -a(-n)|n<2=0|1<2=n#[i|i<-[2..n-1],mod n i<1]
falla
fuente
1
Muchas gracias, maestra =) ¡Siempre puedo aprender mucho cuando me ayudas aquí! ¡Siéntase libre de agregar su versión como su propia respuesta!
flawr
4

J, 30 27 19 caracteres

Gracias a @Dennis por cortar 3 personajes.

Gracias a @Zgarb por cortar 8 personajes.

0:`(*[:+/%@q:@|)@.*

Pruébalo en línea!

Entrada de muestra:

0:`(*[:+/%@q:@|)@.* _8
_12

0:`(*[:+/%@q:@|)@.* 0
0

0:`(*[:+/%@q:@|)@.* 8
12

Cómo funciona:

0:`(*[:+/%@q:@|)@.* N
XX`[email protected]   if Z then Y else X end
0:                        X:  return 0
                  Z       Z:  signum(N)
   (*[:+/%@q:@|)          Y:  N*add_all(reciprocal_all(all_prime_factors(abs(N))))
                              N
    *                          *
      [:+/                      add_all(                                         )
          %@                            reciprocal_all(                         )
            q:@                                       all_prime_factors(      )
               |                                                        abs( )
                                                                            N
Monja permeable
fuente
3

Pyth - 10 8 bytes

Me encanta la entrada implícita! Debería equipararlo con Jelly para la mayoría de las cosas (excepto las habilidades de golf de Dennis).

*scL1P.a

Test Suite .

*             Times the input, implicitly (This also adds the sign back in)
 s            Sum
  cL1         Reciprocal mapped over lit
   P          Prime factorization
    .a        Absolute value of input, implicitly
Maltysen
fuente
3

Haskell, 59 bytes

n%p|n*n<2=0|mod n p>0=n%(p+1)|r<-div n p=r+p*r%2
(%2)

Implementa la definición recursiva directamente, con una variable auxiliar pque cuenta para buscar posibles factores primos, a partir de 2. La última línea es la función principal, que se conecta p=2a la función binaria definida en la primera línea.

La función comprueba cada caso por turno:

  • Si n*n<2, entonces nes uno de -1,0,1, y el resultado es 0.
  • Si nno es un múltiplo de p, incremente py continúe.
  • De lo contrario, exprese n=p*r, y por la propiedad "derivada", el resultado es r*a(p)+p*a(r), que se simplifica a r+p*a(r)porque pes primo.

El último caso ahorra bytes al vincularlos ren un resguardo , lo que también evita el uso 1>0de repeticiones otherwise. Si rpudiera vincularse antes, la segunda condición mod n p>0podría verificarse como r*p==n, que es 3 bytes más corta, pero no veo cómo hacerlo.

xnor
fuente
3

En serio , 17 14 11 12 bytes

Mi primera respuesta seria. Esta respuesta se basa en la respuesta MATL de Luis Mendo y la idea de que la derivada aritmética de un número mes igual a donde es cada factor primo de multiplicidad. Mi adición es tener en cuenta que, si , entonces . Gracias a Mego por el golf y la ayuda para corregir errores. Pruébalo en línea!m·(1/p1 + 1/p2 + ... + 1/pn)p1...pnnm = p1e1·p2e2·...·pnena(m) = m·(e1/p1 + e2/p2 + ... + en/pn)

,;w`i@/`MΣ*l

No golfista:

,             get a single input
 ;w           duplicate input and get prime factorization, p_f
               for input [-1..1], this returns [] and is dealt with at the end
   `   `M     map the function inside `` to p_f
    i         pop all elements of p_f[i], the prime and the exponent, to the stack
     @        rotate so that the exponent is at the top of the stack
      /       divide the exponent by the prime
         Σ    sum it all together
          *   multiply this sum with the input
           l  map and multiply do not affect an empty list, so we just take the length, 0
               l is a no-op for a number, so the result is unchanged for all other inputs
Sherlock9
fuente
3

APL (Dyalog Extended) , 13 9 bytes

Una solución simple La versión Dyalog Unicode era simplemente una versión más larga de esto, por lo que se ha omitido.

Editar: ahorró 4 bytes adoptando el método en la solución Jelly de lirtosiast .

{+/⍵÷⍭|⍵}

Pruébalo en línea!

Ungolfing

{+/⍵÷⍭|⍵}

{        }  A dfn, a function in {} brackets.
     ⍭|⍵   The prime factors of the absolute value of our input.
   ⍵÷      Then divide our input by the above array,
            giving us a list of products for the product rule.
 +/         We sum the above numbers, giving us our arithmetic derivative.
Sherlock9
fuente
2

Ruby, 87 66 80 75 70 68 bytes

This answer is based on Luis Mendo's MATL answer, wythagoras's Python answer, and the idea that the arithmetic derivative of a number m is equal to m·(1/p1 + 1/p2 + ... + 1/pn) where p1...pn is every prime factor of n to multiplicity.

->n{s=0;(2...m=n.abs).map{|d|(m/=d;s+=n/d)while m%d<1};m<2?0:s+0**s}

This function is called in the following way:

> a=->n{s=0;(2...m=n.abs).map{|d|(m/=d;s+=n/d)while m%d<1};m<2?0:s+0**s}
> a[299792458]
196831491

Ungolfing:

def a(n)
  s = 0
  m = n.abs
  (2...m).each do |z|
    while m%d == 0
      m /= d
      s += n / d
    end
  end
  if s == 0
    if n > 1
      s += 1 # if s is 0, either n is prime and the while loop added nothing, so add 1
             # or n.abs < 2, so return 0 anyway
             # 0**s is used in the code because it returns 1 if s == 0 and 0 for all other s
    end
  end
  return s
end
Sherlock9
fuente
2

Julia, 72 43 bytes

n->n^2>1?sum(p->n÷/(p...),factor(n^2))/2:0

This is an anonymous function that accepts an integer and returns a float. To call it, assign it to a variable.

For an input integer n, if n2 ≤ 1 return 0. Otherwise obtain the prime factorization of n2 as a Dict, then for each prime/exponent pair, divide the prime by its exponent, then divide n by the result. This is just computing n x / p, where p is the prime factor and x is its exponent, which is the same as summing n / p, x times. We sum the resulting array and divide that by 2, since we've summed twice as much as we need. That's due to the fact that we're factoring n2 rather than n. (Doing that is a byte shorter than factoring |n|.)

Saved 29 bytes thanks to Dennis!

Alex A.
fuente
1

Jolf, 13 bytes

*jmauΜm)jd/1H

Kudos to the MATL answer for the algorithm! Try it here, or test them all at once. (Outputs [key,out] in an array.)

Explanation

*jmauΜm)jd/1H
*j             input times
      m)j         p.f. of input
     Μ   d/1H      mapped to inverse
    u            sum of
  ma            abs of
Conor O'Brien
fuente
1

Mathematica 10.0, 39 bytes

Tr[If[#>1,#2/#,0]&@@@FactorInteger@#]#&
feersum
fuente
1
Can you please add an explanation? I like answers to have explanations before I upvote them.
Sherlock9
1
@Sherlock9 This is a quite uninteresting answer so I don't plan to add one. It's OK if no one upvotes it.
feersum
Alright, then. Have a good day :)
Sherlock9
In the current Mathematica version, FactorInteger@1 yields {1,1}, so the If function is no longer necessary, saving 10 bytes.
Greg Martin
@GregMartin Seriously? That's even more inconsistent than the value, {{1,1}}, returned by my version ({} is the expected result to me).
feersum
1

APL(NARS), 35 char, 70 bytes

{1≥a←∣⍵:0⋄1=≢k←πa:×⍵⋄c+m×∇c←⍵÷m←↑k}

test and how to use:

  f←{1≥a←∣⍵:0⋄1=≢k←πa:×⍵⋄c+m×∇c←⍵÷m←↑k}
  f 14
9
  f 8
12
  f 225
240
  f ¯5
¯1
  f 299792458
196831491

I thought that it would not be ok because I don't know if c variable is composed (and not a prime)... But seems ok for the test...

RosLuP
fuente
0

Perl 5, 62 bytes

perl -MMath::Prime::Util=:all -E"map$i+=1/$_,factor abs($j=<>);say$i*$j"

Utiliza la fórmula (de OEIS): If n = Product p_i^e_i, a(n) = n * Sum (e_i/p_i).

msh210
fuente
0

Perl 6, 90

sub A(\n) {0>n??-A(-n)!!(n>1)*{$_??n/$_*A($_)+$_*A n/$_!!1}(first n%%*,2..^n)};say A slurp

Esto puede ser un poco lento para grandes números. Reemplace 2..^ncon 2..n.sqrtun código más largo pero un cálculo más rápido.

bb94
fuente
0

Tinta , 183 bytes

==function a(n)
{n<0:
~return-a(-n)
}
{n<2:
~return 0
}
~temp f=t(n,2)
{f:
~return a(n/f)*f+n/f
}
~return 1
==function t(n,i)
{n>1&&n-i:
{n%i:
~return t(n,i+1)
}
~return i
}
~return 0

Pruébalo en línea!

Me niego a creer que esta sea una buena solución, pero tampoco veo una manera de mejorarla.

Sara J
fuente