Menghasilkan bilangan prima Fermat

10

Diberi nomor n, cetak nomor Fermat prima ke-n , di mana angka-angka Fermat adalah dalam bentuk 2 2 k +1. Kode ini secara teoritis harus bekerja untuk n apa pun (yaitu jangan hardcode itu), meskipun tidak diharapkan untuk mengakhiri untuk n> 4. (Kode tidak boleh mengembalikan 4294967297 untuk n = 5, karena 4294967297 bukan bilangan prima.)

Harap perhatikan bahwa meskipun semua bilangan prima Fermat adalah dari bentuk 2 2 n +1, tidak semua angka dari bentuk 2 2 n +1 adalah prima. Tujuan dari tantangan ini adalah mengembalikan perdana ke-n .

Uji kasus

0 -> 3
1 -> 5
2 -> 17
3 -> 257
4 -> 65537

Aturan

  • Celah standar tidak diijinkan.
  • Pengindeksan dan pengindeksan keduanya dapat diterima.
  • Ini adalah , kemenangan byte-count terendah.

Terkait: Constructible n-gons

poi830
sumber
1
Apakah saya atau beberapa jawaban salah menafsirkan tantangan? Bukankah kita hanya menulis program yang menghasilkan 2^(2^n) + 1, di mana ninputnya? Ini sesuai dengan kasus pengujian Anda (yang kami tahu sudah prima, jadi tidak perlu memeriksa). Dan Anda tidak mengharapkan program bekerja di mana n> 4 (dan n = 5 adalah non-prime pertama).
jstnthms
Program ini secara teoritis harus berfungsi untuk n> 4, meskipun itu tidak akan pernah berhasil dalam praktik, karena kita hanya tahu 5 bilangan prima Fermat.
poi830
Saya tidak benar-benar mengerti tujuan bekerja secara teoritis untuk semua bilangan prima Fermat, karena hanya ada 5 istilah yang diketahui.
Tn. Xcoder
2
@CodyGray Testcases menyesatkan, karena ini berfungsi untuk n=1:4. Semua bilangan prima dari bentuk 2^2^n+1, tetapi itu tidak berarti bahwa semua bilangan bentuk 2^2^n+1sebenarnya prima. Ini adalah kasus untuk n=1:4, tetapi tidak n=5untuk contohnya.
JAD
3
Saya pikir beberapa bagian dari kebingungan adalah bahwa Anda mengatakan input ndan output harus dalam bentuk 2^(2^n)+1. Jika Anda menggunakan variabel yang berbeda untuk input dan eksponen maka beberapa kebingungan mungkin berkurang. Mungkin juga membantu jika Anda secara eksplisit menyatakan bahwa "n = 5 tidak perlu menghasilkan dalam waktu yang wajar, tetapi tidak boleh menghasilkan 4294967297"
Kamil Drakari

Jawaban:

3

Jelly , 13 11 byte

ÆẸ⁺‘©ÆPµ#ṛ®

Menggunakan pengindeksan berbasis 1.

Cobalah online!

Bagaimana itu bekerja

ÆẸ⁺‘©ÆPµ#ṛ®  Main link. No argument.

        #    Read an integer n from STDIN and call the chain to the left with
             arguments k = 0, 1, 2, ... until n matches were found.
ÆẸ           Find the integer with prime exponents [k], i.e., 2**k.
  ⁺          Repeat the previous link, yielding 2**2**k.
   ‘         Increment, yielding 2**2**k+1 and...
    ©        copy the result to the register.
     ÆP      Test the result for primality.
          ®  Yield the value from the register, i.e., the n-th Fermar prime.
         ṛ   Yield the result to the right.
Dennis
sumber
Oh, jadi orang menggunakan untuk menghapus hasilnya ... TIL
Leaky Nun
Oh, jadi gunakan satu ÆẸbukan 2*untuk bilangan bulat tunggal ... TIL
Erik the Outgolfer
2

Perl 6 ,  45  42 byte

{({1+[**] 2,2,$++}...*).grep(*.is-prime)[$_]}

Cobalah

{({1+2**2**$++}...*).grep(*.is-prime)[$_]}

Cobalah

Diperluas:

{  # bare block lambda with implicit parameter 「$_」

  (  # generate a sequence of the Fermat numbers

    {
      1 +
      2 ** 2 **
        $++            # value which increments each time this block is called
    }
    ...                # keep generating until:
    *                  # never stop

  ).grep(*.is-prime)\  # reject all of the non-primes
  [$_]                 # index into that sequence
}
Brad Gilbert b2gills
sumber
1

Mathematica, 56 byte

(t=n=0;While[t<=#,If[(PrimeQ[s=2^(2^n)+1]),t++];n++];s)&

Cobalah online!

J42161217
sumber
0

Pyth , 14 byte

Lh^2^2byfP_yTQ

Coba online.

Gagasan utama "meminjam" dari jawaban xnor dalam pertanyaan lain

Lh^2^2byfP_yTQ

L                    define a function with name y and variable b, which:
 h^2^2b                returns 1+2^2^b
       y             call the recently defined function with argument:
        f    Q         the first number T >= Q (the input) for which:
         P_yT            the same function with argument T returns a prime
                     and implicitly print
alleks
sumber
0

05AB1E , 8 byte

Kode:

Hasil diindeks 1.

µN<oo>Dp

Menggunakan penyandian 05AB1E . Cobalah online!

Penjelasan:

µ              # Run the following n succesful times..
 N             #   Push Nn
  oo           #   Compute 2 ** (2 ** n)
    >          #   Increment by one
     D         #   Duplicate
      p        #   Check if the number is prime
               # Implicit, output the duplicated number which is on the top of the stack
Adnan
sumber
0

Javascript, 12 46 byte

k=>eval('for(i=n=2**2**k+1;n%--i;);1==i&&n')

Sebagian besar kode diambil oleh pemeriksaan prima, yaitu dari sini .

SuperStormer
sumber
Perhatikan bahwa ia harus mengembalikan n prima nomor Fermat, bukan hanya jumlah Fermat n.
poi830
@ poi830 sekarang pemeriksaan prima memakan sebagian besar fungsi :(
SuperStormer
saya pikir Anda bisa mengatakan saya <2 bukannya saya == 1 karena nol juga baik di sini? yang seharusnya dikurangi menjadi 2 byte
DanielIndie
0

Dyalog APL (29 Karakter)

Saya hampir yakin ini bisa diperbaiki.

{2=+/0=(⍳|⊢)a←1+2*2*⍵:a⋄∇⍵+1}

Ini adalah fungsi rekursif yang memeriksa jumlah pembagi 1 + 2 ^ 2 ^ ⍵, di mana ⍵ adalah argumen yang tepat dari fungsi tersebut. Jika jumlah pembagi adalah 2, jumlahnya prima, dan mengembalikannya, jika tidak, ia memanggil fungsi lagi dengan ⍵ + 1 sebagai argumen yang benar.

Contoh

{2=+/0=(⍳|⊢)a←1+2*2*⍵:a ⋄ ∇ ⍵+1}¨⍳4
      5 17 257 65537

Di sini saya memanggil fungsi pada masing-masing ⍳4 (angka 1-4). Itu berlaku untuk setiap nomor pada gilirannya.

James Heslip
sumber
0

Haskell , 61 byte

p n=2^2^n;f=(!!)[p x+1|x<-[0..],all((>)2.gcd(p x+1))[2..p x]]

Cobalah online!

Indeks berbasis 0

Penjelasan

p n=2^2^n;                                          -- helper function 
                                                    -- that computes what it says
f=                                                  -- main function
  (!!)                                              -- partially evaluate 
                                                    -- index access operator
      [p x+1|                                       -- output x-th fermat number
             x<-[0..],                              -- try all fermat number indices
                      all                 [2..p x]  -- consider all numbers smaller F_x
                                                    -- if for all of them...
                         ((>)2                      -- 2 is larger than...
                              .gcd(p x+1))          -- the gcd of F_x 
                                                    -- and the lambda input 
                                                    -- then it is a Fermat prime!   
                                                  ]
SEJPM
sumber