Ada sejumlah besar fungsi pembangkit prima. Hampir semua dari mereka dibangun dan didasarkan pada saringan Eratosthenes, fungsi Möbius atau teorema Wilson dan umumnya tidak layak untuk dihitung dalam praktek. Tetapi ada juga generator, yang memiliki struktur yang sangat mudah dan ditemukan secara tidak sengaja.
Pada tahun 2003 Stephen Wolfram menjelajahi kelas persamaan pengulangan bersarang dalam percobaan komputer langsung di NKS Summer School. Sekelompok orang di sekitar Matthew Frank menindaklanjuti dengan eksperimen tambahan dan menemukan properti menarik dari pengulangan itu
a(n) = a(n-1) + gcd(n,a(n-1))
dengan nilai awal a(1) = 7
. Perbedaannya a(n) - a(n-1) = gcd(n,a(n-1))
sepertinya selalu 1 atau prima. Beberapa perbedaan pertama adalah ( OEIS A132199 ):
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, ...
Jika kita hanya menghilangkan 1s kita mendapatkan urutan berikut ( OEIS A137613 ):
5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3,
941, 3, 7, 1889, 3, 3779, 3, 7559, 3, 13, 15131, 3, 53, 3, 7, 30323, 3, ...
Eric S. Rowland membuktikan keunggulan setiap elemen dalam daftar ini beberapa tahun kemudian. Seperti yang Anda lihat, bilangan prima dicampur dan beberapa dari mereka muncul beberapa kali. Juga telah terbukti, bahwa urutannya mencakup bilangan prima yang tak terhingga banyaknya. Selain itu diduga, bahwa semua bilangan prima aneh muncul.
Karena generator utama ini tidak dibangun tetapi hanya ditemukan secara tidak sengaja, generator utama disebut "terjadi secara alami". Tetapi perhatikan bahwa dalam praktiknya generator ini juga sangat tidak layak untuk dihitung. Ternyata, p prima hanya muncul setelah (p–3)/2
1s berturut-turut. Meskipun demikian menerapkan generator utama ini akan menjadi tugas Anda.
Tantangan:
Tulis fungsi atau program yang mencetak n
elemen pertama dari urutan A137613
(urutan tanpa 1s). Anda dapat membaca nomor input n >= 0
melalui STDIN, argumen baris perintah, prompt atau argumen fungsi. Keluarkan n
elemen pertama dalam format apa pun yang dapat dibaca menjadi STDOUT, atau kembalikan array atau daftar dengan nilai-nilai ini.
Ini adalah kode-golf. Karenanya kode terpendek menang.
Papan peringkat:
Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa. Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:
# Language Name, N bytes
di mana N adalah ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda bisa menyimpan skor lama di headline, dengan mencoretnya. Contohnya:
# Ruby, <s>104</s> <s>101</s> 96 bytes
var QUESTION_ID=55272;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>
a(n)-a(n-1)
n
nol?//
) dan menjelaskannya dalam kiriman Anda. Jika ada yang tidak setuju dengan Anda, Anda selalu dapat mengedit posting Anda.Jawaban:
Pyth,
1413 byteMenggunakan di
a(n) = Lpf(6 - n + sum(a(i) for i in range(1, n))
manaLpf
berarti faktor prima.Coba di sini online.
sumber
Python 3.5.0b1 +,
9593 byteTautan ke rilis Python 3.5.0b1 +
Implementasi langsung dari perulangan, menampilkan:
1%x
, danmath.gcd
, sebagai lawan darifractions.gcd
.sumber
1%x
harus dilakukan Pertanyaan sampingan: di mana saya menemukan dokumentasi riwayat revisi Python yang mencakup betas? Sunting: Nevermind, temukan di bagian bawah riwayat revisi .x >= 1
,1%x
mengembalikan 0 jikax == 1
, 1 jika tidak (digunakan untuk memutuskan apakah akan menambahx
daftar)Julia, 110 byte
Tidak Disatukan:
sumber
n<2
sebagai gantin==1
. Juga, jika Anda melihat ke depan, bukan ke belakang, Anda dapat menggunakani=1
danx=a(i)-a(i+=1)
, dan kemudianprintln(-x)
dan-x>1
untuk mengoreksi negativeness, sehingga menghindari kebutuhan untuk kenaikan terpisah darii
. Dan≥
tiga byte, sementara>=
dua ... tetapi kemudian, Anda dapat menggunakann<1||()
daripadan>=1&&()
... namun, itu bahkan tidak diperlukan di tempat pertama (jatuhkan kondisional, n tidak akan pernah kurang dari 1). Anda juga tidak memerlukan tanda kurung terluar saat mendefinisikan (n). Dengan perubahan ini, Anda setidaknya harus turun ke 97 byte.PHP,
1019699987772 bytePenggunaan:
Panggil Script dengan argumen:
php -d error_reporting=0 script.php 30
Jika Anda ingin mengujinya, Anda perlu batalkan komentar
;extension=php_gmp.dll
di php.ini->
extension=php_gmp.dll
Haruskah saya menambahkan ekstensi ke jumlah byte saya? Adakah pikiran?
Log:
Disimpan 3 byte berkat Ismael Miguel.
Disimpan 26 byte berkat primo.
sumber
<?
dan menghapus definisi$j
.<
dalam$j<=$argv[1]
(mencetak terlalu banyak) (-1). Biarkan$e
tidak diinisialisasi, gunakan$e+7
sebagai gantinya (-3). Gunakanfor(;;)
alih-alihwhile()
, memanfaatkan ekspresi sebelum dan sesudah ekspresi (-2). Gantiecho$t.' ';$j++
dengan$j+=print"$t "
, lepaskan tanda kurung (-3). Gantiif($t>1)
dengan2>$t||
(-2). Gabungkan penugasan$t
dengan conditional, switch||
foror
, drop kurung (-5). Pindah$argv[1]
ke$j
kenaikan, pindahkan seluruh ekspresi kefor
conditional (-2). Ubah>=$j+=print
ke-=print
(-3). Langkah demi langkah: codepad.org/s6LNSPSM$e+7
dengan$e+=$t
(-2). Biarkan$i
tidak diinisialisasi, gunakan~++$i
saja (-3). codepad.org/fDIImajpHaskell, 51 byte
Perhatikan bahwa
f
ini adalah fungsi yang akan mengembalikan elemen n pertama .Alih-alih menghitung
a(n)
dan kemudian mengerjakan perbedaan, kami menghitung perbedaand(n)
dan menjumlahkannya untuk mendapatkana(n)
. (Mereka yang tidak terbiasa dengan Haskell dapat memprotes bahwa kita perlua(n)
terlebih dahulu untuk mendapatkannyad(n)
, tetapi tentu saja evaluasi malas membuat kita mengatasi masalah ini!)Tidak Disatukan:
sumber
Pyth, 30 byte
Golf yang sangat buruk, bisa sangat berkurang. Menentukan fungsi rekursif di depan, memfilter pertama
.f
, dan kemudian memetakan perbedaan.Coba di sini online .
sumber
n = 0
Julia,
6967 byteIni adalah solusi berulang sederhana untuk masalah ini.
x
perbedaannya (yang managcd
), dan kemudian saya perbaruia
dengan menambahkanx
.sumber
JavaScript (ES6), 91
GCD rekursif, fungsi utama berulang. Tidak secepat itu.
Catatan biasa: tes menjalankan snippet pada browser apa pun yang mendukung EcmaScript 6 (terutama bukan Chrome bukan MSIE. Saya menguji pada Firefox, Safari 9 bisa pergi)
sumber
Haskell,
747166 byteGunakan triknya di sini: https://codegolf.stackexchange.com/a/39730/43318 , dan bebas poin.
(Sebelumnya: 71 byte)
Pertama buat urutan a, lalu ambil perbedaannya.
(Sebelumnya: 74 byte)
Fungsi daftar standar, ditambah penggunaan fungsi lambda secara cerdas. Perhatikan ini 1 byte lebih pendek dari yang lebih jelas
Jika kami tidak menghitung impor, saya bisa turun ke 66.
sumber
PARI / GP, 60 byte
Diambil kurang lebih langsung dari definisi a (n) - a (n-1) = gcd (n, a (n-1))
Output untuk
a(20)
:sumber
C ++,
193182180172 byteTerima kasih @ Jakube - menyimpan 8 byte pada output.
sumber
f
, yang mengembalikan array dengan hasilnya. Dengan cara ini Anda dapat menghapus termasuk, pemindaian dan cetak.Mathematica, 59 byte
sumber