Das arithmetische Derivat

34

Die Ableitung einer Funktion ist ein Eckpfeiler von Mathematik, Ingenieurwissenschaften, Physik, Biologie, Chemie und einer Vielzahl anderer Wissenschaften. Heute werden wir etwas berechnen, das nur tangential zusammenhängt: die arithmetische Ableitung.

Definition

Die arithmetische Ableitung a(n)oder n'wird hier ( A003415 ) durch eine Reihe von Eigenschaften definiert, die der Ableitung einer Funktion ähnlich sind.

  • a(0) = a(1) = 0,
  • a(p) = 1Wo pist eine Primzahl, und
  • a(mn) = m*a(n) + n*a(m).

Die dritte Regel wird zur Differenzierung von Funktionen auf die Produktregel zugrunde: für Funktionen f(x)und g(x), (fg)' = f'g + fg'. Also mit Zahlen (ab)' = a'b + ab'.

Es ist auch zu beachten, dass a(-n) = -a(n)die Eingabe negativ sein kann, da die arithmetische Ableitung über diese einfache Beziehung auf die negativen Zahlen erweitert werden kann.

Regeln

  • Schreiben Sie ein Programm oder eine Funktion, die bei einer beliebigen Ganzzahl ndie arithmetische Ableitung von zurückgibt n.
  • Eingaben werden sein , um Probleme mit ganzzahligen Größen und Zahlen zu vermeiden, die zu groß sind, um einen angemessenen Zeitraum zu berücksichtigen. Ihr Algorithmus sollte theoretisch in der Lage sein, die arithmetische Ableitung von Zahlen außerhalb dieses Bereichs zu berechnen.-230 < n < 230
  • Eingebaute Funktionen für symbolische Mathematik, Primfaktorisierung und Differenzierung sind zulässig.

Beispiele

> 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

Wie immer, wenn das Problem unklar ist, lassen Sie es mich bitte wissen. Viel Glück und gutes Golfen!

Sherlock9
quelle
Was genau ist primedrin a(prime)? Ist es nur eine Primzahl?
Stackstuck
Außerdem verstehe ich nicht, wie Sie das letzte Beispiel zerlegt haben.
Stackstuck
@Stackstuck Ja, es ist eine Primzahl. Ich habe aus Gründen der Übersichtlichkeit bearbeitet. Außerdem habe ich das letzte Beispiel hinzugefügt, um es hoffentlich klarer zu machen.
Sherlock9

Antworten:

10

MATL , 12 Bytes

|1>?GtYf/s}0

Probieren Sie es online!

Erläuterung

Betrachte eine ganze Zahl a mit | a |> 1 und lassen Sie die (möglicherweise wiederholten) Primfaktoren von | a | sei f 1 , ..., f n . Dann ist das gewünschte Ergebnis 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
quelle
Ist die Summe der Primfaktoren von 1 nicht gleich 0? Oder funktioniert das in MATL nicht?
Wythagoras
@wythagoras Eigentlich 1gibt 1als „Prime“ Nummer Zersetzung. Es ist ein seltsames Ergebnis (ein leeres Array wäre sinnvoller). Aber so funktioniert Matlab. Und auch CJam. Es muss also einen guten Grund geben, 1in diesem Fall auszugeben . Was denkst du? Ich war versucht, die YfFunktion zur Ausgabe eines leeren Arrays für neu zu definieren 1, aber ich war mir nicht sicher
Luis Mendo
1
Pyth liefert ein leeres Array, fwiw.
Isaacg
@isaacg Danke! Vielleicht werde ich das ändern
Luis Mendo
Gleiche in Mathematica (war fast ein Problem einmal)
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)

Eine rekursive Funktion. Bei großen Eingaben ist die Stack-Tiefe auf typischen Systemen unzureichend, es sei denn, Sie verwenden Stackless Python .

Die rekursive Definition wird direkt implementiert und zählt bis zur Suche nach Kandidatenprimfaktoren. Da f(prime)=1, wenn neine Primzahl pals Faktor hat, haben wir f(n) == p*f(n/p)+n/p.

xnor
quelle
Benötigen Sie keine Eingabe und keinen Ausdruck? Zumindest wenn ich das starte (Python 2), bekomme ich kein Ergebnis.
Wythagoras
@wythagoras Standardmäßig sind Funktionen als Alternative zu Programmen zulässig . Auch diese Herausforderung sagt "Programm oder Funktion".
Xnor
7

Gelee, 8 7 Bytes

-1 Byte von @Dennis

ÆfḟṠ³:S

Verwendet die gleiche Formel wie alle anderen. Es gibt jedoch einen kleinen Trick, mit dem man umgehen muss 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.

Probieren Sie es hier aus .

Lirtosiast
quelle
Können Sie bitte eine Erklärung hinzufügen? Ich möchte, dass Antworten Erklärungen haben, bevor ich sie abstimme.
Sherlock9
@ Sherlock9 Fertig.
Lirtosiast
Ich sehe, dass Ihre Antwort abgelehnt wurde und die Erklärung jetzt nicht mehr aktuell ist. Würden Sie das bitte reparieren? Danke: 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

Verbesserungen dank @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

Weitere Verbesserung um zwei 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

Weitere Verbesserung dank @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

Erläuterung

Die arithmetische Ableitung von aist gleich ader Summe der Kehrwerte der Primfaktoren von a. Es ist keine Ausnahme für 1 erforderlich, da die Summe der Kehrwerte der Primfaktoren von 1 Null ist.

Wythagoras
quelle
abs(a)>1kann sein a*a>1.
xnor
@xnor Ja, danke.
Wythagoras
Ersetzen Sie Zeile 2 durchd,s = 2,0
Agnishom Chattopadhyay
@AgnishomChattopadhyay Beide sind insgesamt 8 Bytes.
Wythagoras
4

Haskell, 203 90 Bytes

Vielen Dank @nimi!

Ich habe immer noch keine Ahnung, wann welche Einschnitte welche Interpretation verursachen, dies ist die kürzeste, die ich bisher geschafft habe, und wie immer bin ich sicher, dass es viel mehr Golf spielen kann. Ich werde es am Abend noch einmal versuchen.

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]
fehlerhaft
quelle
1
Vielen Dank, Lehrer =) Ich kann immer so viel lernen, wenn du mir hier hilfst! Fühlen Sie sich frei, Ihre Version als Ihre eigene Antwort hinzuzufügen!
Fehler
4

J, 30 27 19 Zeichen

Vielen Dank an @Dennis für das Abhacken von 3 Zeichen.

Vielen Dank an @Zgarb für das Abhacken von 8 Zeichen.

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

Probieren Sie es online!

Beispieleingabe:

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

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

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

Wie es funktioniert:

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
Undichte Nonne
quelle
3

Pyth - 10 8 Bytes

Liebt den impliziten Input! Sollte es für die meisten Dinge mit Jelly auf Augenhöhe bringen (außer Dennis 'Golffähigkeiten).

*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
quelle
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)

Implementiert die rekursive Definition direkt mit einer Hilfsvariablen p, die bis zur Suche nach potenziellen Primfaktoren ab zählt 2. Die letzte Zeile ist die Hauptfunktion, die p=2an die in der ersten Zeile definierte Binärfunktion anschließt.

Die Funktion prüft jeweils nacheinander:

  • Wenn n*n<2, dann nist einer von -1,0,1und das Ergebnis ist 0.
  • Wenn nnicht ein Vielfaches von ist p, erhöhen pund fortfahren.
  • Ansonsten drücke aus n=p*rund durch die "derivative" Eigenschaft ergibt sich das Ergebnis r*a(p)+p*a(r), was vereinfacht, r+p*a(r)weil pes prime ist.

Der letzte Fall speichert Bytes , die durch die Bindung rin einer Wache , die auch das vermeidet 1>0die vorformulierten otherwise. Wenn rfrüher gebunden werden mod n p>0könnte, könnte die zweite Bedingung als überprüft werden r*p==n, was 3 Bytes kürzer ist, aber ich verstehe nicht, wie das geht.

xnor
quelle
3

Im Ernst , 17 14 11 12 Bytes

Meine allererste ernsthafte Antwort. Diese Antwort basiert auf Luis Mendos MATL-Antwort und der Idee, dass die arithmetische Ableitung einer Zahl mgleich ist, wo sich jeder Primfaktor der Multiplizität befindet. Mein Zusatz ist zu beachten, dass, wenn , dannm·(1/p1 + 1/p2 + ... + 1/pn)p1...pnnm = p1e1·p2e2·...·pnena(m) = m·(e1/p1 + e2/p2 + ... + en/pn) . Vielen Dank an Mego für die Hilfe beim Golfen und bei der Fehlerbehebung. Probieren Sie es 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
quelle
3

APL (Dyalog Extended) , 13 9 Bytes

Eine einfache Lösung. Die Dyalog Unicode-Version war einfach eine längere Version davon und wurde daher weggelassen.

Bearbeiten: 4 Bytes gespart, indem die Methode in Lirtosiast's Jelly-Lösung übernommen wurde .

{+/⍵÷⍭|⍵}

Probieren Sie es 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
quelle
2

Ruby, 87 66 80 75 70 68 Bytes

Diese Antwort basiert auf der MATL-Antwort von Luis Mendo , der Python-Antwort von Wythagoras und der Vorstellung, dass die arithmetische Ableitung einer Zahl mgleich ist, wo sich jeder Primfaktor der Multiplizität befindet.m·(1/p1 + 1/p2 + ... + 1/pn)p1...pnn

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

Diese Funktion wird folgendermaßen aufgerufen:

> 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
quelle
2

Julia, 72 43 Bytes

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

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und einen Gleitkommawert zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Für eine Eingang ganzer Zahl n , wenn n 2 ≤ 1 return 0 sonst ist die prime Faktorisierung erhalten n 2 als a Dict, dann für jedes Ansaug- / Exponenten Paar, unterteilen die prime durch seine Exponenten, dann teilen n durch das Ergebnis. Dies ist nur Rechen n x / p , wobei p der wichtigste Faktor ist , und x ist die Exponenten, die die gleichen wie Summieren ist n / p , x - mal. Wir addieren das resultierende Array und dividieren es durch 2, da wir doppelt so viel summiert haben, wie wir brauchen. Das liegt an der Tatsache, dass wir n 2 faktorisiereneher als n |.). (Das ist ein Byte kürzer als Factoring | n

29 Bytes gespart dank Dennis!

Alex A.
quelle
1

Jolf, 13 Bytes

*jmauΜm)jd/1H

Ein großes Lob an die MATL-Antwort für den Algorithmus! Versuchen Sie es hier , oder testen sie alle auf einmal . (Gibt [key, out] in einem Array aus.)

Erläuterung

*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
quelle
1

Mathematica 10.0, 39 Bytes

Tr[If[#>1,#2/#,0]&@@@FactorInteger@#]#&
Feersum
quelle
1
Können Sie bitte eine Erklärung hinzufügen? Ich möchte, dass Antworten Erklärungen haben, bevor ich sie abstimme.
Sherlock9
1
@ Sherlock9 Dies ist eine ziemlich uninteressante Antwort, daher habe ich nicht vor, eine hinzuzufügen. Es ist in Ordnung, wenn niemand dagegen stimmt.
Feersum
Alles klar dann. Einen schönen Tag noch :)
Sherlock9
In der aktuellen Mathematica-Version FactorInteger@1ergibt sich {1,1}, so dass die IfFunktion nicht mehr benötigt wird und 10 Bytes eingespart werden.
Greg Martin
@ GregMartin Ernsthaft? Das ist noch inkonsistenter als der Wert, der {{1,1}}von meiner Version zurückgegeben wird ( {}ist das erwartete Ergebnis für mich).
Feersum
1

APL (NARS), 35 Zeichen, 70 Byte

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

Test und wie man es benutzt:

  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

Ich dachte, dass es nicht in Ordnung wäre, weil ich nicht weiß, ob die Variable c zusammengesetzt ist (und keine Primzahl) ... Scheint aber in Ordnung für den Test ...

RosLuP
quelle
0

Perl 5, 62 Bytes

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

Verwendet die Formel (aus OEIS): If n = Product p_i^e_i, a(n) = n * Sum (e_i/p_i).

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

Dies kann bei großen Zahlen etwas langsam sein. Ersetzen Sie 2..^ndurch 2..n.sqrtfür längeren Code, aber schnellere Berechnung.

bb94
quelle
0

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

Probieren Sie es online!

Ich weigere mich zu glauben, dass dies eine gute Lösung ist, aber ich sehe auch keinen Weg, sie zu verbessern.

Sara J
quelle