Euler hat die bemerkenswerte Formel
veröffentlicht. Es ergibt sich, dass die Formel 40 Primzahlen für die aufeinanderfolgenden Werte für n=0 bis 39 erzeugt.
Wenn allerdings n=40, ist das Ergebnis durch 41 teilbar, die Reihe an Primzahlen endet dort also.
Mit Hilfe von Computern hat man die unglaubliche Formel
gefunden, die 80 aufeinanderfolgende Primzahlen für n=0 bis 79 erzeugt. Das Produkt der Koeffizienten -79 und 1601 ist -126479.
Wir betrachten die allgemeine quadratische Formel
wobei der Betrag von a und b jeweils unter 1000 liegt. Mit welchen Koeffizienten produziert die quadratische Formel die meisten Primzahlen für aufeinanderfolgende Werte für n, beginnend mit n=0? Geben Sie das Produkt der Koeffizienten an!
Lösung
Für n=0 soll die Formel schon eine Primzahl erzeugen. Es ist aber
Daher muss b eine Primzahl sein. Wir erzeugen daher ein Feld mit allen Primzahlen von 1 bis 999.
Betrachten wir nun den zweiten Koeffizienten. Da für n=1 eine Primzahl erzeugt werden soll, muss
eine Primzahl sein. Da b eine Primzahl ist, ist b auf jeden Fall ungerade. Wenn wir 1 addieren, erhalten wir eine gerade Zahl. Da das Ergebnis wieder ungerade sein muss, ist a auf jeden Fall ungerade.
Damit das Ergebnis positiv wird, muss gelten:
Es ergibt sich folgender Algorithmus.
Matlab-Code:
tic; pList = primes(1000); N = length(pList); n = 0 : 80; best = 0; for x = 1 : N b = pList(x); for a = - (b + 2) : 2 : 999 p = n.^2 + a * n + b; q = 1; while (p(q) > 0 && isprime(p(q)) && q < 80) q = q+1; end if (best < q) paar = [a b]; best = q; end end end disp(prod(paar)) toc
Ergebnis: -59231
Rechenzeit: 7.772937 Sekunden
Die Eulerformel und die angegebene “unglaubliche Formel” gehören beide zu der Familie
wobei bei der Eulerformel i = 40 und bei der unglaublichen Formel i = 0 gilt. Das Ergebnis dieser Aufgabe entspricht i = 9.