Bangga Bertrand

24

Postulat Bertrand menyatakan bahwa untuk setiap bilangan bulat n ≥ 1 ada setidaknya satu prime p sehingga n <p ≤ 2n . Untuk memverifikasi teorema ini untuk n <4000 kita tidak perlu memeriksa 4000 kasus: Trik Landau mengatakan cukup untuk memeriksa bahwa

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 5003

semuanya prima. Karena masing-masing angka ini kurang dari dua kali pendahulunya, setiap interval {y: n <y ≤ 2n} mengandung setidaknya satu dari bilangan prima tersebut.

Urutan angka ini adalah Bertrand Primes (OEIS A006992) dan didefinisikan sebagai berikut:

a(1) = 2
a(n) = largest prime below 2a(n-1)

Tantangan

Terapkan urutan ini. Anda bisa menulis

  • sebuah fungsi atau program yang diberi beberapa pengembalian n a (n) (0 atau 1 diindeks),
  • fungsi atau program yang memberikan beberapa n mengembalikan entri pertama n (atau n-1 atau n + 1 ) dari urutan ini,
  • daftar atau aliran tanpa batas atau generator atau yang serupa di bahasa Anda.
cacat
sumber

Jawaban:

8

Oktaf , 32 byte

k=2
do k=primes(k+k)(end)until 0

Terus mencetak nilai tanpa batas (setiap nilai didahului oleh k =).

Cobalah online!


Oktaf , 42 byte

k=2
for i=2:input('')k=primes(k+k)(end)end

Dibawa n sebagai input dan output n nilai pertama (setiap nilai didahului oleh k =).

Cobalah online!


Oktaf , 51 byte

k=2;for i=2:input('')k=primes(k+k)(end);end
disp(k)

Mirip dengan jawaban MATL dari Luis Mendo . Mengambil n sebagai input dan output a (n) (1-diindeks).

Cobalah online!


Oktaf , 60 byte

k=2;for i=2:input('')k*=2;while~isprime(--k)
end
end
disp(k)

Mengambil n sebagai input dan output a (n) (1-diindeks).

Cobalah online!

Steadybox
sumber
7

J , 11 byte

_4&(p:+:)2:

Cobalah online!

Diindeks 0.

_4&(p:+:)2:  Input: integer n
         2:  Constant 2
_4&(    )    Repeat n times
      +:       Double
_4  p:         Find the largest prime less than the double
mil
sumber
6

05AB1E , 14 7 6 byte

$F·.ØØ

Cobalah online!


1-indexed answer (kecuali 0 seharusnya menghasilkan 1), penjelasan:

$       # Push 1 and input (n)...
 F      # n-times do... 
  ·     # Double the current prime (first iteration is 1*2=2).
   .ØØ  # Find prime slightly less than double the current prime.

Diindeks 1 karena semua iterasi memiliki iterasi 'dummy' n=1.

Guci Gurita Ajaib
sumber
Fx.ØØbegitu dekat ... Berfungsi untuk apa pun di atas n > 2.
Magic Octopus Urn
1
Saya memiliki $F·ÅPθuntuk jumlah byte yang sama.
Emigna
@Emigna punya? Itu seperti 0% haha ​​yang sama. Maksud saya, secara teknis sama, tetapi tidak. Masih bisa mempostingnya; P.
Magic Octopus Mm
5

Jelly , 6 byte

2ḤÆp$¡

Cobalah online!

Diindeks 0.

Penjelasan

2ḤÆp$¡  Main link. Input: n
2       Constant 2
    $¡  Repeat n times
 Ḥ        Double
  Æp      Find the largest prime less than the double
mil
sumber
menyodok Anda memerlukan byte lain sekarang;) ...
Magic Octopus Mm
@MagicOctopusUrn Input 0 mengembalikan 2, 1 mengembalikan 3, dan seterusnya. Saya tidak melihat masalah apa pun.
mil
Maksud saya Anda harus menyimpan satu byte pada jawaban ini untuk menang karena saya mengikat Anda pada 6-byte, jawaban Anda sendiri baik-baik saja.
Magic Gurita Guci
5

MATL , 9 byte

1i:"EZq0)

Input n , output a ( n ), 1-diindeks.

Cobalah online!

Penjelasan

1       % Push 1
i       % Push input n
:"      % Do the following that many times
  E     %   Multiply by 2
  Zq    %   Primes up to that
  0)    %   Get last entry
        % End (implicit). Display (implicit)
Luis Mendo
sumber
5

Stax , 10 byte

ü☼┌τ,æ▒ìn(

Jalankan test case

Masalah ini telah mengekspos bug dalam implementasi stax :p, yang merupakan instruksi yang mendapatkan prime terbesar lebih kecil dari inputnya. Jika bekerja dengan benar, akan ada solusi 5 6 byte. Tapi sayangnya, tidak, dan tidak ada. Sebagai pembuat bahasa, saya akan memperbaikinya, tetapi sepertinya murah untuk memperbaikinya dan menggunakannya setelah masalah diposting.

Bagaimanapun, ini adalah representasi ascii yang sesuai dari program di atas.

ODH{|p}{vgs

Ini adalah implementasi yang relatif lurus dari pernyataan masalah. Satu-satunya hal yang mungkin menarik tentang itu adalah penggunaan gsbentuk generator. Generator adalah keluarga konstruksi yang menggabungkan kondisi awal, transformasi, dan filter, untuk menghasilkan satu atau lebih nilai yang memuaskan. Dalam hal ini, ini digunakan sebagai pengganti :pinstruksi yang rusak .

O               Push integer 1 underneath the input number.
 D              Pop the input and repeat the rest of the program that many times.
  H             Double number.
   {|p}         Predicate block: is prime?
       {vgs     Decrement until the predicate is satisfied.
                Output is implicitly printed.

Sunting: inilah solusi 6 byte, tetapi membutuhkan perbaikan bug yang hanya diterapkan setelah tantangan ini diposting.

rekursif
sumber
Bahasa yang bagus! Saya telah menambahkannya ke daftar golf langs . Beri tahu saya jika Anda melihat sesuatu yang salah, atau ada hal lain yang ingin Anda tambahkan.
ETHproduk
@ ETHproductions: Bagus, terima kasih! Jika Anda tidak keberatan, bisakah Anda mengubah url juru bahasa menjadi staxlang.xyz Saya memutuskan untuk mendapatkan domain untuk itu.
rekursif
1
Wow, seluruh domain hanya untuk bahasa golf? Lucky esolang;) Diperbarui!
ETHproduk
@recursive WOW, $ 1,99 untuk setiap domain xyz? Saya ikut.
Magic Octopus Mm
4

Python 2 , 63 byte

r=m=k=P=2
while k:
 P*=k;k+=1
 if k>m:print r;m=r*2
 if P%k:r=k

Cobalah online!

Mencetak selamanya.

Menggunakan generator utama Teorema Wilson meskipun menghasilkan bilangan prima ke depan kikuk untuk masalah ini. Melacak prime terbesar saat ini yang terlihat rdan batas penggandaanm .

Dua byte disimpan dengan melakukan P*=kdaripada P*=k*kseperti biasanya, karena satu-satunya efek adalah untuk mengklaim bahwa 4 adalah prima, dan urutan penggandaan melewatkannya.

Tidak
sumber
4

CJam (15 byte)

2{2*{mp},W=}qi*

Demo online . Perhatikan bahwa ini diindeks 0.


Pendekatan yang lebih efisien adalah dengan mencari mundur, tetapi ini membutuhkan satu karakter lebih karena tidak dapat menggunakan implisit ,(kisaran):

2{2*,W%{mp}=}qi*
Peter Taylor
sumber
4

Japt , 16 14 13 12 byte

Dua solusi untuk harga satu, keduanya 1-diindeks.


Istilah ke-N

Akhirnya, sebuah tantangan saya bisa menulis solusi untuk digunakan F.g().

_ôZ fj Ì}g°U

Cobalah

                 :Implicit input of integer U
_       }g       :Starting with the array [0,1] take the last element (Z),
                 :pass it through the following function
                 :and push the returned value to the array
 ôZ              :  Range [Z,Z+Z]
    fj           :  Filter primes
       Ì         :  Get the last item
          °U     :Repeat that process U+1 times and return the last element in the array

Ketentuan N Pertama

ÆV=ôV fj ̪2

Cobalah

                 :Implicit input of integer U
                 :Also makes use of variable V, which defaults to 0
Æ                :Create range [0,U) and pass each through a function
  ôV             :  Range [V,V+V]
     fj          :  Filter primes
        Ì        :  Get the last item
         ª2      :  Logical OR with 2, because the above will return undefined on the first iteration
 V=              :  Assign the result of the above to V
Shaggy
sumber
3

Haskell , 58 byte

a 1=2
a n=last[p|p<-[2..2*a(n-1)],all((>0).mod p)[2..p-1]]

Cobalah online!

ბიმო
sumber
2

Python 2 , 68 byte

Mencetak urutan tanpa batas (Anda harus mengklik "Jalankan" kedua kalinya untuk menghentikan eksekusi).

k=2
while 1:
 print k;k+=k
 while any(k%u<1for u in range(2,k)):k-=1

Cobalah online!

Python 3 , 90 byte

Mengembalikan istilah ke- n .

f=lambda n,i=1,p=1:n*[0]and p%i*[i]+f(n-1,i+1,p*i*i) 
a=lambda n:n and f(2*a(n-1))[-1]or 1

Cobalah online!

Tuan Xcoder
sumber
2

C (gcc) , 97 87 86 80 79 byte

  • Disimpan sepuluh byte dengan menggarisbawahi fungsi pemeriksaan non-primality P ke dalam loop utama.
  • Menyimpan byte dengan memindahkan printf panggilan.
  • Disimpan enam byte dengan mengembalikan i entri urutan-ke-10 (diindeks 0) alih-alih menghasilkan aliran yang tidak pernah berakhir.
  • Disimpan satu byte berkat ceilingcat .
f(p,r,i,m,e){for(r=2;p--;)for(e=0,i=r+r;e=m=!e;r=i--)for(;i-++m;e=e&&i%m);p=r;}

Cobalah online!

Jonathan Frech
sumber
@ceilingcat Terima kasih.
Jonathan Frech
1

Attache , 38 byte

{If[_,Last[Series[Prime,2*$[_-1]]],2]}

Cobalah online!

Berbasis 0; mengembalikan nbilangan prima Bertrand.

Saat ini tidak ada builtin untuk menemukan bilangan prima sebelumnya / berikutnya, jadi saya menggunakan Series builtin untuk menghitung semua bilangan prima hingga 2*$[_-1]. Ungkapan terakhir ini menggunakan rekursi implisit (terikat $) untuk dengan mudah mendefinisikan relasi perulangan. Kondisi if digunakan untuk menentukan kondisi dasar.

Conor O'Brien
sumber
1

Perl 6 , 35 byte

2,{(2*$_,*-1...&is-prime).tail}...*

Cobalah online!

Ungkapan ini adalah daftar bilangan prima Bertrand yang tak terbatas.

Sean
sumber
1

Retina , 39 byte

.K`_
"$+"{`_
__
+`^(?=(..+)\1+$).

*\`_

Cobalah online! Penjelasan:

.K`_

Mulai dengan 1.

"$+"{`

Ulangi loop menggunakan input sebagai jumlah loop.

_
__

Gandakan nilainya.

+`^(?=(..+)\1+$).

Temukan prime tertinggi kurang dari nilainya.

*\`_

Cetak itu.

Neil
sumber
0

Ruby , 51 + 7 (-rprime) = 58 byte

->n{x=2
n.times{x=(x..2*x).select(&:prime?)[-1]}
x}

Cobalah online!

Lamba yang menerima ndan mengembalikan nthBertrand prime, diindeks 0. Tidak banyak di sini, tapi biar saya ungolf itu:

->n{
  x=2                       # With a starting value of 2
  n.times{                  # Repeat n times:
    x=(x..2*x)              # Take the range from x to its double
      .select(&:prime?)[-1] # Filter to only primes, and take the last
  }
  x                         # Return
}

Ruby , 48 + 7 = 55 byte

x=2
loop{puts x
x*=2
loop{(x-=1).prime?&&break}}

Cobalah online!

Untuk bersenang-senang, inilah solusi loop tak terbatas. Ini mencetak saat berjalan, dan membutuhkan interupsi. Bergantung pada kapan tepatnya Anda menyela, Anda mungkin atau mungkin tidak melihat hasilnya. Tidak Disatukan:

x=2
loop{
  puts x
  x*=2
  loop{
    (x-=1).prime? && break
  }
}
benj2240
sumber
0

APL (Dyalog Extended) , 12 byte

Mengambil input dari pengguna sebagai N, mengembalikan elemen N urutan (0-diindeks).

42×⍵}⍣⎕⊢2

Cobalah online!

Penjelasan:

42×⍵}⍣⎕⊢2  Full program
              Get input from user - call it 'N'
          2  Repeat the left function N times, beginning with 2
    2×⍵        Double the function input
 ¯4           Find the largest prime less than above
voidhawk
sumber
0

R , 87 byte

nOutput yang diberikana(n)

j=scan();n=2;while(j-1){for(i in (n+1):(2*n)){n=ifelse(any(i%%2:(i-1)<1),n,i)};j=j-1};n

Cobalah online!

Saya masih mengerjakan "Diberikan n keluaran a (1), a (2) ... a (n)". Saya pikir saya hanya bisa memodifikasi kode ini sedikit, tetapi tampaknya lebih sulit dari itu.

Sumner18
sumber