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.