Golf Hilbert Primes

18

Bilangan Hilbert didefinisikan sebagai bilangan bulat positif 4n + 1untuk formulir n >= 0. Beberapa angka Hilbert pertama adalah:

1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97

Urutan nomor Hilbert diberikan oleh urutan OEIS A016813 .

Sebuah urutan nomor yang terkait, bilangan prima Hilbert, didefinisikan sebagai nomor Hilbert H > 1yang tidak dapat dibagi oleh sejumlah Hilbert ksehingga 1 < k < H. Beberapa bilangan prima Hilbert pertama adalah:

5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197

Secara alami, OEIS juga memiliki urutan ini .

Diberikan bilangan bulat nsehingga 0 <= n <= 2^16sebagai input, output nutama Hilbert.

Ini adalah kode-golf , jadi aturan standar berlaku, dan kode terpendek dalam byte akan menang.

Papan peringkat

Cuplikan Stack di bagian bawah posting ini menghasilkan leaderboard dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

## Perl, 43 + 2 (-p flag) = 45 bytes

Anda juga dapat membuat nama bahasa menjadi tautan yang kemudian akan muncul di cuplikan:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Tampilkan cuplikan kode

code-golf math number sequence number-theory Mego
sumber
Saya pikir maksud Anda "tidak habis dibagi oleh" alih-alih "relatif prima dengan". 21 dan 9 berbagi faktor umum 3.
xnor

Jawaban:

3

Pyth, 21 byte

Lh*4bye.fqZf!%yZyT1hQ

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

Lh*4bye.fqZf!%yZyT1Q    implicit: Q = input number
L                       define a function y(b), which returns
 h*4b                      4*b + 1
                        this converts a index to its Hilbert number
       .f          hQ   find the first (Q+1) numbers Z >= 1, which satisfy:
           f      1        find the first number T >= 1, which satisfies:
            !%yZyT            y(Z) mod y(T) == 0
         qZ                test if the result is equal to Z 

                        this gives a list of indices of the first Q Hilbert Primes
      e                 take the last index
     y                  apply y and print
Jakube
sumber
11

Haskell, 46 byte

(foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..]!!)

Fungsi anonim.

Inti adalah foldr(\a b->a:[x|x<-b,mod x a>0])[][5,9..], yang iterate melalui perkembangan aritmatika 5,9,13,..., menghilangkan kelipatan masing-masing dari daftar di sebelah kanannya. Ini menghasilkan daftar bilangan prima Hilbert yang tak terbatas. Kemudian, !!ambil nelemen th.

Saya telah mencoba membuat (\a b->a:[x|x<-b,mod x a>0])pointfree tetapi tidak menemukan cara yang lebih pendek.

Tidak
sumber
3
Mengubahnya foldrmenjadi daftar pemahaman lain menghemat dua bye:([x|x<-[5,9..],all((>0).mod x)[5,9..x-1]]!!)
nimi
@nimi Solusi yang bagus. Anda harus memposting itu, ini metode yang berbeda. Saya sedih ini lebih pendek karena lebih langsung ke definisi dan pengulangan daftar kurang cantik.
xnor
4

CJam, 36 33 32 23 byte

5ri{_L+:L;{4+_Lf%0&}g}*

Cobalah online

Versi terbaru sebenarnya jauh lebih @ MartinBüttner daripada milik saya. Gagasan kunci dalam solusi yang disarankan adalah menggunakan dua loop bersarang untuk menemukan nilai ke-n yang memenuhi kondisi tersebut. Saya pikir saya menjadi pandai dengan hanya menggunakan satu loop dalam solusi asli saya, tetapi ternyata biaya tambahan logika lebih banyak daripada yang saya hemat dengan tidak menggunakan loop kedua.

Penjelasan

5       Push first Hilbert prime.
ri      Get input n and convert to integer.
{       Loop n times.
  _       Push a copy of current Hilbert prime.
  L       Push list of Hilbert primes found so far (L defaults to empty list).
  +       Prepend current Hilbert prime to list.
  :L      Store new list of Hilbert primes in variable L.
  ;       Pop list off stack.
  {       Start while loop for finding next Hilbert prime.
    4+      Add 4 to get next Hilbert number.
    _       Copy candidate Hilbert number.
    L       Push list of Hilbert primes found so far.
    f%      Element wise modulo of Hilbert number with smaller Hilbert primes.
    0&      Check for 0 in list of modulo values.
  }g      End while loop.
}*      End loop n times.
Reto Koradi
sumber
2

Minkolang 0,14 , 46 37 32 byte

Saya tidak menyadari bahwa gosub sama sekali tidak perlu ...> _>

n$z(xxi4*5+d(4-$d%)1=,z+$ziz-)N.

Coba di sini dan periksa semua test case di sini .

Penjelasan

n$z                                 Take number from input and store it in the register
   (                                Open while loop
    xx                              Dump the stack
      i4*5+                         Loop counter times 4 plus 5 (Hilbert number)
           d                        Duplicate
            (                       Open while loop
             4-                     Subtract 4
               $d                   Duplicate stack
                 %                  Modulo
                  )                 Exit while loop when top of stack is 0
                   1=,              0 if 1, 1 otherwise
                      z             Push register value
                       +            Add
                        $z          Pop and store in register
                          iz-       Subtract z from loop counter
                             )      Exit while loop when top of stack is 0
                              N.    Output as number and stop.

Register digunakan untuk menyimpan indeks target. Lingkaran while luar menghitung setiap nomor Hilbert dan melakukan pembukuan. Loop sementara dalam memeriksa setiap nomor Hilbert untuk primality. Jika bilangan Hilbert bukan bilangan Hilbert prima, maka target bertambah sehingga loop sementara di luar harus mengulang (setidaknya) sekali lagi, secara efektif melewatkan komposit Hilbert.

El'endia Starman
sumber
2

Mathematica, 65 byte

Select[4Range[4^9]+1,Divisors[#][[2;;-2]]~Mod~4~FreeQ~1&][[#+1]]&

Buat seluruh daftar dan pilih elemen dari itu.

LegionMammal978
sumber
1

Ruby, 60 byte

h=->i{n=[];x=5;n.any?{|r|x%r<1}?x+=4: n<<x until e=n[i-1];e}

Hanya memeriksa faktor prima Hilbert.

MegaTom
sumber
0

JavaScript (ES6), 73 byte

n=>{for(i=0,t=2;i<=n;)i+=!/^(.(....)+)\1+$/.test(Array(t+=4));return t-1}

Cukup periksa nomor Hilbert satu per satu sampai kita mencapai prime Hilbert ke-n. Dapat dibagi oleh nomor Hilbert ditangani oleh regex.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
sumber
0

Matlab, 74 83 byte

function t=H(n)
x=5;t=x;while nnz(x)<n
t=t+4;x=[x t(1:+all(mod(t,x)))];end

Terima kasih kepada Tom Carpenter karena menghapus 9 byte!

Contoh penggunaan:

>> H(20)
ans =
   101
Luis Mendo
sumber
@TomCarpenter Terima kasih! Sekarang jawaban ini lebih milikmu daripada milikku :-)
Luis Mendo
Sama-sama :). Itu masih logika Anda, hanya menerapkan beberapa trik yang saya pelajari di sepanjang jalan.
Tom Carpenter
0

Julia, 73 byte

n->(a=[x=5];while length(a)<n;x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x)

Terima kasih Alex A. untuk menghemat 11 byte! Ini menggunakan algoritma yang sama dengan jawaban Matlab dan Ruby. Karena array Julia diindeks satu, ini dimulai dengan f(1) == 5.

Upaya pertama saya, menggunakan paket Malas, adalah 106 byte . Jika Anda berencana untuk menjalankan ini di REPL, pastikan untuk menambahkan titik koma ke ujung garis untuk menekan output yang tak terbatas. Dan hubungi Pkg.Add("Lazy")jika Anda belum menginstalnya.

using Lazy
r=range
h=r(1,Inf,4)
p=@>>r() filter(n->n!=1&&all(map(x->mod(h[n],h[x])<1,2:n-1)))
f=n->h[p[n]]
Andrew berkata Reinstate Monica
sumber
1
73 byte:n->(a=[x=5];while length(a)<n x+=4;all(k->mod(x,k)>0,a)&&push!(a,x)end;x)
Alex A.
1
Anda dapat menyimpan lebih banyak dengan menggunakan endofbukan lengthdan x%kbukan mod(x,k).
Alex A.