Dalam tantangan ini kami belajar cara untuk menyandikan setiap bilangan bulat positif menggunakan pohon faktor.
Inilah cara kerjanya:
String kosong memiliki nilai 1.
(S)
di manaS
setiap ekspresi dengan nilai S mengevaluasi ke prime S th.AB
di manaA
danB
adalah ekspresi arbirary dengan nilai-nilai A dan B masing-masing memiliki nilai A * B .
Sebagai contoh jika kita ingin mewakili 7, kita akan melakukannya
7 -> (4) -> (2*2) -> ((1)(1)) -> (()())
Ternyata kita bisa mewakili setiap bilangan bulat menggunakan metode ini. Bahkan beberapa angka dapat kami wakili dalam berbagai cara. Karena perkalian adalah komutatif 10 adalah keduanya
((()))()
dan
()((()))
Pada saat yang sama beberapa angka hanya dapat diwakili dalam 1 cara. Ambil 8 misalnya. 8 hanya dapat direpresentasikan sebagai
()()()
Dan karena semua atom kita sama, kita tidak dapat menggunakan komutivitas untuk mengaturnya kembali.
Jadi sekarang pertanyaannya adalah "Angka mana yang hanya bisa diwakili dalam 1 cara?". Pengamatan pertama adalah yang baru saja saya mulai di sana. Tampaknya kekuatan sempurna memiliki beberapa sifat khusus. Di bawah penyelidikan lebih lanjut kita dapat menemukan 36, yang 6 2 adalah kekuatan sempurna tetapi memiliki banyak representasi.
(())()(())()
(())()()(())
()(())()(())
()(())(())()
()()(())(())
Dan ini masuk akal karena 6 sudah diatur ulang, jadi angka apa pun yang kita buat dari 6 juga harus diatur ulang.
Jadi sekarang kita punya aturan:
- Angka memiliki representasi unik jika itu adalah kekuatan sempurna angka dengan representasi unik.
Aturan itu dapat membantu kita mengurangi penentuan apakah bilangan komposit unik untuk menentukan apakah bilangan prima unik. Sekarang kita memiliki aturan itu, kita ingin mencari tahu apa yang membuat bilangan prima unik. Ini sebenarnya cukup jelas. Jika kita mengambil angka unik dan membungkusnya dengan tanda kurung, hasilnya harus unik, dan, sebaliknya jika n memiliki banyak representasi, perdana ke- n harus memiliki banyak representasi. Ini menghasilkan aturan kedua:
- The n prima th unik jika dan hanya jika n adalah unik.
Kedua aturan ini bersifat rekursif, jadi kita akan membutuhkan kasus dasar. Berapa nomor unik terkecil? Orang mungkin tergoda untuk mengatakan 2 karena hanya ()
, tetapi 1, string kosong, bahkan lebih kecil dan unik.
- 1 unik.
Dengan tiga aturan ini kita dapat menentukan apakah angka memiliki pohon faktor unik.
Tugas
Anda mungkin telah melihatnya datang, tetapi tugas Anda adalah mengambil bilangan bulat positif, dan menentukan apakah itu unik. Anda harus menulis program atau fungsi yang melakukan perhitungan ini. Anda harus menampilkan salah satu dari dua nilai yang mungkin, apa nilai-nilai ini terserah Anda tetapi satu harus mewakili "ya", menjadi output ketika input unik dan satu harus mewakili "tidak" menjadi output sebaliknya.
Jawaban Anda harus dinilai dalam byte dengan lebih sedikit byte menjadi lebih baik.
Uji kasus
Berikut adalah nomor unik pasangan pertama:
1
2
3
4
5
7
8
9
11
16
17
19
23
25
27
31
Kasus uji yang disarankan
5381 -> Unique
Tampaknya OEIS A214577 entah bagaimana terkait, jadi jika Anda perlu lebih banyak uji coba coba di sana, tapi saya tidak tahu mereka sama, jadi gunakan dengan risiko Anda sendiri.
Jawaban:
Sekam ,
1110 byteDisimpan satu byte berkat Zgarb!
Pengembalian
1
untuk unik,0
jika tidakCobalah online! Atau mengembalikan 50 yang pertama
Penjelasan:
sumber
ȯp←
".ṁ¬
bisa saja¬
karena daftar harus kosong di cabang itu.Jelly , 10 byte
Setelah BANYAK mengutak-atik!
Tautan monadik mengambil bilangan bulat positif dan kembali
1
jika unik atau0
jika tidak.Cobalah online!
Bagaimana?
Tunggu, logaritma, apa ?!
Mari kita jalankan melalui beberapa contoh loop.
Jika
n=31
( 31 1 , prime sebelas):Jika
n=625
( 5 4 ):Jika
n=225
( 5 2 × 3 2 ):sumber
APL (Dyalog) , 42 byte
Menggunakan
⎕CY'dfns'
dengandfns
es sangat tidak layak pada tio.sumber
Jelly , 11 byte
Cobalah online!
-2 Berkat trik yang sangat jenius oleh Jonathan Allan .
Menggunakan algoritma Husk H.PWiz.
sumber
None
yang dapat Anda lakukanÆfẋE$ḢÆCµl¿
untuk 11 :)Pari / GP , 49 byte
Cobalah online!
sumber