Algoritmus für die Primzahlen durch Wiederholung von Additionen?

Question

Ich habe einen Algoritmus für die Primzahlen entdeckt.....

Alleine durch Wiederholung von Additionen kommt man direkt zu den Zahlen!

Hier MEIN Algorithmus: START bei der 7, inkl. den vorherigen Zahlen UR Primzahlen, dadurch entstehen erst die eigentlichen Primzahlen:

7

+4=11
+2=13
+4=17
+2=19
+4=23

+6=29
+2=31
+6=37

+4=41
+2=43
+4=47
+2=49
+4=51

+6=57
+2=59
+6=61

+4=65
+2=67
+4=71
+2=73
+4=77

+6=83
+2=85
+6=91

+4=95
+2=97
+4=101
+2=103
+4=107


77 und 49 sind zur Bestimmung/Addition wichtig, welche aber als Vervielfältigungszahlen automatisch raus fallen...

Deshalb werden die Primzahlen auch immer weniger, je größer die Zahl wird.

Geht schneller oder?!

Sandra, 48, Mama , verheiratet, angestellt, und ich liebe Rätsel!!

Was haltet ihr davon?

Answer 1

Hallo Sandra,

schön, dass Du von der Folge https://oeis.org/A001223
11 Glieder nachbilden konntest.

Das ist jedoch nur kleiner Zufall und Grundschulwissen und hat nichts mit exaktem Algorithmus (Bildungsgesetz)  zu tun.

Mit Interpolationen (egal ob Polynome, Trigonometrischen Funktionen ,...) kann man hunderte Glieder richtig finden und hat damit immer noch nicht mal ansatzweise die unendlich große Tür zu den echten Primzahlen aufgeschlagen!
Auszüge weiter hinten ab der 112228680. Primzahl zeigen schöne Pseudozufallszahlen:
Differences[Prime[Range[112228680, 112228686]]]  = 58, 32, 28, 320, 40, 80,...

für Interessierte: eine exakte Formeldarstellung für die Primzahlen gibt es längst:
https://www.lamprechts.de/gerd/php/Formeln/Formel-7.png

Nachteil: die 3 ineinander verschachtelten Summen ergeben eine exponentiell anwachsende Berechnungszeit und sind bereits ab der 1000. Primzahl selbst mit schnellen Computern kaum noch in Stunden berechenbar.

Da gibt es schnellere Algorithmen. (http://www.pi-e.de/NextPrime-Benchmark.htm )

Comments

Nachteil: die 3 ineinander verschachtelten Summen ergeben eine exponentiell anwachsende Berechnungszeit

Exponentiell ist der Aufwand hier nicht. Wenn ich jetzt mal die Zwischenrechnungen, also Addition und Multiplikation als konstant vielen Aufwand annehme, dann landet man aufgrund der dreifach verschachtelten Summation in einem Aufwand von \(\Theta(n^3)\).

Aber hübsche Formel!

---

Theoretisch n^3 richtig.

Praktisch kommen noch zig Faktoren wie größer werdender RAM-Bedarf dazu:

n | Zeit in s {Mathematica ohne Optimierung}

20    0.812 s
30    3.842 s
40   11.387 s
50   26.868 s
60   53.562 s
70   98.9  s
80 155.5  s
90 244.3  s

Bis 80: -0.994754698918751+0.0000211191093854899 x^3.611295

Bis 90: -0.499937065684709+0.0000150578777030378 x^3.6894527

Bei Prime[100]=541 schon fast 6 min Rechenzeit!

Das geht dann für größere Argumente gegen x^4 (oder noch größer)

Answer 2

Hi,

was genau willst Du damit jetzt zeigen? Hier sind neben 77 und 49 auch 51, 57 und andere Zahlen keine Primzahlen?! Bspw fehlt aber auch die 89.

Grüße

Comments

Ich zeige hiermit, das. Primzahlen wiederholende sind....

Auch wenn einige durch das Sieb fallen, schneller kann man nicht zu den Zahlen kommen....

---

Somit sind die Primzahlen unendlich, solange sie nicht als Produkt der Vorzahlen ausscheiden....

Deshalb : Wie Sterne in der Galaxie,

Je weiter, desto weniger, aber hier und da.......

Answer 3

Hallo,

ab der 5 sind alle Primzahlen von der Form

      6n±1

Wenn du abwechselnd 2 und 4 bzw. 2+4 addierst, benutzt du genau diese Tatsache.

:-)