Die Primzahl-Zwillingssuche

Letztmalig dran rumgefummelt: 27.05.08 15:02:00

	Primzahlzwillinge sind sehr selten und existieren aus Sicht des Schreibers dieser Zeilen mit derzeitigem Erkenntnisstand in großer Dichte nur im unteren Bereich des Systems der natürlichen Zahlen. Definiert sind sie dadurch, dass der Abstand zweier benachbarter Primzahlen gleich zwei ist - also schau'n wer moal ;-)
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für die Primzahl-Zwillingssuche Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff.

1. Problembeschreibung

	Primzahlzwillinge nennt man zwei Primzahlen p1 und p2, deren Differenz p2 − p1 = 2 ist. Die Primzahl p2 = p1 + 2 wird dabei auch als Primzahlzwilling zur Primzahl p1 bezeichnet.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten.
	Jede ganze Zahl lässt sich in der Form 6n-2, 6n-1, 6n, 6n+1, 6n+2 oder 6n+3 darstellen (mit einer ganzen Zahl n). Primzahlen (außer 2 und 3) haben aber nicht die Form 6n-2, 6n, 6n+2, 6n+3, da alle solchen Zahlen durch 2 oder durch 3 (oder sogar durch 6) teilbar sind. Daher hat jede Primzahl (außer 2 und 3) die Form 6n-1 oder 6n+1. Wenn nun (p, p+2) Primzahlzwillinge sind, ist p auch nicht von der Form 6n+1. Also gilt: Wenn (p, q) Primzahlzwillinge sind, dann ist p von der Form 6n-1 und q von der Form 6n+1. Daraus folgt auch, dass p*q+1 eine durch 36 teilbare Quadratzahl ist: . n (6n-1) (6n+1) 1 5 7 2 11 13 3 17 19 5 29 31 7 41 43 10 59 61 12 71 73 17 101 103 18 107 109 23 137 139 25 149 151 30 179 181 n (6n-1) (6n+1) 32 191 193 33 197 199 38 227 229 40 239 241 45 269 271 47 281 283 52 311 313 58 347 349 70 419 421 72 431 433 77 461 463 87 521 523 n (6n-1) (6n+1) 95 569 571 100 599 601 103 617 619 107 641 643 110 659 661 135 809 811 137 821 823 138 827 829 143 857 859 147 881 883 170 1019 1021 172 1031 1033 n (6n-1) (6n+1) 175 1049 1051 177 1061 1063 182 1091 1093 192 1151 1153 205 1229 1231 213 1277 1279 215 1289 1291 217 1301 1303 220 1319 1321 238 1427 1429 242 1451 1453 247 1481 1483 n (6n-1) (6n+1) 248 1487 1489 268 1607 1609 270 1619 1621 278 1667 1669 283 1697 1699 287 1721 1723 298 1787 1789 312 1871 1873 313 1877 1879 322 1931 1933 325 1949 1951 333 1997 1999 n (6n-1) (6n+1) 338 2027 2029 347 2081 2083 348 2087 2089 352 2111 2113 355 2129 2131 357 2141 2143 373 2237 2239 378 2267 2269 385 2309 2311 390 2339 2341 397 2381 2383 425 2549 2551 Mit Ausnahme von n=1 ist die letzte Ziffer eines n eine 0, 2, 3, 5, 7 oder eine 8, da im anderen Fall eine der beiden Zahlen 6n-1 bzw. 6n+1 durch 5 teilbar und damit keine Primzahl wäre. Mit einer ganzen Zahl n lässt sich jede ungerade Zahl in der Form 30n+1, 30n+3, 30n+5, 30n+7, ..., 30n+25, 30n+27, 30n+29 (bzw. letztere besser als 30n-1) darstellen. Primzahlen (außer 3 und 5) haben aber nie die Form 30n+3, 30n+5, 30n+9, 30n+15, 30n+21, 30n+25 und 30n+27, da alle solchen Zahlen durch 2, durch 3 oder durch 5 teilbar sind. Daher hat jedes Primzahlzwillingspaar (außer (3,5) und (5,7)) genau eine der drei Formen (30n-1, 30n+1), (30n+11, 30n+13), (30n+17, 30n+19) (bzw. letzteres alternativ, da symmetrischer, als (30n-13, 30n-11)) (mit einer ganzen Zahl n).

3. Lösungsalgorithmus

Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

4. Programmvorschläge

	Wir suchen alle Primzahlen und schaufeln sie in ein Feld - anschließend ermitteln wir von zwei benachbarten gefunden Primzahlen die Differenz - ist diese gleich zwei, so haben wir ein Primzahlzwilligspaar gefunden.
	Primzahlzwillinge direkt suchen - große Rechenzeit für große Zahlen ;-)

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

	http://de.wikipedia.org/wiki/Primzahlzwilling

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 24. Dezember 2007