027 – Polynome zur Erzeugung von Primzahlen

 

Euler hat die bemerkenswerte Formel

n^2+n+41

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

n^2-79n+1601

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

n^2+an+b

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

0^2+0a+b = b

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

1^2+1a+b = 1 + a + b

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:

a > -\frac{b+2}{2}

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

\left(n+i\right)^2-79\left(n+i\right)+1601

wobei bei der Eulerformel i = 40 und bei der unglaublichen Formel i = 0 gilt. Das Ergebnis dieser Aufgabe entspricht i = 9.

Ähnliche Artikel

Kommentar verfassen