Der Sinus-Primzahltest

DIE PRIMZAHLENSERIE

Beitrag 10

Der Sinus-Primzahltest ist kein Wahrscheinlichkeitstest, sondern ein indirekter Test, der eindeutig bestimmt, ob eine gewählte ungerade Zahl größer 1 eine Primzahl ist oder nicht.

Der Test basiert auf der Definition 6 aus Beitrag 1, Primzahldefinitionen:

Da es unendlich viele Primzahlen gibt und nur eine gerade Primzahl, nämlich 2, muß es unendlich viele ungerade Primzahlen geben. Daher folgende Definition für alle Primzahlen größer 2:

Eine Primzahl größer 2 ist eine ungerade Zahl U größer 2, die durch keine ungerade Zahl u im Bereich $3 \leq u \leq \sqrt{U}$ ohne Rest teilbar ist.

Dieser Test gilt für alle ungeraden Zahlen $U > 1$ .

Mit

$U=2n+3$ ᴧ n ∈ ℕ

sind alle ungeraden Zahlen > 1 gegeben, die für diesen Test ausgewählt werden können.

Aufgelöst nach n ergibt sich

$n=\frac{U-3}{2}$

Das ermittelte n wird dann in die folgende Testfunktion ts(n) eingesetzt:

$ts(n)=\prod\limits_{k=0} ^{k_{max}} \lceil\sin^2(\frac{n-k}{2k+3}\pi)\rceil$

mit

$k_{max}=\lfloor{\frac{\sqrt{2n+3}-3} {2}\rfloor}$

wobei n ∈ ℕ und n ≥ 1 sowie k ∈ ℕ und k ≥ 0.

Legende:

$\prod\limits_{k=0} ^{k_{max}}$ Produkt, in dem die Laufvariable k von 0 bis k_maxläuft

|x| Absolutwert von einem beliebigem Wert x

⌊x⌋ untere Gaußklammer, x abgerundet auf die nächste ganze Zahl

⌈x⌉ obere Gaußklammer, x aufgerundet auf die nächste ganze Zahl

Für ein gewähltes n aus der Menge der natürlichen Zahlen ist ts(n) entweder 0 oder 1.

Ist ts(n)=0, dann ist 2n+3 für das gewählte n nicht prim.

Ist ts(n)=1, dann ist 2n+3 für das gewählte n prim.

Beweis:

In Beitrag 6 wurde bewiesen, daß die Formel

n_km= 2k²+6k+3+m(2k+3) ʌ k, m ∈ ℕ

jene n liefert, die in der Formel 2n+3 alle zusammengesetzten, ungeraden Zahlen größer 2 ergeben.

Nehmen wir an, daß ein gewähltes n n_km entspricht, d.h.

$n = n_{km}$

dann können wir n in

$\sin(\frac{n-k}{2k+3}\pi)$

durch

2k²+6k+3+m(2k+3)

ersetzen.

Dies ergibt

$\sin(\frac{2k^2+6k+3+m(2k+3)-k}{2k+3}\pi)$

und weiter

$\sin(\frac{2k^2+5k+3}{2k+3}+m)\pi)$

$\frac{2k^2+5k+3}{2k+3}=k+1$

ergibt sich

$sin((k+1+m)\pi)$

Dieser Term hat immer den Wert 0, da k, 1 und m natürliche Zahlen sind, deren Summe wieder eine natürliche Zahl ergeben und der Sinus von ganzzahligen Vielfachen von π immer 0 ist.

Ist aber

$n \neq n_{km}$

dann ist

$\sin(\frac{n-k}{2k+3}\pi) \neq 0$

da alle ungeraden, zusammengesetzten Zahlen > 1 durch n_km in 2n+3 gegeben sind und alle anderen n in 2n+3 prim sein müssen.

Doch wie groß ist k_max?

Gemäß Definition 6, Beitrag 1 gilt:

Eine Primzahl größer 2 ist eine ungerade Zahl U größer 2, die durch keine ungerade Zahl u im Bereich

$3 \le u \le \sqrt{U}$

ohne Rest teilbar ist.

Setzt man

$U=2n+3$ ᴧ n ∈ ℕ

und

$u=2k+3$ ᴧ n ∈ ℕ

$u \le \sqrt{U}$

ergibt dies

$2k+3 \le \sqrt{2n+3}$

Die Lösungen für k bei einem gewählten n reichen von k=0 bis k=k_max für n, k ∈ ℕ.

Da wir k_maxalso als natürliche Zahl bestimmen wollen, aber bei der Auflösung nach k für k in den reellen Zahlenbereich kommen, schreiben wir zur besseren Unterscheidung:

$2k_{max_{r}}+3 = \sqrt{2n+3}$

Aufgelöst nach $k_{max_{r}}$ ergibt sich folgende Lösung:

$k_{max_{r}} = \frac{\sqrt{2n+3}-3}{2}$

Die reelle Lösung für $k_{max_{r}}$ kann durch Auf- oder Abrunden wieder in den Bereich der natürlichen Zahlen zurückgeführt werden.

In unserem Fall ist gemäß Definition 6 aus Beitrag 1 abzurunden.

Somit ergibt sich für k_max

$k_{max}=\lfloor{\frac{|\sqrt{2n+3}-3|} {2}\rfloor}$

Der Term

$\lceil|\sin(\frac{n-k}{2k+3}\pi)|\rceil$ bzw. $\lceil\sin^2(\frac{n-k}{2k+3}\pi)\rceil$

kann nur die Werte 0 oder 1 annehmen, wenn

$n = n_{km}$ → $\lceil|\sin(\frac{n_{km}-k}{2k+3}\pi)|\rceil=\sin((k+1+m)\pi) =0$

$n \neq n_{km}$ → $\lceil|\sin(\frac{n-k}{2k+3}\pi)|\rceil=1$

Ist dieser Term 0, ergibt das gewählte n in der Formel 2n+3 keine Primzahl, sondern eine zusammengesetzte, ungerade Zahl.

Ist dieser Term 1, kann das gewählte n in der Formel 2n+3 eine Primzahl ergeben, muß aber nicht.

Bildet man aber das Produkt für alle k von 0 bis k_max und ist dieses Produkt nicht 0, sondern 1, dann ist mit diesem deterministischen Primzahltest eindeutig sichergestellt, daß 2n+3 eine Primzahl ist. Ist aber in diesem Produkt mindestens ein Faktor 0, dann ist das gesamte Produkt 0, und es ist mit diesem deterministischen Primzahltest eindeutig sichergestellt, daß 2n+3 für das gewählte n keine Primzahl ergibt.

Was zu beweisen war.

Beispiele

n=1 → ts(1)=1 → 2*1+3=5 → prim

n=10 → ts(10)=1 → 2*10+3=23 → prim

n=97 → ts(97)=1 → 2*97+3=197 → prim

n=1002 → ts(1001)=0 → 2*1001+3=2005 → nicht prim

n=30997 → ts(30997)=0 → 2*30997+3=61997=13*19*251 → nicht prim

n=30103 → ts(30103)=1 → 2*30103+3=60209 → prim

München, 11. November 2022

Gottfried Färberböck

Sprache:

Sprache:

DIE PRIMZAHLENSERIE

Der Sinus-Primzahltest