Konstanta Brun adalah nilai di mana jumlah kebalikan dari pasangan prima kembar ( 1/p
dan di 1/(p+2)
mana p
dan p+2
keduanya 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
Jawaban:
Python 3 ,
787775706862 byteTerima kasih kepada @xnor karena bermain golf
24 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
and
akan 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/k
dievaluasi 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.
sumber
m%k*(j/k+j/(k-2))
.((k-2)!!)^4 = p(k)
modulop
untuk anehp
. Saya belum membahas argumen Anda, tapi inilah yang saya kemukakan (mungkin intinya sama). Bekerja modulop
di set{1,2,..,p-1}
, GENAP sebenarnya adalah negatif dari peluang. Jadi,prod(odds) = ± prod(evens)
. Teorema Wilson memberitahu kita tentang hal ituprod(all) = - p(k)
. Sejakprod(all) = prod(odds) * prod(evens) = prod(odds) * ± prod(evens)
, kita punyaprod(odds)^2 = ±p(k)
dan sebagainyaprod(odds)^4 = p(k)^2 = p(k)
.Jelly ,
1514 byteCobalah online!
Bagaimana itu bekerja
sumber
Jelly ,
1614 byte (dengan sedikit bantuan dari @Dennis)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+$$Ðḟ
denganIċ¥Ðf2
; Saya benar-benar lupa tentang kemungkinan filter diad. Dengan demikian, algoritma ini sekarang terkait dengan yang digunakan Dennis.Penjelasan
sumber
2_/2+$$Ðḟ
bisa menjadiIċ¥Ðf2
.Brachylog , 17 byte
Cobalah online!
Ini adalah versi baru dari Brachylog, dengan halaman kode yang mengkilap!
Penjelasan
sumber
MATL , 16 byte
Cobalah online!
Pertimbangkan input
13
sebagai contoh.sumber
Mathematica,
4847 byteTerima kasih kepada JungHwan Min karena menghemat 1 byte!
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]
pengembalian92/105
.If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]
menguji apakah keduanyai
dani-2
prima, mengembalikan jumlah timbal balik mereka jika demikian dan0
jika tidak.~Sum~{i,#-1}&
lalu kembalikan jumlah kontribusi tersebut untuk semua nilaii
kurang dari input.Pengajuan sebelumnya:
sumber
If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&
N@
, di depan kode.N
mengembalikan 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.Oktaf, 45 byte
Penjelasan:
Cobalah secara Online!
sumber
JavaScript (ES6),
6766 byteDisimpan 1 byte berkat @Arnauld
Output
false
untuk test case2
, yang diizinkan secara default .Cuplikan tes
Tampilkan cuplikan kode
sumber
1/n+++1/++n
menghemat satu byte.+++
tidak selalu membuat kesalahan ...05AB1E ,
1914 byte (-5 @Emigna)Cobalah online!
sumber
<LDpÏÍDpÏDÌ«zO
untuk menghemat 5 byte.Jelly , 19 byte
Cobalah online!
Saya merasa ini tidak bisa diperbaiki, tetapi saya tidak bisa segera melihat caranya.
Penjelasan
The
µ
connect semua bagian-bagian bersama-sama pipa-gaya, dengan masing-masing mengambil output dari satu sebelum sebagai input.sumber
Pyth -
222117 byteSaya pikir refactoring akan membantu.
Test Suite .
sumber
Perl 6 ,
5951 byte{sum 1 «/»grep((*-(2&0)).is-prime,^$_).flatmap:{$_-2,$_}}
-2..* Z ^$_
zip daftar tanpa batas-2, -1, 0, 1, ...
dengan daftar0, 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, tetapi3..* Z 5..^$_
beberapa byte lebih panjang, dan tidak ada angka tambahan yang prima.)The
grep
menyeleksi hanya mereka pasang di mana semua (yaitu, keduanya) jumlahnya prima, danflat
merata mereka ke dalam daftar polos nomor.«/»
adalah hyperoperator divisi; dengan daftar di sebelah kanan dan1
di sebelah kiri, itu mengubah daftar pasangan utama menjadi timbal balik mereka, yang kemudian disimpulkan olehsum
.sumber
Clojure, 147 byte
Dan Clojure mati terakhir, seperti biasa.
Tidak Disatukan:
sumber
Julia 0.4 ,
4846 byteCobalah online!
sumber
Utilitas Bash + GNU,
8685 byteCobalah online!
Buat ekspresi aritmatika yang besar dan kemudian masukkan
bc -l
untuk mengevaluasinya.Sunting: Salah dalam pasangan $ (...) dari versi lama dengan substitusi perintah bersarang; diubah menjadi backticks untuk menyimpan byte.
sumber
APL NARS, 216 byte, 108 karakter
ini akan menggunakan "Crivello di Eratostene" untuk menemukan sublist di 1..arg dari bilangan permintaan. Uji:
sumber