Es gibt eine große Anzahl von Funktionen zur Erzeugung von Primzahlen. Ziemlich alle von ihnen sind konstruiert und basieren auf dem Sieb von Eratosthenes, der Möbius-Funktion oder dem Wilson-Theorem und sind im Allgemeinen in der Praxis nicht berechenbar. Es gibt aber auch Generatoren, die einen sehr einfachen Aufbau haben und zufällig gefunden wurden.

Im Jahr 2003 untersuchte Stephen Wolfram eine Klasse verschachtelter Wiederholungsgleichungen in einem Live-Computerexperiment an der NKS Summer School. Eine Gruppe von Menschen um Matthew Frank hat daraufhin weitere Experimente durchgeführt und eine interessante Eigenschaft der einfachen Wiederholung entdeckt

a(n) = a(n-1) + gcd(n,a(n-1))

mit dem Startwert von a(1) = 7. Der Unterschied a(n) - a(n-1) = gcd(n,a(n-1))schien immer 1 oder eine Primzahl zu sein. Die ersten Unterschiede sind ( 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, ...

Wenn wir nur die Einsen weglassen, erhalten wir die folgende Sequenz ( 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 bewies einige Jahre später die Primität jedes Elements in dieser Liste. Wie Sie sehen können, sind die Primzahlen gemischt und einige von ihnen erscheinen mehrmals. Es wurde auch nachgewiesen, dass die Sequenz unendlich viele verschiedene Primzahlen enthält. Weiterhin wird vermutet, dass alle ungeraden Primzahlen auftreten.

Da dieser Primärgenerator nicht konstruiert wurde, sondern einfach zufällig gefunden wurde, wird der Primärgenerator als "natürlich vorkommend" bezeichnet. Beachten Sie jedoch, dass sich dieser Generator in der Praxis auch nicht berechnen lässt. Wie sich herausstellt, erscheint eine Primzahl p erst nach (p–3)/2aufeinanderfolgenden Einsen. Trotzdem wird es Ihre Aufgabe sein, diesen Primärgenerator zu implementieren.

Herausforderung:

Schreiben Sie eine Funktion oder ein Programm, das die ersten nElemente der Sequenz druckt A137613(die Sequenz ohne die Einsen). Sie können die Eingabenummer n >= 0über STDIN, Befehlszeilenargument, Eingabeaufforderung oder Funktionsargument lesen . Geben Sie die ersten nElemente in einem beliebigen lesbaren Format an STDOUT aus oder geben Sie ein Array oder eine Liste mit diesen Werten zurück.

Das ist Code-Golf. Daher gewinnt der kürzeste Code.

Bestenliste:

Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren. Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wobei N die Größe Ihrer Einreichung ist. Wenn Sie Ihre Punktzahl verbessern, können Sie alte Punkte in der Überschrift behalten, indem Sie sie durchstreichen. Zum Beispiel:

# 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 Bytes

meaYhP+sY-5dQ

Verwendet, a(n) = Lpf(6 - n + sum(a(i) for i in range(1, n))wo der Lpfkleinste Primfaktor bedeutet.

Probieren Sie es hier online.

Python 3.5.0b1 +, 95 93 Bytes

Link zu Python 3.5.0b1 + Release

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

Eine direkte Implementierung der Wiederholung mit:

• Unser guter Freund 1%xund
• math.gcdim Gegensatz zu fractions.gcd.

Julia, 110 Bytes

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)

Ungolfed:

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 Bytes

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

Verwendung:
Rufen Sie das Skript mit einem Argument auf: php -d error_reporting=0 script.php 30
Wenn Sie es testen möchten, müssen ;extension=php_gmp.dllSie das Kommentarzeichen in Ihrer php.ini entfernen
-> extension=php_gmp.dll
Soll ich die Erweiterung zu meiner Byteanzahl hinzufügen? Irgendwelche Gedanken?

Protokoll:
Dank Ismael Miguel wurden 3 Bytes gespeichert.
26 Bytes dank primo gespart.

Haskell, 51 Bytes

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

Beachten Sie, dass dies feine Funktion ist, die die ersten n Elemente zurückgibt.

Anstatt a(n)die Unterschiede zu berechnen und dann zu berechnen, berechnen wir sie d(n)und addieren sie, um sie zu erhalten a(n). (Diejenigen, die mit Haskell nicht vertraut sind, mögen protestieren, dass wir a(n)zuerst brauchen, um es zu bekommen d(n), aber eine faule Bewertung bringt uns natürlich um dieses Problem herum!)

Ungolfed:

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 Bytes

Sehr schlecht golfen, kann erheblich reduziert werden. Definiert die rekursive Funktion im .fVordergrund , filtert zuerst n und bildet dann den Unterschied ab.

L?tb+KytbibK7m-yhdyd.ft-yhZyZQ

Probieren Sie es hier online .

Julia, 69 67 Bytes

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

Dies ist eine einfache iterative Lösung des Problems. xist der Unterschied (der ist der gcd), und dann aktualisiere ich adurch Hinzufügen x.

JavaScript (ES6), 91

Rekursive gcd, iterative Hauptfunktion. Nicht so schnell.

Üblicher Hinweis: Testen Sie die Ausführung des Snippets in jedem EcmaScript 6-kompatiblen Browser (insbesondere nicht in Chrome und nicht in MSIE. Ich habe es in Firefox getestet, Safari 9 könnte funktionieren).

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 Bytes

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

Habe den Trick hier benutzt: https://codegolf.stackexchange.com/a/39730/43318 , und ohne Punkt gemacht.

(Vorher: 71 Bytes)

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

Machen Sie zuerst die Sequenz von a und nehmen Sie dann die Unterschiede.

(Vorher: 74 Bytes)

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

Standardlistenfunktionen sowie die clevere Verwendung der Lambda-Funktion. Beachten Sie, dass dies 1 Byte kürzer ist als das offensichtlichere

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

Wenn wir die Importe nicht zählen, kann ich das auf 66 reduzieren.

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

PARI / GP, 60 Bytes

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

Mehr oder weniger direkt aus der Definition a (n) - a (n-1) = gcd (n, a (n-1))

Ausgabe für 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 Bytes

Danke @Jakube - 8 Bytes bei der Ausgabe gespart.

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 Bytes

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