Istnieje dość duża liczba funkcji generujących liczby pierwsze. Prawie wszystkie z nich są zbudowane i opierają się na sicie Eratostenesa, funkcji Möbiusa lub twierdzeniu Wilsona i są generalnie niemożliwe do obliczenia w praktyce. Ale są też generatory, które mają bardzo łatwą strukturę i zostały znalezione przypadkowo.
W 2003 roku Stephen Wolfram zbadał klasę zagnieżdżonych równań rekurencyjnych w eksperymencie komputerowym na żywo w NKS Summer School. Grupa ludzi wokół Matthew Franka przeprowadziła dodatkowe eksperymenty i odkryła interesującą właściwość tego prostego nawrotu
a(n) = a(n-1) + gcd(n,a(n-1))
z wartością początkową a(1) = 7
. Różnica a(n) - a(n-1) = gcd(n,a(n-1))
zawsze wydawała się 1 lub liczbą pierwszą. Pierwsze kilka różnic to ( 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, ...
Jeśli pominiemy tylko jedynki, otrzymamy następującą sekwencję ( 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, ...
Kilka lat później Eric S. Rowland udowodnił prymat każdego elementu z tej listy. Jak widać, liczby pierwsze są mieszane, a niektóre z nich pojawiają się wiele razy. Udowodniono również, że sekwencja zawiera nieskończenie wiele różnych liczb pierwszych. Ponadto przypuszcza się, że pojawiają się wszystkie nieparzyste liczby pierwsze.
Ponieważ ten główny generator nie został skonstruowany, ale po prostu został znaleziony przypadkowo, główny generator nazywany jest „naturalnie występującym”. Zauważ jednak, że w praktyce generator ten jest również bardzo trudny do obliczenia. Jak się okazuje, pierwsze p pojawia się dopiero po (p–3)/2
kolejnych 1s. Niemniej jednak wdrożenie tego generatora będzie Twoim zadaniem.
Wyzwanie:
Napisz funkcję lub program, który drukuje pierwsze n
elementy sekwencji A137613
(sekwencja bez 1s). Numer wejściowy można odczytać za n >= 0
pomocą STDIN, argumentu wiersza poleceń, monitu lub argumentu funkcji. Wypisz pierwsze n
elementy w dowolnym czytelnym formacie do STDOUT lub zwróć tablicę lub listę z tymi wartościami.
To jest golf golfowy. Dlatego wygrywa najkrótszy kod.
Tabela liderów:
Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka. Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:
# Language Name, N bytes
gdzie N jest rozmiarem twojego zgłoszenia. Jeśli poprawisz swój wynik, możesz zachować stare wyniki w nagłówku, przekreślając je. Na przykład:
# 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
być zero?//
) i wyjaśnij to w swoim zgłoszeniu. Jeśli ktoś się z tobą nie zgadza, zawsze możesz edytować swój post.Odpowiedzi:
Pyth,
1413 bajtówUżywa
a(n) = Lpf(6 - n + sum(a(i) for i in range(1, n))
gdzieLpf
oznacza najmniejszy czynnik główny.Wypróbuj tutaj online.
źródło
Python 3.5.0b1 +,
9593 bajtówLink do wydania Python 3.5.0b1 +
Bezpośrednia realizacja cyklu, obejmująca:
1%x
imath.gcd
, w przeciwieństwie dofractions.gcd
.źródło
1%x
zrobić? Pytanie poboczne: gdzie znajdę dokumentację historii wersji Pythona, która zawiera bety? Edycja: Nevermind, znalazłem go na dole historii zmian .x >= 1
,1%x
zwraca 0 jeślix == 1
, 1 inaczej (używany do zdecydować, czy dodaćx
do listy)Julia, 110 bajtów
Nie golfowany:
źródło
n<2
zamiastn==1
. Ponadto, jeśli spojrzeć do przodu zamiast do tyłu, można użyći=1
ix=a(i)-a(i+=1)
, a następnieprintln(-x)
i-x>1
na prawidłowe dla negativeness, unikając w ten sposób konieczności stosowania oddzielnego przyrostui
. I≥
ma trzy bajty, podczas gdy>=
dwa ... ale wtedy możesz użyćn<1||()
zamiastn>=1&&()
... a mimo to nie jest to nawet konieczne (porzuć warunek, n nigdy nie będzie mniejszy niż 1). Nie potrzebujesz również najbardziej zewnętrznych nawiasów podczas definiowania (n). Dzięki tym zmianom powinieneś uzyskać przynajmniej 97 bajtów.PHP,
1019699987772 bajtówUżycie:
Wywołaj skrypt z argumentem:
php -d error_reporting=0 script.php 30
jeśli chcesz go przetestować, musisz cofnąć komentarz
;extension=php_gmp.dll
w php.ini->
extension=php_gmp.dll
Czy powinienem dodać rozszerzenie do mojej liczby bajtów? jakieś pomysły?
Dziennik:
Zapisano 3 bajty dzięki Ismael Miguel.
Zaoszczędź 26 bajtów dzięki primo.
źródło
<?
i usunąć definicję$j
.<
w$j<=$argv[1]
(drukuje o jeden za dużo) (-1). Pozostaw$e
niezainicjowane, użyj$e+7
zamiast tego (-3). Użyjfor(;;)
zamiastwhile()
, używając wyrażeń wstępnych i końcowych (-2). Wymienićecho$t.' ';$j++
z$j+=print"$t "
, spadek wsporniki (-3). Wymienićif($t>1)
z2>$t||
(-2). Połącz przypisanie$t
z warunkowym, przełącz||
naor
, upuść nawiasy (-5). Przejdź$argv[1]
do$j
przyrostu, przenieś całe wyrażenie dofor
warunkowej (-2). Zmień>=$j+=print
na-=print
(-3). Krok po kroku: codepad.org/s6LNSPSM$e+7
z$e+=$t
(-2). Pozostaw$i
niezainicjowane, użyj~++$i
zamiast tego (-3). codepad.org/fDIImajpHaskell, 51 bajtów
Zauważ, że
f
jest to funkcja, która zwróci pierwsze n elementów.Zamiast obliczać,
a(n)
a następnie opracowywać różnice, obliczamy różniced(n)
i sumujemy je razema(n)
. (Osoby niezaznajomione z Haskellem mogą protestować, żea(n)
najpierw musimy to zrobićd(n)
, ale oczywiście leniwa ocena omija ten problem!)Nie golfowany:
źródło
Pyth, 30 bajtów
Bardzo źle golfa, można znacznie zmniejszyć. Definiuje funkcję rekurencyjną z przodu, filtruje
.f
irst-n, a następnie odwzorowuje różnicę.Wypróbuj tutaj online .
źródło
n = 0
Julia,
6967 bajtówJest to proste iteracyjne rozwiązanie problemu.
x
jest różnica (która jestgcd
), a następnie aktualizujęa
, dodającx
.źródło
JavaScript (ES6), 91
Rekurencyjny gcd, iteracyjna główna funkcja. Nie tak szybko.
Zwykła uwaga: przetestuj fragment kodu w dowolnej przeglądarce zgodnej z EcmaScript 6 (w szczególności nie Chrome, a nie MSIE. Testowałem na Firefoxie, Safari 9 mogłaby działać)
źródło
Haskell,
747166 bajtówZastosowałem lewę tutaj: https://codegolf.stackexchange.com/a/39730/43318 i uczyniono bez punktów.
(Poprzedni: 71 bajtów)
Najpierw utwórz sekwencję a, a następnie weź różnice.
(Poprzedni: 74 bajty)
Standardowe funkcje listy oraz sprytne wykorzystanie funkcji lambda. Zauważ, że jest to 1 bajt krótszy niż bardziej oczywisty
Jeśli nie liczymy importów, mogę to zmniejszyć do 66.
źródło
PARI / GP, 60 bajtów
Wzięte mniej więcej prosto z definicji a (n) - a (n-1) = gcd (n, a (n-1))
Dane wyjściowe dla
a(20)
:źródło
C ++,
193182180172 bajtówDzięki @Jakube - zapisano 8 bajtów na wyjściu.
źródło
f
, która zwraca tablicę z wynikami. W ten sposób możesz usunąć dołączenie, skan i wydruk.Mathematica, 59 bajtów
źródło