Perkiraan Konstan Brun

25

Konstanta Brun adalah nilai di mana jumlah kebalikan dari pasangan prima kembar ( 1/pdan di 1/(p+2)mana pdan p+2keduanya prima) bertemu. Itu kira-kira 1.902160583104.

Diberikan bilangan bulat positif N, perkiraan konstanta Brun dengan menjumlahkan kebalikan dari pasangan utama kembar di mana kedua bilangan prima dalam pasangan kurang dari N, dan menghasilkan perkiraan.

Aturan

  • N akan menjadi bilangan bulat positif dalam rentang yang dapat direpresentasikan untuk bahasa Anda.
  • Outputnya harus seakurat mungkin dengan nilai sebenarnya, dalam batas-batas implementasi floating-point bahasa Anda, mengabaikan segala masalah potensial karena ketidakakuratan aritmatika floating-point. Jika bahasa Anda mampu aritmatika presisi sewenang-wenang, bahasa itu harus setidaknya setepat aritmetika presisi ganda IEEE 754.
  • Atau, fraksi yang tepat dapat dihasilkan dalam format yang konsisten dan tidak ambigu.
  • Jika perdana muncul dalam beberapa pasangan kembar utama (mis. 5, Bagian dari keduanya (3, 5)dan (5, 7)), timbal baliknya berkontribusi pada jumlah setiap waktu.

Uji Kasus

2 -> 0
6 -> 0.5333333333333333
10 -> 0.8761904761904762
13 -> 0.8761904761904762
100 -> 1.3309903657190867
620 -> 1.4999706034568274
100000 -> 1.67279958482774
Mego
sumber
Bisakah pecahan yang tepat menjadi output?
LegionMammal978
@ LegionMammal978 Ya, saya akan mengklarifikasi.
Mego
Catatan: nilai 1,902160583104 ... untuk konstanta Brun hanya dugaan; bahkan angka signifikan pertama belum dihitung dengan teliti (yaitu, bahkan tidak diketahui apakah itu lebih besar atau kurang dari 2).
Greg Martin
@GregMartin Sementara itu benar, itu juga perkiraan terbaik yang kami miliki saat ini.
Mego
5 adalah satu-satunya prime yang muncul dalam dua pasangan utama
Christian Sievers

Jawaban:

25

Python 3 , 78 77 75 70 68 62 byte

f=lambda n,k=3,m=1,j=0:k<n and-m%k*j*2/k+f(n,k+2,m*k**4,m%k/k)

Terima kasih kepada @xnor karena bermain golf 2 4 byte dan membuka jalan untuk 4 lainnya!

Cobalah online!

Latar Belakang

Ingat bahwa teorema Wilson menyatakan bahwa untuk semua bilangan bulat k> 1 ,

di mana a ≡ b (mod d) berarti bahwa a - b dapat dibagi habis oleh d , yaitu a dan b memiliki residu yang sama ketika dibagi dengan d .

Dalam Wilson Theorems for Double, Hyper-, Sub-, dan Super-factorials , penulis membuktikan generalisasi untuk faktorial ganda, yang menjadi dasar jawaban ini. Faktor ganda bilangan bulat k ≥ 0 didefinisikan oleh

Teorema 4 dari makalah tersebut menyatakan sebagai berikut.

Mengangkat kedua sisi kongruensi ke kekuatan keempat, kami menyimpulkan itu

untuk semua bilangan prima ganjil p . Sejak 1 !! = 1 , persamaan juga berlaku untuk p = 2 .

Sekarang, melakukan hal yang sama pada teorema Wilson mengungkapkan hal itu

Sejak

mengikuti itu

setiap kali p adalah prima.

Sekarang, biarkan k menjadi bilangan bulat yang aneh, positif, dan komposit. Menurut definisi, ada bilangan bulat a, b> 1 sehingga k = ab .

Karena k aneh, begitu juga a dan b . Dengan demikian, keduanya terjadi pada urutan 1, 3,…, k - 2 dan

dimana | menunjukkan keterbagian.

Ringkasnya, untuk semua bilangan bulat ganjil k> 1

di mana p (k) = 1 jika k adalah prime dan p (k) = 0 jika k adalah komposit.

Bagaimana itu bekerja

Ketika fungsi f dipanggil dengan argumen tunggal, k , m , dan j diinisialisasi sebagai 3 , 1 , dan 0 .

Perhatikan bahwa ((k - 2) !!) 4 = 1 !! 4 = 1 = m . Bahkan, kesetaraan m = ((k - 2) !!) 4 akan berlaku setiap saat. j adalah pelampung dan akan selalu sama dengan ((k - 4) !!) 4 % (k - 2) / (k - 2) .

Sementara k <n , argumen yang benar andakan dievaluasi. Karena j = ((k - 4) !!) 4 % (k - 2) / (k - 2) , sebagaimana dibuktikan pada paragraf pertama, j = 1 / (k - 2) jika k - 2 adalah prima dan j = 0 jika tidak. Demikian juga, karena m% k = ((k - 2) !!) 4 sama dengan 1 jika k adalah prima dan 0 jika tidak, -m% k = k - 1 jika k adalah prime dan -m% k = 0 jika tidak. Karenanya, -m%k*j*2/kdievaluasi menjadi 2 (k - 1) / (k (k - 2)) = ((k - 2) + k) / (k (k - 2)) = 1 / k + 1 / (k - 2) jika pasangan (k - 2, k)terdiri dari bilangan prima kembar dan 0 jika tidak.

Setelah menghitung di atas, kami menambahkan hasilnya ke nilai kembali panggilan rekursif f(n,k+2,m*k**4,m%k/k). k bertambah 2 sehingga hanya membutuhkan nilai ganjil ‡ † , kita mengalikan m dengan k 4 karena mk 4 = ((k - 2) !!) 4 k 4 = (k !!) 4 , dan meneruskan nilai saat ini dari m% k / k - yang sama dengan 1 / k jika "lama" k adalah bilangan prima dan 0 jika tidak - sebagai parameter j ke pemanggilan fungsi.

Akhirnya, begitu k sama dengan atau lebih besar dari n , f akan mengembalikan False dan rekursi berhenti. Nilai pengembalian f (n) akan menjadi jumlah dari semua 1 / k + 1 / (k - 2) seperti (k - 2, k) adalah pasangan kembar utama dan k <n , seperti yang diinginkan.


Hasil dari paragraf Latar Belakang hanya berlaku untuk bilangan bulat ganjil. Karena bahkan bilangan bulat tidak bisa menjadi bilangan prima kembar, kita dapat melewatkannya dengan aman.

Dennis
sumber
Saya pikir ekspresimu sama dengan m%k*(j/k+j/(k-2)).
xnor
Ya, itu berhasil. Terima kasih!
Dennis
Hemat lain
xnor
Pengamatan bagus yang ((k-2)!!)^4 = p(k)modulo puntuk aneh p. Saya belum membahas argumen Anda, tapi inilah yang saya kemukakan (mungkin intinya sama). Bekerja modulo pdi set {1,2,..,p-1}, GENAP sebenarnya adalah negatif dari peluang. Jadi, prod(odds) = ± prod(evens). Teorema Wilson memberitahu kita tentang hal itu prod(all) = - p(k). Sejak prod(all) = prod(odds) * prod(evens) = prod(odds) * ± prod(evens), kita punya prod(odds)^2 = ±p(k)dan sebagainya prod(odds)^4 = p(k)^2 = p(k).
xnor
Bagus! Saya mencoba menyatakan jumlah itu sebagai pecahan tunggal, tetapi menghitung sebagiannya dalam j tidak terpikir oleh saya. Terima kasih lagi! Bukti Anda jauh lebih sederhana daripada yang ada di koran.
Dennis
7

Jelly , 15 14 byte

’ÆRµ_2fµ+2;µİS

Cobalah online!

Bagaimana itu bekerja

’ÆRµ_2fµ+2;µİS  Main link. Argument: n

’               Decrement; yield n-1.
 ÆR             Prime range; yield all primes in [1, ..., n-1].
   µ            New chain. Argument: r (prime range)
    _2          Subtract 2 from all primes.
      f         Filter; keep all p-2 that appear in r.
       µ        New chain. Argument: t (filtered range)
        +2      Add 2 to all primes in s.
          ;     Concatenate with s.
           µ    New chain. Argument: t (twin primes)
            İ   Take the inverses.
             S  Sum.
Dennis
sumber
5

Jelly , 16 14 byte (dengan sedikit bantuan dari @Dennis)

’ÆRṡ2_/2+$$ÐḟFİS

Cobalah online!

Ketika mencoba meningkatkan jawaban saya sebelumnya, saya memikirkan algoritma yang sama sekali berbeda, dan itu datang agak lebih pendek. Saya menggunakan pos berbeda untuk itu, seperti standar di sini untuk jawaban yang menggunakan teknik berbeda.

Dennis menyarankan untuk mengganti _/2+$$Ðḟdengan Iċ¥Ðf2; Saya benar-benar lupa tentang kemungkinan filter diad. Dengan demikian, algoritma ini sekarang terkait dengan yang digunakan Dennis.

Penjelasan

’ÆRṡ2Iċ¥Ðf2FİS
’                  Decrement.
 ÆR                Primes from 2 to the argument inclusive
                   (i.e. 2 to the original input exclusive).
   ṡ2              Take overlapping slices of size 2.
        Ðf         Keep only elements where the following is true:
       ¥           {the second parse of, which parses like this}
     Iċ   2          the differences (I) contain (ċ) 2
           F       Flatten.
            İ      Take 1/x {for every list element}.
             S     Sum.

sumber
2_/2+$$Ðḟbisa menjadi Iċ¥Ðf2.
Dennis
4

Brachylog , 17 byte

{>I-₂:I{ṗ/₁}ᵐ}ᶠc+

Cobalah online!

Ini adalah versi baru dari Brachylog, dengan halaman kode yang mengkilap!

Penjelasan

{            }ᶠ        Find all valid outputs of the predicate in brackets
               c+      Output is the sum of that list after flattening it

 >I                    Input > I
   -₂:I                The list [I-2, I]
       {   }ᵐ          Map:
        ṗ/₁              Must be prime and the output is its inverse
Fatalisasi
sumber
3

MATL , 16 byte

liqZqtd2=)t2+h/s

Cobalah online!

Pertimbangkan input 13sebagai contoh.

l     % Push 1
      %   STACK: 1
i     % Input N
      %   STACK: 1, 13
q     % Subtract 1
      %   STACK: 1, 12
Zq    % Primes up to that
      %   STACK: 1, [2 3 5 7 11]
t     % Duplicate
      %   STACK: 1, [2 3 5 7 11], [2 3 5 7 11]
d     % Consecutive differences
      %   STACK: 1, [2 3 5 7 11], [1 2 2 4]
2=    % Compare with 2, element-wise
      %   STACK: 1, [2 3 5 7 11], [0 1 1 0]
)     % Use as logical index to select elements from array
      %   STACK: 1, [3 5]
t     % Duplicate
      %   STACK: 1, [3 5], [3 5]
2+    % Add 2, element-wise
      %   STACK: 1, [3 5], [5 7]
h     % Concatenate horizontally
      %   STACK: 1, [3 5 5 7]
/     % Divide, element-wise
      %   STACK: [0.3333 0.2 0.2 0.1429]
s     % Sum of array. Implicitly display
      %   STACK: 0.8762
Luis Mendo
sumber
2

Mathematica, 48 47 byte

Terima kasih kepada JungHwan Min karena menghemat 1 byte!

If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&

Fungsi tanpa nama mengambil integer positif sebagai input dan mengembalikan pecahan yang tepat; misalnya, If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&[10]pengembalian 92/105.

If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]menguji apakah keduanya idan i-2prima, mengembalikan jumlah timbal balik mereka jika demikian dan 0jika tidak. ~Sum~{i,#-1}&lalu kembalikan jumlah kontribusi tersebut untuk semua nilai ikurang dari input.

Pengajuan sebelumnya:

If[And@@PrimeQ@{i,g=i-2},1/i+1/g,0]~Sum~{i,#-1}&
Greg Martin
sumber
Nah, itu seram sekali. Saya menyerah. ⚐
LegionMammal978
Saya bertanya-tanya apakah "fraksi tepat" berarti Mathematica :)
Greg Martin
-1 byte:If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&
JungHwan Min
Seseorang bisa mendapatkan angka presisi arbitrer dengan menambahkan dua byte N@, di depan kode.
JungHwan Min
Kondisi golf yang bagus! Memang benar bahwa Nmengembalikan perkiraan desimal ke bilangan real; Namun, itu membutuhkan byte tambahan untuk menampilkan lebih dari 6 sig ara atau lebih, dan tidak peduli berapa banyak ara sig yang ditampilkan, masih kurang akurat daripada fraksi itu sendiri.
Greg Martin
2

Oktaf, 45 byte

@(n)sum(all(isprime(m=[h=3:n-1;h-2]))*m'.^-1)

Penjelasan:

m=[h=3:n-1;h-2]             generate an concatenate two ranges 3:n-1 and 1:n-3
rec=m'.^-1                  transpose and reciprocal
idx=all(isprime(m))         create a logical [0 1 ..] array  if both ranges are prime set 1 else set 0
sum1 = idx * rec            matrix multiplication(extrat elements with logical index and sum along the first dimension)
sum(sum1)                   sum along the second dimension  

Cobalah secara Online!

rahnema1
sumber
2

JavaScript (ES6), 67 66 byte

Disimpan 1 byte berkat @Arnauld

f=n=>--n>1&&((p=x=>n%--x?p(x):x==1)(n)&&p(n-=2)&&1/n+++1/++n)+f(n)

Output falseuntuk test case 2, yang diizinkan secara default .

Cuplikan tes

Produksi ETH
sumber
Saya pikir 1/n+++1/++nmenghemat satu byte.
Arnauld
@Arnauld Terima kasih. Untuk beberapa alasan saya tidak tahu itu +++tidak selalu membuat kesalahan ...
ETHproduksi
2

05AB1E , 19 14 byte (-5 @Emigna)

<LDpÏÍDpÏDÌ«zO

Cobalah online!

Guci Gurita Ajaib
sumber
<LDpÏÍDpÏDÌ«zOuntuk menghemat 5 byte.
Emigna
1

Jelly , 19 byte

’ÆRḊµ_Æp=2Tịµ_2;µİS

Cobalah online!

Saya merasa ini tidak bisa diperbaiki, tetapi saya tidak bisa segera melihat caranya.

Penjelasan

’ÆRḊµ_Æp=2Tịµ_2;µİS
 ÆR                  Generate all primes from 2 to n inclusive
’                    Subtract 1
   Ḋ                 Remove first element
’ÆRḊ                 Generate all primes from 3 to n-1 exclusive

     _Æp             Subtract the previous prime (i.e. calculate the prime gap)
        =2           Compare to 2
          Tị         Take elements of the input where the comparison is true
     _Æp=2Tị         Filter a list of primes to the latter halves of prime pairs

             _2      Subtract 2
               ;     Append
             _2;     Append the list to the list with 2 subtracted from it
                 İ   Take reciprocals
                  S  Sum
                 İS  Take the sum of the reciprocals

The µconnect semua bagian-bagian bersama-sama pipa-gaya, dengan masing-masing mengambil output dari satu sebelum sebagai input.


sumber
1

Pyth - 22 21 17 byte

Saya pikir refactoring akan membantu.

scL1sf.APM_MTm,tt

Test Suite .

Maltysen
sumber
1

Perl 6 , 59 51 byte

{sum 1 «/»grep((*-(2&0)).is-prime,^$_).flatmap:{$_-2,$_}}

{sum 1 «/»grep(*.all.is-prime,(-2..*Z ^$_)).flat}

-2..* Z ^$_zip daftar tanpa batas -2, -1, 0, 1, ...dengan daftar 0, 1, ... $_-1( $_menjadi argumen untuk fungsi), menghasilkan daftar (-2, 0), (-1, 1), (0, 2), ..., ($_-3, $_-1). (Jelas tidak ada dari angka-angka ini yang kurang dari 3 yang dapat berpasangan prima, tetapi 3..* Z 5..^$_beberapa byte lebih panjang, dan tidak ada angka tambahan yang prima.)

The grepmenyeleksi hanya mereka pasang di mana semua (yaitu, keduanya) jumlahnya prima, dan flatmerata mereka ke dalam daftar polos nomor.

«/»adalah hyperoperator divisi; dengan daftar di sebelah kanan dan 1di sebelah kiri, itu mengubah daftar pasangan utama menjadi timbal balik mereka, yang kemudian disimpulkan oleh sum.

Sean
sumber
1

Clojure, 147 byte

(fn[n](let[p #(if(> % 2)(<(.indexOf(for[a(range 2 %)](mod % a))0)0))](reduce +(for[a(range 2 n)](if(and(p a)(p(- a 2)))(+(/ 1 a)(/ 1(- a 2)))0)))))

Dan Clojure mati terakhir, seperti biasa.

Tidak Disatukan:

; Returns the primality of a number.
(defn prime? [n]
  (if (> n 2)
    (< (.indexOf (for [a (range 2 n)] (mod n a)) 0) 0)))

; Calculates the actual Brun's Constant. ' (Stupid highlighter)
(defn brunsconst [n]
  ; Adds all of the entries together
  (reduce
    +
    ; For a in range(2, n):
    (for [a (range 2 n)]
      (let [b (- a 2)]
        ; If both a and a-2 are prime:
        (if (and (prime? a) (prime? b))
          ; Place (1/a + 1/a-2) on the array, else 0
          (+ (/ 1 a) (/ 1 b)) 0)))))
clismique
sumber
0

Julia 0.4 , 48 46 byte

!n=sum(1./[(p=n-1|>primes)∩(p-2);p∩(p+2)])

Cobalah online!

Dennis
sumber
0

Utilitas Bash + GNU, 86 85 byte

for((k=4;k<$1;k++,j=k-2)){ [ `factor $k $j|wc -w` = 4 ]&&x=$x+1/$k+1/$j;};bc -l<<<0$x

Cobalah online!

Buat ekspresi aritmatika yang besar dan kemudian masukkan bc -luntuk mengevaluasinya.

Sunting: Salah dalam pasangan $ (...) dari versi lama dengan substitusi perintah bersarang; diubah menjadi backticks untuk menyimpan byte.

Mitchell Spector
sumber
0

APL NARS, 216 byte, 108 karakter

  r←z n;h;i;k;v
  i←0⋄n-←1⋄h←1+⍳n-1⋄→B
A:k←i⊃h⋄h←k∪(0≠k∣h)/h
B:→A×⍳(⍴h)≥i+←1
  r←+/÷(v-2),v←(h=1⌽h+2)/h

ini akan menggunakan "Crivello di Eratostene" untuk menemukan sublist di 1..arg dari bilangan permintaan. Uji:

  z¨2 6 10 13 100 620
0 0.5333333333 0.8761904762 0.8761904762 1.330990366 1.499970603 
  z 100000
1.672799585
RosLuP
sumber