Oblicz normę p-adyczną liczby wymiernej

Napisz funkcję lub program, który pobiera 3 liczby całkowite m,n,p(gdzie liczba pdodatnia jest liczbą pierwszą) jako dane wyjściowe, które generują normę p-adyczną (oznaczoną |m/n|_pjako) jako ułamek (całkowicie zredukowany). Fermat jest znany z bardzo małych marginesów, ale raczej nie wiadomo, że miał tylko bardzo mały ekran komputera. Dlatego staraj się, aby kod był jak najkrótszy, aby zmieścił się na ekranie Fermata!

Definicja

Biorąc pod uwagę pliczbę pierwszą , każdą część m/nmożna jednoznacznie zapisać (ignorując znaki) jako (a/b)* p^etaką, która ejest liczbą całkowitą i pnie dzieli ani aani b. Normą p adyczne na m/nto p^-e. Jest to szczególny przypadek, gdy frakcja jest 0: |0|_p = 0.

Format wyjściowy musi być x/y(np. 1/3Dla liczb całkowitych dozwolone są oba 10lub równoważnie 10/1, dla liczb ujemnych musi być wiodący minus np. -1/3)

Detale

Program musi używać stdin / stdout lub po prostu składać się z funkcji, która zwraca liczbę wymierną lub łańcuch. Musisz założyć, że dane wejściowe m/nnie są w pełni zmniejszone. Możesz założyć, że pjest to liczba pierwsza. Program musi być zdolny do przetwarzania liczb całkowitych od -2^28do 2^28, i nie powinien zająć więcej niż 10 sekund.

Wbudowane funkcje faktoryzacji i sprawdzania liczb pierwszych nie są dozwolone, podobnie jak wbudowane konwersacje bazowe i wbudowane funkcje, które obliczają wartość p-adyczną lub normę.

Przykłady (skradzione z wikipedii ):

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

Ciekawe ciekawostki

(Nie trzeba znać / czytać tego wyzwania, ale być może warto je czytać jako motywację).

(Proszę poprawić mnie, jeśli użyję niewłaściwych słów lub coś innego jest nie tak, nie jestem przyzwyczajony do mówienia o tym po angielsku.)

Jeśli weźmiesz pod uwagę liczby wymierne jako pole, wówczas norma p-adyczna indukuje metrykę p-adyczną d_p(a,b) = |a-b|_p. Następnie możesz wypełnić to pole w odniesieniu do tej metryki, co oznacza, że ​​możesz zbudować nowe pole, w którym zbiegają się wszystkie sekwencje cauchy, co jest przyjemną właściwością topologiczną. (Które np. Liczby wymierne nie mają, ale liczby rzeczywiste tak.) Te liczby p-adyczne są, jak można się domyślać, używane w teorii liczb.

Innym interesującym wynikiem jest twierdzenie Ostrowskiego, które w zasadzie mówi, że dowolna wartość bezwzględna (jak zdefiniowano poniżej) liczb wymiernych jest jedną z następujących trzech:

• Trywialne: |x|=0 iff x=0, |x|=1 otherwise
• Standard (rzeczywisty): |x| = x if x>=0, |x| = -x if x<0
• P-adic (jak to zdefiniowaliśmy).

Wartość bezwzględna / metryka jest po prostu uogólnieniem tego, co uważamy za odległość . Wartość bezwzględna |.|spełnia następujące warunki:

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

Zauważ, że możesz łatwo konstruować metryki z wartości bezwzględnych i odwrotnie: |x| := d(0,x)lub d(x,y) := |x-y|, więc są one prawie takie same, jeśli możesz dodać / odjąć / pomnożyć (to jest w domenach integralnych). Możesz oczywiście zdefiniować metrykę na bardziej ogólnych zestawach, bez tej struktury.

Julia, 94 80 75 bajtów

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)

Uwaga: użycie linii odniesienia zamiast średników dla zwiększenia czytelności - będzie działać tak samo.

Jest to dość proste - g(m,n)funkcja korzysta z rekurencji i reszty ( %) w celu wyodrębnienia p^nwspółczynnika z danych wejściowych m, przy n=1czym domyślnie, a następnie pomnożona przez pna każdym etapie rekurencji, tak aby wynik był p^n. Kod stosuje to do n/gcd(m,n), a następnie m/gcd(m,n)do uzyskania odpowiedniego wyrażenia. k=gcd(m,n)służy do unikania gcd(m,n)podwójnego obliczania , do zapisywania znaków. m!=0jest testem do obsługi przypadku, w którym x=0.

Dane wyjściowe mają postać N/1lub, 1/Nw stosownych przypadkach, gdzie Njest p^e.

J, 35 34 bajtów

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

Jest to czasownik binarny, który przyjmuje pliczbę pierwszą za swój lewy argument, a tablicę m nza swój prawy argument. Zawsze drukuje ukośnik /i zwraca 0/1if m = 0. Użyj tego w ten sposób:

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

Wyjaśnienie

W x:zakręty na rozszerzonej precyzji, ponieważ mamy do przenoszenia bardzo dużych ilościach. Reszta kodu działa w następujący sposób:

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])
                        ^         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 bajty

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

To kończy się błędem (po wydrukowaniu 0) dla wejścia 0. Wypróbuj go online w interprecie CJam .

Stax , 32 bajty

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

Uruchom i debuguj

Powinien być w stanie skrócić. Natywne wsparcie dla frakcji przez Staxa jest całkiem fajne.

Odpowiednik ASCII:

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