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)/2kolejnych 1s. Niemniej jednak wdrożenie tego generatora będzie Twoim zadaniem.

Wyzwanie:

Napisz funkcję lub program, który drukuje pierwsze nelementy sekwencji A137613(sekwencja bez 1s). Numer wejściowy można odczytać za n >= 0pomocą STDIN, argumentu wiersza poleceń, monitu lub argumentu funkcji. Wypisz pierwsze nelementy 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&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\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>

Pyth, 14 13 bajtów

meaYhP+sY-5dQ

Używa a(n) = Lpf(6 - n + sum(a(i) for i in range(1, n))gdzie Lpfoznacza najmniejszy czynnik główny.

Wypróbuj tutaj online.

Python 3.5.0b1 +, 95 93 bajtów

Link do wydania Python 3.5.0b1 +

import math
def f(k,n=2,a=7,L=[]):x=math.gcd(n,a);return k and f(k-1%x,n+1,a+x,L+1%x*[x])or L

Bezpośrednia realizacja cyklu, obejmująca:

• Nasz dobry przyjaciel 1%xi
• math.gcd, w przeciwieństwie do fractions.gcd.

Julia, 110 bajtów

n->(a(n)=(n≥1&&(n==1?7:a(n-1)+gcd(n,a(n-1))));i=2;j=0;while j<n x=a(i)-a(i-1);x>1&&(j+=1;println(x));i+=1end)

Nie golfowany:

function a(n::Int)
    n ≥ 1 && (n == 1 ? 7 : a(n-1) + gcd(n, a(n-1)))
end

function f(n::Int)
    i = 2;
    j = 0;
    while j < n
        x = a(i) - a(i-1)
        if x > 1
            j += 1
            println(x)
        end
        i += 1
    end
end

PHP, 101 96 99 98 77 72 bajtów

<?for(;2>$t=gmp_strval(gmp_gcd(~++$i,7+$e+=$t))or$argv[1]-=print"$t ";);

Uż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.dllw 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.

Haskell, 51 bajtów

d=zipWith gcd[2..]$scanl(+)7d
f=($filter(>1)d).take

Zauważ, że fjest to funkcja, która zwróci pierwsze n elementów.

Zamiast obliczać, a(n)a następnie opracowywać różnice, obliczamy różnice d(n)i sumujemy je razem a(n). (Osoby niezaznajomione z Haskellem mogą protestować, że a(n)najpierw musimy to zrobić d(n), ale oczywiście leniwa ocena omija ten problem!)

Nie golfowany:

a = scanl (+) 7 d        -- yielding a(n) = 7 + d(1) + d(2) + ... + d(n-1)
d = zipWith gcd [2..] a  -- yielding d(n) = gcd(n+1, a(n))

f n = take n $ filter (> 1) d -- get rid of 1s and take the first n

Pyth, 30 bajtów

Bardzo źle golfa, można znacznie zmniejszyć. Definiuje funkcję rekurencyjną z przodu, filtruje .first-n, a następnie odwzorowuje różnicę.

L?tb+KytbibK7m-yhdyd.ft-yhZyZQ

Wypróbuj tutaj online .

Julia, 69 67 bajtów

n->(i=1;a=7;while n>0 x=gcd(i+=1,a);a+=x;x>1&&(n-=1;println(x))end)

Jest to proste iteracyjne rozwiązanie problemu. xjest różnica (która jest gcd), a następnie aktualizuję a, dodając x.

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ć)

F=m=>{
  for(G=(a,b)=>b?G(b,a%b):a,o=[],p=7,n=1;m;d>1&&(o.push(d),--m))
    p+=d=G(++n,p);
  return o
}

O.innerHTML=F(+I.value)

<input id=I value=10><button onclick='O.innerHTML=F(+I.value)'>-></button>
<pre id=O></pre>

Haskell, 74 71 66 bajtów

f=($filter(>1)$tail>>=zipWith(-)$scanl(\x->(x+).gcd x)7[2..]).take

Zastosowałem lewę tutaj: https://codegolf.stackexchange.com/a/39730/43318 i uczyniono bez punktów.

(Poprzedni: 71 bajtów)

a=scanl(\x->(x+).gcd x)7[2..]
f m=take m$filter(>1)$zipWith(-)(tail a)a

Najpierw utwórz sekwencję a, a następnie weź różnice.

(Poprzedni: 74 bajty)

f m=take m$filter(>1)$map snd$scanl(\(x,d)->(\y->(x+y,y)).gcd x)(7,1)[2..]

Standardowe funkcje listy oraz sprytne wykorzystanie funkcji lambda. Zauważ, że jest to 1 bajt krótszy niż bardziej oczywisty

g m=take m$filter(>1)$map snd$scanl(\(x,d)n->(x+gcd x n,gcd x n))(7,1)[2..]

Jeśli nie liczymy importów, mogę to zmniejszyć do 66.

import Data.List
h m=take m$filter(>1)$snd$mapAccumL(\x->(\y->(x+y,y)).gcd x)7[2..]

PARI / GP, 60 bajtów

a(n)=a=7;i=1;while(n,if(1<d=gcd(i+=1,a),n-=1;print(d));a+=d)

Wzięte mniej więcej prosto z definicji a (n) - a (n-1) = gcd (n, a (n-1))

Dane wyjściowe dla a(20):

5
3
11
3
23
3
47
3
5
3
101
3
7
11
3
13
233
3
467
3

C ++, 193 182 180 172 bajtów

Dzięki @Jakube - zapisano 8 bajtów na wyjściu.

int g(int a,int b){return a==b?a:a>b?g(b,a-b):g(a,b-a);}void f(int *r,int n){int m=1,i=0,a=7,b;while(i<n){b=g(a,++m);if(b>1){r[i]=b;++i;}a+=b;}}int main(){int r[6];f(r,6);}

Mathematica, 59 bajtów

For[i=j=1;a=7,i<=#,,d=GCD[++j,a];If[d>1,Print@d;i++];a+=d]&