Berechnen Sie die p-adische Norm einer rationalen Zahl

Schreiben Sie eine Funktion oder ein Programm, das 3 Ganzzahlen m,n,p(wobei peine positive Primzahl ist) als Eingabe verwendet und die p-adische Norm (bezeichnet mit |m/n|_p) als (vollständig reduzierten) Bruch ausgibt . Es ist bekannt, dass Fermat nur sehr kleine Ränder hat, aber was eher unbekannt ist, ist, dass er nur einen sehr kleinen Computerbildschirm hatte. Versuchen Sie also, den Code so kurz wie möglich zu halten, damit er auf den Bildschirm von Fermat passt!

Definition

Bei einer gegebenen Primzahl pkann jeder Bruch m/neindeutig als (a/b)* p^esolcher geschrieben werden (wobei die Vorzeichen ignoriert werden) , der eeine ganze Zahl ist und pweder anoch teilt b. Die p-adische Norm von m/nist p^-e. Es gibt einen Sonderfall, wenn der Bruch 0 ist : |0|_p = 0.

Das Ausgabeformat muss sein x/y(z 1/3. B. für ganze Zahlen ist beides 10oder gleichwertig 10/1zulässig, für negative Zahlen muss ein führendes Minus vorhanden sein, z. B. -1/3)

Einzelheiten

Das Programm muss stdin / stdout verwenden oder nur aus einer Funktion bestehen, die die rationale Zahl oder Zeichenfolge zurückgibt. Sie müssen davon ausgehen, dass die Eingabe m/nnicht vollständig reduziert ist. Sie können davon ausgehen, dass dies peine Primzahl ist. Das Programm muss Ganzzahlen zwischen -2^28bis zu 2^2810 Sekunden verarbeiten können und sollte nicht länger als 10 Sekunden dauern.

Eingebaute Faktorisierungs- und Prime-Checking-Funktionen sind nicht zulässig, ebenso wie eingebaute Basiskonversationen und eingebaute Funktionen, die die p-adische Bewertung oder Norm berechnen.

Beispiele (aus Wikipedia gestohlen ):

x = m/n = 63/550 = 2^-1 * 3^2 * 5^-2 * 7 * 11^-1
|x|_2 = 2
|x|_3 = 1/9
|x|_5 = 25
|x|_7 = 1/7
|x|_11 = 11
|x|_13 = 1

Interessante Trivia

(Nicht notwendig, um diese Herausforderung zu kennen / zu lesen, aber vielleicht schön als Motivation zu lesen.)

(Bitte korrigieren Sie mich, wenn ich die falschen Wörter verwende oder etwas anderes nicht stimmt. Ich bin es nicht gewohnt, auf Englisch darüber zu sprechen.)

Wenn Sie die rationalen Zahlen als Feld betrachten, induziert die p-adische Norm die p-adische Metrik d_p(a,b) = |a-b|_p. Dann können Sie füllen Sie dieses Feld im Hinblick auf diese Metrik, das bedeutet Sie ein neues Feld erstellen können , in der alle Cauchyfolgen zusammenlaufen, was eine nette topologische Eigenschaft ist zu haben. (Was zB die rationalen Zahlen nicht haben, aber die Realzahlen.) Diese p-adischen Zahlen werden, wie Sie vielleicht vermutet haben, häufig in der Zahlentheorie verwendet.

Ein weiteres interessantes Ergebnis ist der Satz von Ostrowski, der im Grunde besagt, dass jeder absolute Wert (wie unten definiert) für die rationalen Zahlen einer der folgenden drei ist:

• Das Triviale: |x|=0 iff x=0, |x|=1 otherwise
• Der Standard (echt): |x| = x if x>=0, |x| = -x if x<0
• Das p-adic (wie wir es definiert haben).

Ein absoluter Wert / eine Metrik ist nur die Verallgemeinerung dessen, was wir als Entfernung betrachten . Ein absoluter Wert |.|erfüllt folgende Bedingungen:

• |x| >= 0 and |x|=0 if x=0
• |xy| = |x| |y|
• |x+y| <= |x|+|y|

Beachten Sie, dass Sie Metriken leicht aus absoluten Werten erstellen können und umgekehrt: |x| := d(0,x)oder d(x,y) := |x-y|, sie sind also fast gleich, wenn Sie addieren / subtrahieren / multiplizieren können ( dh in integralen Domänen). Ohne diese Struktur können Sie natürlich eine Metrik für allgemeinere Mengen definieren.

Julia, 94 80 75 Bytes

f(m,n,p)=(k=gcd(m,n)
g(m)=m%p>0?g(m÷p)p:1
m!=0?print(g(n÷k),/,g(m÷k)):0)

Hinweis: Die Verwendung von Zeilenvorschüben anstelle von Semikolons zur besseren Lesbarkeit funktioniert in beiden Fällen genauso.

Dies ist ganz einfach: Die g(m,n)Funktion verwendet Rekursion und Rest ( %), um den p^nFaktor standardmäßig aus der Eingabe zu extrahieren und dann bei jedem Schritt der Rekursion mmit zu n=1multiplizieren p, sodass die Ausgabe erfolgt p^n. Der Code wendet dies auf n/gcd(m,n)und dann an m/gcd(m,n), um den entsprechenden Ausdruck zu erhalten. k=gcd(m,n)wird verwendet, um die gcd(m,n)doppelte Berechnung zu vermeiden und Zeichen zu speichern. m!=0ist ein Test, um den Fall zu behandeln, in dem x=0.

Der Ausgang ist von der Form N/1oder 1/Ngegebenenfalls , wo Nist p^e.

J, 35 34 Bytes

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:

Dies ist ein binäres Verb, das die Primzahl pals linkes Argument und das Array m nals rechtes Argument verwendet. Es druckt immer den Schrägstrich /und gibt 0/1if zurück m = 0. Verwenden Sie es so:

  f =: (,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:
  5 f 63 550
25/1

Erläuterung

Das x:schaltet erweiterte Präzision ein, da wir sehr große Zahlen verarbeiten. Der Rest des Codes funktioniert wie folgt:

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])
                        ^         Power: this gives the array p^n p^m
                         +.       Take element-wise GCD with
                           |.@]   the rotated array n m; this gives
                                  the largest powers of p that divide n and m
                      <.          Take element-wise minimum with
                     [            The array m n to handle the m=0 case correctly
              %+./                Divide this array by its GCD to get it to lowest terms
        &":/                      Convert both elements to strings
 ,'/'&,                           Insert the slash '/' between them

CJam, 42 Bytes

q~)\_:*g_sW<o@*28#f{{{_@\%}h;}:G~}_~Gf/'/*

Dies endet mit einem Fehler (nach dem Drucken von 0) für Eingabe 0. Versuchen Sie es online im CJam-Interpreter .

Stax , 32 Bytes

éE▌ΦΔΘao£╙)ΩuÅI~AAε3∞xC█&½╤%╩▌ïö

Führen Sie es aus und debuggen Sie es

Sollte es kürzer machen können. Die native Unterstützung für Fraktion durch Stax ist ziemlich ordentlich.

ASCII-Äquivalent:

hY{y:+y|aEGsG-ys|**}0?}0{^scxHY%Cy/sWd