A derivada aritmética

34

A derivada de uma função é uma pedra angular da matemática, engenharia, física, biologia, química e também um grande número de outras ciências. Hoje vamos calcular algo apenas tangencialmente relacionado: a derivada aritmética.

Definição

A derivada aritmética a(n)ou n'é definida aqui ( A003415 ) por um número de propriedades semelhantes à derivada de uma função.

  • a(0) = a(1) = 0,
  • a(p) = 1, onde pestá qualquer prime, e
  • a(mn) = m*a(n) + n*a(m).

A terceira regra é baseada na regra do produto para a diferenciação de funções: para funções f(x)e g(x), (fg)' = f'g + fg'. Então, com números (ab)' = a'b + ab'.

Além disso, como a derivada aritmética pode ser estendida aos números negativos por meio dessa relação simples a(-n) = -a(n), a entrada pode ser negativa.

Regras

  • Escreva um programa ou função que, dado qualquer número inteiro n, retorne a derivada aritmética de n.
  • As entradas serão , para evitar problemas com tamanhos e números inteiros muito grandes para levar em consideração uma quantidade de tempo razoável. Seu algoritmo ainda deve ser capaz de calcular teoricamente a derivada aritmética de números fora desse intervalo.-230 < n < 230
  • São permitidos embutidos para matemática simbólica, fatoração principal e diferenciação.

Exemplos

> 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 sempre, se o problema não estiver claro, entre em contato. Boa sorte e bom golfe!

Sherlock9
fonte
O que, exatamente, é primeem a(prime)? É apenas um número primo?
Stackstuck 17/04
Além disso, não entendo como você decompôs o último exemplo.
Stackstuck 17/04
@Stackstuck Sim, é qualquer prime. Eu editei para maior clareza. Além disso, adicionei o último exemplo para, com sorte, torná-lo mais claro.
Sherlock9

Respostas:

10

MATL , 12 bytes

|1>?GtYf/s}0

Experimente online!

Explicação

Considere um número inteiro a com | a |> 1, e deixe os fatores primários (possivelmente repetidos) de | a | seja f 1 , ..., f n . Então o resultado desejado é a · (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
fonte
A soma dos fatores primos de 1 não é igual a 0? Ou isso não funciona no MATL?
wythagoras
@wythagoras Na verdade, 11como decomposição de números "primos". É um resultado estranho (uma matriz vazia seria mais significativa). Mas é assim que o Matlab funciona. E também CJam. Então eu acho que deve haver uma boa razão para produzir 1nesse caso? O que você acha? Fui tentado a redefinir a Yffunção para gerar uma matriz vazia 1, mas não tinha certeza
Luis Mendo
1
Pyth fornece uma matriz vazia, fwiw.
Isaacg
@isaacg Thanks! Talvez eu mude isso
Luis Mendo
O mesmo no Mathematica (quase foi um problema uma 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)

Uma função recursiva. Em entradas grandes, fica sem profundidade de pilha em sistemas típicos, a menos que você a execute com algo como o Stackless Python .

A definição recursiva é implementada diretamente, contando até a busca de fatores primos candidatos. Desde af(prime)=1 , se ntem um primo pcomo um fator, nós temos f(n) == p*f(n/p)+n/p.

xnor
fonte
Você não precisa de entrada e impressão? Pelo menos quando executo isso (Python 2), não obtenho resultado.
Wythagoras 3/04
@wythagoras Por padrão, as funções são permitidas como uma alternativa aos programas. Além disso, esse desafio diz "programa ou função".
Xnor
7

Geléia, 8 7 bytes

-1 byte por @Dennis

ÆfḟṠ³:S

Usa a mesma fórmula que todo mundo faz. No entanto, há um pequeno truque para lidar com0 .

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.

Experimente aqui .

lirtosiast
fonte
Você pode adicionar uma explicação? Eu gosto de respostas para ter explicações antes de votá-las.
Sherlock9
@ Sherlock9 Concluído.
precisa saber é o seguinte
Vejo que sua resposta foi jogada e a explicação está desatualizada. Você poderia consertar isso? Graças: 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

Melhorias graças 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

Melhoria adicional em dois 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

Melhorias adicionais graças ao @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

Explicação

A derivada aritmética de aé igual a avezes a soma dos recíprocos dos fatores primos de a. Nenhuma exceção para 1 é necessária, uma vez que a soma dos recíprocos dos fatores primos de 1 é zero.

wythagoras
fonte
abs(a)>1pode ser a*a>1.
Xnor #
@ xnor Sim, obrigado.
Wythagoras 03/04
Substitua a linha 2 pord,s = 2,0
Agnishom Chattopadhyay 04/04
@AgnishomChattopadhyay Ambos têm 8 bytes no total.
Wythagoras 04/04
4

Haskell, 203 90 bytes

Obrigado @nimi!

Ainda não tenho idéia de quando quais recuos causam qual interpretação, esse é o mais curto que consegui até agora e, como sempre, tenho certeza de que pode jogar muito mais. Vou tentar novamente à noite.

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]
flawr
fonte
1
Muito obrigado, professor =) Eu sempre posso aprender muito sempre que você me ajudar aqui! Sinta-se livre para adicionar sua versão como sua própria resposta!
flawr
4

J, 30 27 19 caracteres

Obrigado a @Dennis por cortar 3 caracteres.

Obrigado ao @Zgarb por cortar 8 caracteres.

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

Experimente online!

Entrada de amostra:

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

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

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

Como 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
Freira Furada
fonte
3

Pitão - 10 8 bytes

Amando a entrada implícita! Deve equipará-lo a Jelly para a maioria das coisas (exceto as habilidades de golfe de Dennis).

*scL1P.a

Conjunto de Teste .

*             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
fonte
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 a definição recursiva diretamente, com uma variável auxiliar pque conta até procurar possíveis fatores primos, começando em 2. A última linha é a função principal, que se conecta p=2à função binária definida na primeira linha.

A função verifica cada caso por sua vez:

  • Se n*n<2, então né um dos -1,0,1, e o resultado é 0.
  • Se nnão for múltiplo de p, aumentep and continue.
  • Caso contrário, expresse n=p*re pela propriedade "derivada", o resultado é r*a(p)+p*a(r), o que simplifica r+p*a(r)porque pé primo.

The last case saves bytes by binding r in a guard, which also avoids the 1>0 for the boilerplate otherwise. If r could be bound earlier, the second condition mod n p>0 could be checked as r*p==n, which is 3 bytes shorter, but I don't see how to do that.

xnor
fonte
3

Seriously, 17 14 11 12 bytes

My first ever Seriously answer. This answer is based on Luis Mendo's MATL 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. My addition is to note that, if m = p1e1·p2e2·...·pnen, then a(m) = m·(e1/p1 + e2/p2 + ... + en/pn). Thanks to Mego for golfing and bug fixing help. Try it online!

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

Ungolfing:

,             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
fonte
3

Japt -x, 16 13 10 bytes

ÒU©a k £/X

- 6 bytes thanks to @Shaggy

Try it online!

Quintec
fonte
Both fail for negative numbers because, for some reason, N.k() doesn't work on them.
Shaggy
Here's a fix, with some golfing.
Shaggy
Or -2 more byes with the -x flag.
Shaggy
@Shaggy Thanks, nice
Quintec
3

APL (Dyalog Extended), 13 9 bytes

A simple solution. The Dyalog Unicode version was simply a longer version of this so it has been omitted.

Edit: Saved 4 bytes by adopting the method in lirtosiast's Jelly solution.

{+/⍵÷⍭|⍵}

Try it online!

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
fonte
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
fonte
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.
fonte
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
fonte
1

Mathematica 10.0, 39 bytes

Tr[If[#>1,#2/#,0]&@@@FactorInteger@#]#&
feersum
fonte
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
fonte
0

Perl 5, 62 bytes

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

Uses the formula (from OEIS): If n = Product p_i^e_i, a(n) = n * Sum (e_i/p_i).

msh210
fonte
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

This might be a bit slow for large numbers. Replace 2..^n with 2..n.sqrt for longer code but faster computation.

bb94
fonte
0

Ink, 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

Try it online!

I refuse to believe this is a good solution, but I can't see a way to improve it either.

Sara J
fonte