Hitung norma p-adic dari bilangan rasional

Tulis fungsi atau program, yang mengambil 3 bilangan bulat m,n,p(di mana pbilangan prima positif) sebagai input, yang menampilkan norma p-adic (dilambangkan dengan |m/n|_p) sebagai fraksi (dikurangi sepenuhnya). Fermat diketahui hanya memiliki margin yang sangat kecil, tetapi yang agak tidak diketahui adalah bahwa ia hanya memiliki layar komputer yang sangat kecil. Jadi cobalah untuk membuat kode sesingkat mungkin agar muat di layar Fermat!

Definisi

Diberi bilangan prima p, setiap fraksi m/ndapat ditulis secara unik (mengabaikan tanda-tanda) dengan (a/b)* p^edemikian eadalah bilangan bulat dan ptidak membagi ajuga b. The norma p-adic dari m/nadalah p^-e. Ada kasus khusus, jika fraksi adalah 0: |0|_p = 0.

Format output harus x/y(misalnya 1/3; untuk bilangan bulat keduanya 10atau yang setara 10/1diizinkan, untuk bilangan negatif harus ada minus minus terkemuka -1/3)

Detail

Program harus menggunakan stdin / stdout, atau hanya terdiri dari fungsi yang mengembalikan bilangan rasional atau string. Anda harus berasumsi bahwa input m/ntidak sepenuhnya berkurang. Anda dapat berasumsi bahwa pitu prima. Program harus dapat memproses bilangan bulat antara -2^28hingga 2^28, dan tidak boleh lebih dari 10 detik.

Internalisasi faktorisasi dan fungsionalitas pemeriksaan prima tidak diperbolehkan, serta basis percakapan bawaan, dan fungsi internal yang menghitung penilaian atau norma p-adic.

Contoh (dicuri dari wikipedia ):

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

Hal- hal sepele yang menarik

(Tidak perlu tahu / membaca untuk tantangan ini, tetapi mungkin baik untuk dibaca sebagai motivasi.)

(Tolong koreksi saya jika saya menggunakan kata-kata yang salah, atau ada yang salah, saya tidak terbiasa membicarakan hal ini dalam bahasa Inggris.)

Jika Anda menganggap bilangan rasional sebagai bidang, maka norma p-adic menginduksi metrik p-adic d_p(a,b) = |a-b|_p. Kemudian Anda dapat menyelesaikan bidang ini terkait dengan metrik ini, itu berarti Anda dapat membangun bidang baru tempat semua urutan cauchy bertemu, yang merupakan properti topologi yang bagus untuk dimiliki. (Yang misalnya bilangan rasional tidak memiliki, tetapi real memiliki.) Bilangan p-adik ini seperti yang Anda duga, banyak digunakan dalam teori bilangan.

Hasil lain yang menarik adalah teorema Ostrowski yang pada dasarnya mengatakan, setiap nilai absolut (sebagaimana didefinisikan di bawah) pada bilangan rasional adalah salah satu dari tiga berikut:

• Sepele: |x|=0 iff x=0, |x|=1 otherwise
• Standar (nyata): |x| = x if x>=0, |x| = -x if x<0
• P-adic (seperti yang kita definisikan).

Nilai absolut / metrik hanyalah generalisasi dari apa yang kami anggap sebagai jarak . Nilai absolut |.|memenuhi persyaratan berikut:

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

Perhatikan bahwa Anda dapat dengan mudah membuat metrik dari nilai absolut dan sebaliknya: |x| := d(0,x)atau d(x,y) := |x-y|, sehingga hampir sama jika Anda dapat menambah / mengurangi / melipatgandakan (yang ada dalam domain integral). Anda tentu saja dapat mendefinisikan metrik pada set yang lebih umum, tanpa struktur ini.

Julia, 94 80 75 byte

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)

Catatan: menggunakan linefeeds sebagai pengganti titik koma untuk keterbacaan - akan bekerja dengan cara yang sama.

Ini cukup sederhana - g(m,n)fungsi menggunakan rekursi dan sisa ( %) untuk mengekstraksi p^nfaktor dari input m, dengan n=1sebagai default dan kemudian dikalikan dengan ppada setiap langkah rekursi, sehingga output akan menjadi p^n. Kode berlaku untuk n/gcd(m,n), dan kemudian m/gcd(m,n)untuk mendapatkan ekspresi yang sesuai. k=gcd(m,n)digunakan untuk menghindari penghitungan gcd(m,n)dua kali, untuk menyimpan karakter. m!=0adalah ujian untuk menangani kasus di mana x=0.

Output adalah dalam bentuk N/1atau 1/Nyang sesuai, di mana Nadalah p^e.

J, 35 34 byte

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

Ini adalah kata kerja biner yang menggunakan bilangan prima psebagai argumen kirinya, dan array m nsebagai argumen kanannya. Itu selalu mencetak garis miring /, dan mengembalikan 0/1jika m = 0. Gunakan seperti ini:

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

Penjelasan

The x:bergantian pada presisi diperpanjang, karena kita sedang menangani jumlah yang sangat besar. Sisa kode berfungsi sebagai berikut:

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

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

Ini selesai dengan kesalahan (setelah mencetak 0) untuk input 0. Cobalah online di interpreter CJam .

Stax , 32 byte

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

Jalankan dan debug itu

Seharusnya bisa membuatnya lebih pendek. Dukungan asli untuk fraksi oleh Stax cukup rapi.

Setara ASCII:

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