Catatan: tantangan ini telah diposting di kotak pasir .

pengantar

Tantangan ini terinspirasi oleh Putnam B1 2009 , masalah dalam kompetisi matematika sarjana. Masalahnya adalah sebagai berikut:

Tunjukkan bahwa setiap bilangan rasional positif dapat ditulis sebagai hasil bagi produk faktorial (tidak harus berbeda) bilangan prima. Sebagai contoh,

Tantangan

Tantangan Anda adalah mengambil sepasang bilangan bulat positif yang relatif prima, mewakili pembilang dan penyebut bilangan rasional positif (atau hanya bilangan rasional itu sendiri) sebagai input, dan menampilkan dua daftar (atau array, dll.) Dari bilangan prima sehingga bilangan rasional yang dimasukkan sama dengan rasio produk dari faktorial bilangan prima dalam daftar pertama dengan produk dari faktorial bilangan prima dalam daftar kedua.

Catatan

• Mungkin tidak ada bilangan prima yang terkandung di daftar pertama dan di daftar kedua; Namun, prime dapat muncul sebanyak yang diinginkan dalam daftar.
• Input dapat diasumsikan masing-masing menjadi (tidak ketat) antara 1 dan 65535; namun, tidak dapat diasumsikan bahwa faktorial dari angka-angka yang akan Anda butuhkan akan berada dalam kisaran ini.

Contoh Input dan Output

Berikut adalah contoh input dan output hukum.

input=>output
10,9 => [2,5],[3,3,3]
2,1 => [2],[]
3,1 => [3],[2]
1,5 => [2,3,2],[5]     (elements of a list may be in any order)
3,2 => [3],[2,2]
6,1 => [3],[]

Input (2,2), (0,3), (3,0), (3,6) dan (1,65536) adalah input ilegal (yaitu program Anda tidak perlu berperilaku dengan cara tertentu terhadap mereka ). Berikut adalah beberapa contoh hasil ilegal:

1,2 => [2],[2,2] (2 is in both returned lists)
5,2 => [5],[2,4] (4 is not prime)
2,1 => [2],[1] (1 is not prime either)
3,2 => [3],[2] (3!/2! = 3, not 3/2)

Mencetak gol

Ini adalah kode-golf , sehingga skor terendah dalam byte menang!

05AB1E , 54 53 48 46 40 35 33 32 28 byte

[D¿÷Z#DÓ€gZD<ØŠQ*DˆR!*]¯øεʒĀ

Cobalah online! Sunting: Disimpan 2 byte berkat hanya @ ASCII. Disimpan 1 2 3 4 byte berkat @Emigna. (Saya hanya perlu menyimpan satu lagi dan saya turun ke setengah dari jumlah byte asli saya!) Penjelasan:

[       Begin an infinite loop
D¿÷     Reduce to lowest terms
Z#      Exit the loop if the (largest) value is 1
DÓ€g    Find the index of the largest prime factor of each value
Z       Take the maximum
D<ØŠ    Convert index back to prime and save for later
Q       Convert to an pair of which value had the largest prime factor
*       Convert to an pair with that prime factor and zero
Dˆ      Save the pair in the global array for later
R!*     Multiply the other input value by the factorial of the prime
]       End of infinite loop
¯ø      Collect all the saved primes
εʒĀ     Forget all the saved 0s

Mathematica, 175 177 169 154 108 byte

Join@@@Table[x[[1]],{s,{1,-1}},{x,r@#},x[[2]]s]&@*(If[#==1,1,{p,e}=Last@(r=FactorInteger)@#;p^e#0[p!^-e#]]&)

Cobalah online!

Bagaimana itu bekerja

Ini adalah komposisi dari dua fungsi. Yang pertama, yang ungolfs untuk

If[# == 1,
  1,
  {p,e} = Last[FactorInteger[#]];
  p^e * #0[p!^-e * #]
]&

adalah fungsi rekursif untuk benar-benar menghitung faktorisasi yang diinginkan. Secara khusus, diberi input rasional x, kami menghitung bilangan prima yang faktorialnya harus dalam pembilang dan penyebut, dan mengembalikan fraksi dengan semua bilangan prima dikalikan bersama. (Misalnya, pada input 10/9 = 2!*5!/(3!*3!*3!), kami kembali 10/27 = 2*5/(3*3*3).)

Kami melakukan ini dengan berurusan dengan faktor prima terbesar di setiap langkah: jika p ^e terjadi di faktorisasi x, kami pastikan p! ^e terjadi dalam faktorisasi faktorial, dan berulang pada x dibagi dengan p! ^e .

(Sebelumnya, saya memiliki strategi yang lebih pintar yang menghindari angka besar dengan melihat bilangan prima sebelumnya sebelum p, tetapi Mathematica dapat menangani angka sebesar 65521! Dengan mudah, jadi tidak ada gunanya. Versi lama yang dapat Anda temukan dalam sejarah adalah jauh lebih cepat: di komputer saya, butuh input 0,05 detik yang ditangani versi ini dalam 1,6 detik.)

Fungsi kedua mengubah output dari fungsi pertama menjadi daftar bilangan prima.

Join @@@ 
  Table[x[[1]],
    {s,{1,-1}},
    {x,FactorInteger[#]},
    x[[2]]*s
  ]&

Untuk s=1(kekuatan positif) dan s=-1(kekuatan negatif), dan untuk setiap istilah {prime,exponent}dalam faktorisasi r@#, kami mengulangi bilangan prima prime exponent*sberkali-kali.

Versi tidak bersaing dengan 109 62 byte

If[#==1,∇1=1,{p,e}=Last@FactorInteger@#;(∇p)^e#0[p!^-e#]]&

Sama seperti di atas, tetapi alih-alih memberikan output sebagai daftar, berikan output sebagai ekspresi, menggunakan operator ∇ (karena tidak memiliki makna bawaan) sebagai pengganti faktorial. Dengan demikian, input 10/9memberikan output (∇2*∇5)/(∇3)^3untuk mewakili (2!*5!)/(3!)^3.

Ini lebih pendek karena kita melewatkan bagian kedua dari fungsi.

+2 byte: tugas f=Firstharus dilakukan di tempat yang tepat untuk menjaga agar Mathematica tidak marah.

-8 byte: memperbaiki bug untuk output integer, yang sebenarnya membuat kode lebih pendek.

-15 byte: FactorIntegermengembalikan output yang diurutkan, yang dapat kita manfaatkan.

-46 byte: kita sebenarnya tidak perlu pintar.

Python 2, 220 202 195 183 byte

g=lambda a,b:a and g(b%a,a)or b;n,d=input();m=c=()
while n+d>2:
 t=n*d;f=p=2
 while t>p:
	if t%p:p+=1;f*=p
	else:t/=p
 if n%p:c+=p,;n*=f
 else:m+=p,;d*=f
 t=g(n,d);n/=t;d/=t
print m,c

Cobalah online! Sunting: Disimpan 18 25 byte berkat @ Mr.Xcoder. Disimpan 12 byte berkat @JonathanFrech.