Apakah nomor saya Unik

21

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 mana Ssetiap ekspresi dengan nilai S mengevaluasi ke prime S th.

  • ABdi mana Adan Badalah 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.

Wisaya Gandum
sumber
Saya percaya bahwa faktor-faktor utama harus dipilah tetapi apa pun.
Nissa
1
@ Jonathan. Allan tidak, semua ada di sini.
Nissa
Kasing uji yang disarankan: 5381
Nissa
@StephenLeppik Test case ditambahkan, terima kasih.
Wheat Wizard
1
@ H.PWiz Saya akan mengatakan bahwa program lengkap dapat error sebagai output karena itu adalah bentuk output untuk suatu program, tetapi suatu fungsi harus mengembalikan nilai.
Wheat Wizard

Jawaban:

9

Sekam , 11 10 byte

Disimpan satu byte berkat Zgarb!

Ωεo?oṗ←¬Ep

Pengembalian 1untuk unik, 0jika tidak

Cobalah online! Atau mengembalikan 50 yang pertama

Penjelasan:

Ωε              Until the result is small (either 1 or 0), we repeat the following
         p     Get the prime factors
  o?           If ...
        E      they are all equal:
    ȯṗ←           Get the index of the first one into the primes
               Else:
       ¬          Not the list (since non-empty lists are truthy, this returns 0)
H.Piz
sumber
Oh, dan penjelasan Anda mengatakan " ȯp←".
Erik the Outgolfer
@EriktheOutgolfer Tangkapan bagus, diperbaiki
H.PWiz
Saya pikir ṁ¬bisa saja ¬karena daftar harus kosong di cabang itu.
Zgarb
@ Zgarb Oh mewah, saya pikir Anda memberi saya tip itu sebelumnya
H.PWiz
7

Jelly , 10 byte

Setelah BANYAK mengutak-atik!

ÆET0ṪḊ?µl¿

Tautan monadik mengambil bilangan bulat positif dan kembali 1jika unik atau 0jika tidak.

Cobalah online!

Bagaimana?

ÆET0ṪḊ?µl¿ - Link: number, n     e.g. 11          or 13            or 20
         ¿ - while:
        l  - ...condition: (left) logarithm with base (right)
           -               note: x log 0 and x log 1 both yield None, which is falsey
       µ   - ...do the monadic chain: (first pass shown)
ÆE         -   prime exponent array   [0,0,0,0,1]    [0,0,0,0,0,1]    [2,0,1]
  T        -   truthy indexes         [5]            [6]              [1,3]
      ?    -   if:
     Ḋ     -   ...condition: dequeue (i.e. if length > 1)
   0       -   ...then: literal zero   -              -               0
    Ṫ      -   ...else: tail           5              6               -
           - end result                1              0               0

Tunggu, logaritma, apa ?!

Mari kita jalankan melalui beberapa contoh loop.

Jika n=31( 31 1 , prime sebelas):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |       31 |        31 |    1.000 -> continue
         2 |       11 |        31 |    0.698 -> continue
         3 |        5 |        11 |    0.671 -> continue
         4 |        3 |         5 |    0.683 -> continue
         5 |        2 |         3 |    0.631 -> continue
         6 |        1 |         2 |    0.000 -> stop, yielding left = 1

Jika n=625( 5 4 ):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |      625 |       625 |    1.000 -> continue
         2 |        3 |       625 |    0.171 -> continue
         3 |        2 |         3 |    0.631 -> continue
         4 |        1 |         2 |    0.000 -> stop, yielding left = 1

Jika n=225( 5 2 × 3 2 ):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |      225 |       225 |    1.000 -> continue
         2 |     *  0 |       225 |-inf+nanj -> continue
         3 |     ** 0 |         0 |     None -> stop, yielding left = 0

*The dequeued list was not empty
**Tailing an empty list in Jelly yields 0
Jonathan Allan
sumber
4

APL (Dyalog) , 42 byte

CY'dfns'
{1≥⍵:11=≢∪r3pco⍵:∇11pcor0}

Menggunakan ⎕CY'dfns'dengan dfnses sangat tidak layak pada tio.

Uriel
sumber
Jawaban saya keluar sangat mirip dengan Anda, meskipun, saya memang menulis versi pertama sekitar 4 jam yang lalu
H.PWiz
@ H. PWiz lihat, saya tidak terlalu peduli ketika orang mengirimkan dalam bahasa yang sama meskipun saya biasanya lebih suka hanya berkomentar ketika saya menemukan solusi yang lebih pendek, tetapi ini hampir sama. Saya tidak keberatan Anda menyimpannya, tetapi saya menemukan jawaban yang terlihat sama tidak berguna. Tentang pengaturan waktu - begitulah cara kerjanya. Saya menjatuhkan lusinan jawaban karena ada orang lain yang lebih dulu. Saya (dan saya percaya sisanya) melakukannya untuk bersenang-senang, bukan kompetisi nyata.
Uriel
Maaf telah menghabiskan waktu lama untuk itu, tetapi saya telah menghapus jawaban saya. Menengok ke belakang, komentar sepertinya lebih cocok. Saya pikir, karena saya masih baru di APL pada saat itu, jawaban seperti itu membutuhkan upaya yang cukup signifikan, dan saya merasa komentar akan membuatnya terasa seperti sia
H.PWiz
2

Jelly , 11 byte

ÆfẋE$ḢÆCµl¿

Cobalah online!

-2 Berkat trik yang sangat jenius oleh Jonathan Allan .

Menggunakan algoritma Husk H.PWiz.

Erik the Outgolfer
sumber
Sejak login ke base satu dan nol keduanya menghasilkan Noneyang dapat Anda lakukan ÆfẋE$ḢÆCµl¿untuk 11 :)
Jonathan Allan
@ JonathanAllan Hei, itu yang pertama! Bagus.
Erik the Outgolfer