Berechnen Sie das Kronecker-Symbol

9

Relevante Links hier und hier , aber hier ist die Kurzversion:

Sie haben eine Eingabe von zwei ganzen Zahlen aund bzwischen negativer Unendlichkeit und Unendlichkeit (obwohl ich bei Bedarf den Bereich einschränken kann, aber die Funktion muss immer noch negative Eingaben akzeptieren).

Definition des Kronecker-Symbols

Sie müssen das Kronecker-Symbol (a|b)für Eingaben aund bwo zurückgeben

(a|b) = (a|p_1)^e_1 * (a|p_2)^e_2 * ... * (a|p_n)^e_n

wo b = p_1^e_1 * p_2^e_2 * ... * p_n^e_nund p_iund e_isind die Primzahlen und Exponenten in der Primfaktorisierung von b.

Für eine ungerade Primzahl p, (a|p)=a^((p-1)/2) (mod p)wie hier definiert .

Für b == 2,(n|2)={0 for n even; 1 for n odd, n=+/-1 (mod 8); -1 for n odd, n=+/-3 (mod 8)

Für b == -1,(n|-1)={-1 for n<0; 1 for n>0

Wenn a >= b, (a|b) == (z|b)wo z == a % b. Durch diese Eigenschaft und wie hier und hier erklärt , aist ein quadratischer Rest von bif zis, obwohl a >= b.

(-1|b)= 1wenn b == 0,1,2 (mod 4)und -1wenn b == 3 (mod 4). (0|b)ist 0außer für (0|1)was ist 1, weil (a|1)ist immer 1und für negativ a, (-a|b) == (-1|b) * (a|b).

Die Ausgabe des Kronecker-Symbols ist immer dort -1, 0 or 1, wo die Ausgabe ist, 0wenn aund bhat gemeinsame Faktoren. If bist eine ungerade Primzahl, (a|b) == 1if aist ein quadratischer Rest mod bund -1wenn ist es kein quadratischer Rest.

Regeln

  • Ihr Code muss ein Programm oder eine Funktion sein.

  • Die Eingänge müssen in der Reihenfolge sein a b.

  • Der Ausgang muss entweder -1, 0oder 1.

  • Dies ist Code Golf, daher muss Ihr Code nicht effizient sein, sondern nur kurz.

  • Keine eingebauten Elemente, die den Kronecker oder die zugehörigen Jacobi- und Legendre-Symbole direkt berechnen. Andere integrierte Funktionen (z. B. zur Primfaktorisierung) sind Freiwild.

Beispiele

>>> kronecker(1, 5)
1
>>> kronecker(3, 8)
-1
>>> kronecker(15, 22)
1
>>> kronecker(21, 7)
0
>>> kronecker(5, 31)
1
>>> kronecker(31, 5)
1
>>> kronecker(7, 19)
1
>>> kronecker(19, 7)
-1
>>> kronecker(323, 455625)
1
>>> kronecker(0, 12)
0
>>> kronecker(0, 1)
1
>>> kronecker(12, 0)
0
>>> kronecker(1, 0)
1
>>> kronecker(-1, 5)
1
>>> kronecker(1, -5)
1
>>> kronecker(-1, -5)
-1
>>> kronecker(6, 7)
-1
>>> kronecker(-1, -7)
1
>>> kronecker(-6, -7)
-1

Dies ist eine komplizierte Funktion. Bitte lassen Sie mich wissen, wenn etwas unklar ist.

Sherlock9
quelle
Sind Sie sicher, dass Sie integrierte Funktionen nicht verbieten möchten? reference.wolfram.com/language/ref/KroneckerSymbol.html
Martin Ender
@ MartinBüttner Ich habe in Beispielen bearbeitet, als ich Ihren Kommentar sah. Ich werde integrierte Funktionen, die die Kronecker-, Jacobi- oder Legendre-Symbole direkt berechnen, nicht zulassen, aber alles andere (einschließlich Primfaktorisierungsfunktionen) sollte ein faires Spiel sein.
Sherlock9
Ich bin mir nicht ganz sicher, warum (31 | 5) 1 ergibt. Es sollte keinen qudratischen Rückstand geben. Warum ist es nicht -1?
Eumel
auch 7/19 sollte 1 sein und 19/7 sollte -1 sein, gemäß dem Wiki, das Sie verlinkt haben
Eumel
3
Wenn Lösungen negative und Null-Eingaben korrekt verarbeiten müssen, sollten Sie auf jeden Fall einige Testfälle hinzufügen.
Martin Ender

Antworten:

2

CJam (70 Bytes)

{_g\zmf+f{:P2+"W>2*(
z1=
;1
7&4-z[0W0X0]=
P%P+P(2/#P%_1>P*-"N/<W=~}:*}

Online-Demo (mit Mathematica generierte Testfälle).

Präparation

{               e# Anonymous function. Stack: a b
  _g\zmf+       e# Factorise b, with special treatment for negatives
                e# CJam also gives special treatment to 0 and 1
                e# Stack: e.g. a [-1 2 2 5]; or a [-1 1]; or a [0 0]; or a [1 2 2 5]
  f{            e# For each "prime" factor P, find (a|P)
    :P2+        e# Extract code for P from an array formed by splitting a string
    "W>2*(      e#   a -> (a|-1)
z1=             e#   a -> (a|0)
;1              e#   a -> (a|1)
7&4-z[0W0X0]=   e#   a -> (a|2)
P%P+P(2/#P%_1>P*-" e# a -> (a|P) for odd prime P
    N/<W=~      e# Split string and select appropriate element
  }
  :*            e# Multiply the components together
}

Ich habe verschiedene Möglichkeiten gefunden, (a|2)um die gleiche Anzahl von Zeichen zu bewerten , und habe mich für die mit der klarsten Darstellung entschieden.

integer array <W= Ist IMO eine ziemlich elegante Art, Fallbacks zu machen: Wenn die Ganzzahl größer als die Länge des Arrays ist, wählen wir das letzte Element aus.

Andere Kommentare

Es ist enttäuschend, dass für ungerade Primzahlen pder direkte Fermat-Stil (a|p)so kurz ist, weil es eine sehr gute Möglichkeit gibt, (a|n)positive ungerade zu finden, ndie ich verwenden wollte. Die Basis ist Zolotarevs Lemma:

Wenn pes sich um eine ungerade Primzahl und aeine ganzzahlige Koprime handelt, pist das Legendre-Symbol (a|p)das Zeichen der Permutationx -> ax (mod p)

Dies wurde von Frobenius zu verstärkt

Wenn aund bCoprime positive ungerade ganze Zahlen sind, ist das Jacobi-Symbol (a|b)das Zeichen der Permutationx -> ax (mod b)

und von Lerch zu

Wenn bes sich um eine positive ungerade Ganzzahl und aeine ganzzahlige Koprime handelt, bist das Jacobi-Symbol (a|b)das Vorzeichen der Permutationx -> ax (mod b)

Siehe Brunyate und Clark, Erweiterung des Zolotarev-Frobenius-Ansatzes auf quadratische Reziprozität , The Ramanujan Journal 37.1 (2014): 25-50 für Referenzen.

Und es kann leicht einen Schritt weiter gestärkt werden (obwohl ich dies in der Literatur nicht gesehen habe)

Wenn bes sich um eine positive ungerade Ganzzahl und aeine Ganzzahl handelt, ist das Jacobi-Symbol (a|b)das Levi-Civita-Symbol der Karte x -> ax (mod b).

Beweis: Wenn aes Koprime ist, verwenden bwir Zolotarev-Frobenius-Lerch; Andernfalls ist die Karte keine Permutation, und das Levi-Civita-Symbol ist 0wie gewünscht.

Dies ergibt die Jacobi-Symbolberechnung

{_2m*{~>},@ff*\ff%::-:*g}

Die spezielle Behandlung, die für (a|-1)und erforderlich ist, (a|2)bedeutet jedoch, dass ich keinen Weg gefunden habe, das Kronecker-Symbol zu berechnen, das bei diesem Ansatz kürzer ist: Es ist kürzer, die Primzahlen einzeln zu faktorisieren und zu behandeln.

Peter Taylor
quelle
4

Python 3, 747 369 335 Bytes

Als Beispiel Antwort, nur leicht Golf gespielt, und um Ihnen eine Vorstellung davon zu geben, wie eine Antwort aussehen wird.

Und ja, die Primfaktorisierungs- und Lauflängencodierungsbits werden von Pyth mit Entschuldigungen an isaacg abgeschnitten .

from itertools import*
def k(d,r):
 if d<0:a=-d;m=1
 else:a=d;m=0
 if r==1:return 1
 p=1;w=r;n=2;f=[]
 while n*n<=w:
  while w%n<1:w//=n;f+=n,
  n+=1
 if w>1:f+=w,
 z=[[k,len(list(g))]for k,g in groupby(f)]
 for i,j in z:
  if i==2:p*=pow(-1,(a*a-1)//8)
  x=pow(a,(i-1)//2,i)
  if x>1:x-=i
  p*=x**j
 if m:p*=pow(-1,(r-1)//2)
 return p
Sherlock9
quelle
4
Entschuldigung angenommen - Ich bin froh, dass jemand Pyth-Quellcode liest.
isaacg
2

Mathematica, 169 175 165 Bytes

(1|-1)~k~0=_~k~1=1
_~k~0=0
a_~k~-1=If[a<0,-1,1]
a_~k~2=DirichletCharacter[8,2,a]
a_~k~p_/;PrimeQ@p=Mod[a^((p-1)/2),p,-1]
a_~k~b_:=1##&@@(a~k~#^#2&@@@FactorInteger@b)
Alephalpha
quelle
2

LabVIEW, 44 Bytes LabVIEW-Grundelemente

Da es symmetrisch ist, habe ich die Eingänge getauscht, wenn a größer als b war.

Repräsentiert jetzt die reale Formel

zählen wie immer nach

für den wahren Fall

Eumel
quelle
Leider (a|b) != (b|a)in allen Fällen. In den meisten Fällen ja, aber nicht in allen. Obwohl es funktionieren würde, wenn Sie reduzieren, a mod banstatt sie zu tauschen.
Sherlock9
Da ich die Erklärung jetzt habe, kann ich sie bearbeiten, gib mir eine Minute
Eumel
1
Kann ich das auf irgendeine Weise testen? Ich verstehe nicht wirklich, wie LabView funktioniert.
Sherlock9
Das ist eine gute Frage, ich kann mir zwei Möglichkeiten vorstellen. Erstens kann ich eine EXE-Datei erstellen und an Sie senden, zweitens können Sie eine Labview-Testversion erhalten und ich kann Ihnen die vi senden oder Sie können sie vom Bild aus neu erstellen.
Eumel
7
Dies sind keine 44 Bytes. Wenn Sie ein Bewertungssystem definieren, das nicht auf der Größe der Datei basiert, sollten Sie es anders als Bytes nennen.
Feersum
1

Julia, 195 Bytes

k(a,b)=b==0?a∈[1,-1]?1:0:b==1?1:b==2?iseven(a)?0:a%8∈[1,-1]?1:-1:b==-1?a<1?-1:1:isprime(b)&&b>2?a%b==0?0:a∈[i^2%b for i=0:b-1]?1:-1:k(a,sign(b))*prod(i->k(a,i)^factor(b)[i],keys(factor(b)))

Dies ist eine rekursive Funktion k, die zwei Ganzzahlen akzeptiert und eine Ganzzahl zurückgibt.

Ungolfed:

function k(a::Integer, b::Integer)
    if b == 0
        return a  [1, -1] ? 1 : 0
    elseif b == 1
        return 1
    elseif b == 2
        return iseven(a) ? 0 : a % 8  [1, -1] ? 1 : -1
    elseif b == -1
        return a < 1 ? -1 : 1
    elseif isprime(b) && b > 2
        return a % b == 0 ? 0 : a  [i^2 % b for i = 1:b-1] ? 1 : -1
    else
        p = factor(b)
        return k(a, sign(b)) * prod(i -> k(a, i)^p[i], keys(p))
    end
end
Alex A.
quelle
1

Haskell, 286 Bytes

a#0|abs a==1=1|1<2=0
a#1=1
a#2|even a=0|mod a 8`elem`[1,7]=1|1<2=(-1)
a#b|b<0=a`div`abs a*a#(-b)|all((/=0).mod b)[2..b-1]=if elem n[0,1] then n else(-1)|1<2=product$map(a#)$f b where n=a^(div(b-1)2)`mod`b
f 1=[]
f n|n<0=(-1):f(-n)|1<2=let p=head$filter((==0).mod n)[2..n]in p:f(div n p)

Wahrscheinlich nicht vollständig optimiert, aber eine tapfere Anstrengung. Das Kronecker-Symbol ist definiert als die Infix-Funktion a # b, dh

*Main>323#455265 
1
Killmous
quelle