1. Arithmetische Folgen und Arithmetische Primzahlfolgen
Arithmetische Zahlenfolgensind Aneinanderreihungen von Zahlen, bei denen die Abstände zwischen je zwei aufeinander folgenden Gliedern gleich sind. Ein Beispiel ist die Folge 5, 9, 13, 17, 21, 25. Der Abstand der Folgeglieder beträgt hierbei 4 und die Folge hat 6 Glieder. Interessant sind Folgen, wenn die Glieder noch zusätzliche Eigenschaften haben – zum Beispiel wenn sie Primzahlen sind. Eine arithmetische Primzahlfolge1 mit 5 Gliedern ist beispielsweise 5, 17, 29, 41, 53. Der Abstand der Zahlen beträgt hierbei jeweils 12. Diese Folge lässt sich nicht verlängern, denn das nächste Glied müsste 65 sein. Diese Zahl aber ist das Produkt aus 5 und 13 und somit keine Primzahl.
Wie viele Folgeglieder kann eine arithmetische Primzahlfolge haben? Im Jahre 1923 vermuteten die britischen Mathematiker Hardy und Littlewood 2, dass es keine obere Grenze für diese Zahl gebe. Mehr als 80 Jahre später (2004) konnte diese Vermutung von den Mathematikern Green und Tao 3 bewiesen werden: Es gibt arithmetische Primzahlfolgen beliebiger Länge. Außerdem bewiesen Green und Tao, dass es zu jeder vorgegebenen Länge unendlich viele verschiedene solcher Folgen gibt.
2. Länge und Schrittweite
Die Länge einer arithmetischen Primzahlfolge bestimmt den Mindestabstand zwischen den aufeinander folgenden Primzahlen, genannt die (minimale) Schrittweite der Folge.
Die minimale Schrittweite k einer arithmetischen Primzahlfolge der Länge m ist gleich dem Produkt aller Primzahlen, die kleiner oder gleich m sind, oder ein Vielfaches davon. Das Produkt aller Primzahlen kleiner oder gleich m wird mit m# („m primorial“) bezeichnet. Das heißt, es ist k = m# (oder ein Vielfaches von m#).
Bei einer Folge mit m = 6 Gliedern beispielsweise muss die Schrittweite mindestens 30 oder ein Vielfaches davon sein. Denn das Produkt 6# aller Primzahlen, die kleiner sind als 6, ist 6# = 5# = 2×3×5 = 30. Sucht man Folgen der Länge 10, muss die Schrittweite indestens 10# = 7# = 2×3×5×7 = 210 sein.
Zum Beweis betrachten wir alle Zahlen pi der Folge und die Schrittweite k modulo4 einer beliebigen Zahl n. Die Schrittweite k sei nicht durch n teilbar, es gelte zum Beispiel k = 1 (mod n). Dann würde man, ausgehend von p1 = 1 (mod n), nach n – 1-maliger Addition von k eine Zahl erhalten, die durch n teilbar und damit zusammengesetzt wäre: pn = p1 + (n – 1) × k = 1 + (n – 1) ×1 = n = 0 (mod n).
Ginge man von p1 = 2 oder größeren Werten (mod n) aus, würde man schon nach n – 2 oder weniger Schritten ein Folgeglied erhalten, das durch n teilbar wäre. Dasselbe wäre der Fall, wenn die Schrittweite k größer als 1 (mod n) wäre.
Daher muss die Schrittweite k durch die Zahl n teilbar sein, wenn man mindestens n Folgeglieder erhalten will, die nicht durch n teilbar sein sollen. Zum Beispiel muss k durch zwei teilbar und damit gerade sein, um nicht nach einem Schritt auf eine durch zwei teilbare Zahl zu stoßen (Folgen, die mit der Primzahl 2 beginnen, wollen wir nicht betrachten). Entsprechend muss die Schrittweite k durch 3 teilbar sein, damit nicht nach spätestens zwei Schritten ein durch 3 teilbares Folgeglied entsteht. Ist k nicht durch 5 teilbar, erhält man nach spätestens 4 Schritten eine durch 5 teilbare Zahl, usw.
Auch dazu ein Beispiel: Die Schrittweite k = 12 ist durch 2 und 3, aber nicht durch 5 teilbar. Wir versuchen, bei der Zahl p = 7 beginnend, eine arithmetische Primzahlfolge maximaler Länge mit dieser Schrittweite zu konstruieren. Das gelingt uns zunächst recht gut, die ersten drei Schritte liefern in der Tat Primzahlen: 7, 19, 31, 43. Aber dann folgt nach dem vierten Schritt, wie vorhergesagt, die durch 5 teilbare Zahl 55. Ein Blick in die modulare Arithmetik erklärt, warum das so sein muss: Modulo 5 gehört die Anfangszahl 7 zur Restklasse 2, die Schrittweite 12 ebenso – denn beide Zahlen ergeben, durch 5 geteilt, den Rest 2. Der erste Schritt führt daher, modulo 5 gerechnet und notiert, zu 2 + 2 = 4 (19 º 4 mod 5), der zweite Schritt zu 4 + 2 = 6 = 1 (31 º 1 mod 5), der dritte zu 1 + 2 = 3 (43 º 3 mod 5) und der vierte zu 3 +2 = 5 = 0. Daher ist die fünfte Zahl unserer Folge durch 5 teilbar und nicht prim.
3. Modulare Primzahlgrafiken
Wir wollen die genannten Folgen in einem Gitternetz der natürlichen Zahlen sichtbar machen. Folgen mit der Schrittweite 30 lassen sich in einem solchen Gitter direkt ablesen, wenn man die Zahlen in Zeilen der Länge 30 anordnet: In der ersten Zeile die Zahlen 0 bis 29, in der Zeile darunter diejenigen von 30 bis 59, usw. Das ist in Abb. 1 für die natürlichen Zahlen von 0 bis 899 geschehen.
Abb. 1: Die natürlichen Zahlen von 0 bis 302 – 1 = 899 von oben nach unten in Zeilen der Länge 30 aufgetragen: Primzahlen sind weiß gekennzeichnet, rot diejenigen Primzahlen, die arithmetische Folgen mit der Schrittweite 30 und der maximal möglichen Länge 6 bilden. Hervorgehoben sind die Vielfachen von 7 (blau) und 11 (dunkelblau), welche die weißen Balken in ihrer Länge begrenzen. Grün: sonstige Zahlen.
Damit in der ersten Spalte links die „glatten“ Zehner Platz finden, wurde auch die Null (schwarzes Feld links oben) mit aufgenommen. Primzahlen sind weiß markiert. Sie kommen, von der ersten Zeile abgesehen, nur in gewissen Spalten der Tabelle vor. Dies sind die Spalten, die keine der Vielfachen von 2, 3 und 5 enthalten. Mehrere weiße Felder untereinander entsprechen daher einer arithmetischen Primzahlfolge mit der Schrittweite 30. Die Vielfachen von 7 (blau) und 11 (dunkelblau) verhindern, dass mehr als sechs weiße Felder aneinander grenzen. Alle übrigen Zahlen sind durch grüne Felder dargestellt. Balken mit genau sechs aneinander grenzenden Feldern sind rot gekennzeichnet. Sie entsprechen den arithmetischen Primzahlfolgen maximaler Länge mit der Schrittweite 30.
Arithmetische Primzahlfolgen mit der Schrittweite 210 sind aus Abbildung 2 ablesbar. Hier sind die natürlichen Zahlen von 0 bis 26459 in Zeilen der Länge 210 aufgetragen. Primzahlen (weiß) kommen wiederum nur in Spalten vor, die keine der Vielfachen von 2, 3, 5 und 7 enthalten. In der rechten oberen Ecke erkennt man einen Balken der Länge 10. Er entspricht der arithmetischen Primzahlfolge 199, 409, 619, …, 2089. Primzahlfolgen maximaler Länge mit der Schrittweite 210 sind nicht sehr häufig anzutreffen. Die Folge mit dem kleinsten Startwert größer als 199 beginnt bei der Primzahl 243051733 und endet nach 10 Schritten bei 243053623.
Abb. 2: Die natürlichen Zahlen von 0 bis 26459 von oben nach unten in Zeilen der Länge 210 aufgetragen. Primzahlen sind weiß gekennzeichnet, Zahlen mit zwei Primteilern blau, Zahlen mit drei Primfaktoren magenta. Hervorgehoben sind die Vielfachen von 11 (rot) und 13 (grün), welche die weißen Balken in ihrer Länge begrenzen. Sonstige Zahlen: schwarz. Der weiße Balken in der rechten oberen Ecke entspricht der zehnteiligen arithmetischen Primzahlfolge 199 + 210n mit der Schrittweite 210 und der kleinsten Anfangszahl. Die nächste derartige Folge beginnt mit der Primzahl 243051733.
Die zeilenweise Anordnung unserer Zahlen hat natürlich einen mathematischen Hintergrund. Dazu betrachten wir nochmals Abb. 1. Die hier untereinander stehenden Zahlen bilden nicht nur arithmetische Folgen mit der Schrittweite 30, sondern haben drüber hinaus bei Division durch 30 dieselben Reste. Sie gehören derselben Restklasse (modulo 30) an. Die in der Spalte unter der 5 stehenden Zahlen 35, 65, 95, … beispielsweise gehören zur Restklasse 5 (ihre Reste bei Division durch 30 sind alle gleich 5). Mit Hilfe des Begriffs modulo lässt sich die Anordnung der Zahlen in den Abbildungen 1 und 2 kurz mit den Worten beschreiben: „Zahlen derselben Restklasse modulo 30 bzw. modulo 210 stehen untereinander“.
4. Warum trifft man Primzahlen nur in einem Teil der Spalten?
Unsere modulare Anordnung der Zahlen hatte den Zweck, arithmetische Primzahlfolgen sichtbar zu machen. Wie kommt es dazu, dass sich Primzahlen bei dieser Anordnung nur in gewissen Spalten „aufhalten“? Betrachten wir weiterhin Abb. 1. Die Zahlen einer Spalte bilden, wie schon erwähnt, eine arithmetische Folge mit der Schrittweite 30. Beispielsweise stehen unter der 5 in der ersten Zeile die Zahlen 35, 65, 95, … usw. Sie lassen sich alle in der Form 5 + 30n mit n = 0, 1, 2, …. schreiben. Ist die Zahl in der ersten Zeile m, haben alle Zahlen in derselben Spalte die Form m + 30n (m, n = 0, 1, 2, …). Entscheidend ist jetzt, von welcher Art diese Zahl m ist. Ist sie zum Beispiel ein Vielfaches von 2, also m = 2k (k = 1, 2, 3, …), dann stehen in der zugehörigen Spalte Zahlen der Form 2k + 30n. Da die Zahl 30 die Primfaktoren 2, 3 und 5 enthält (30 = 2×3×5), können wir die Zahlen dieser Spalte auch 2k + 2×3×5n schreiben – und sehen nun, dass sie alle den Faktor 2 enthalten und damit zusammengesetzt sind. Ist m in der ersten Zeile durch 3 oder 5 teilbar, also m = 3k bzw. m = 5k, lassen sich die Zahlen in den zugehörigen Spalten als 3k + 2×3×5n bzw. 5k + 2×3×5n schreiben und sind damit ebenfalls zusammengesetzt. Das heißt, wir finden in den Spalten, in deren erster Zeile Vielfache von 2, 3 oder 5 stehen, nur zusammengesetzte Zahlen. Für die Primzahlen bleiben daher nur diejenigen Spalten übrig, in deren erster Zeile Zahlen mit Primfaktoren stehen, die sämtlich größer als 5 sind, oder eine Primzahl (außer 2, 3 und 5) oder die 1 (Eins) steht. Die kleinste Zahl, deren Primfaktoren alle größer als 5 sind, ist 49 = 7×7 und kommt in der ersten Zeile nicht vor. Deshalb treten Primzahlen nur in den Spalten auf, in deren erster Zeile selber eine Primzahl oder die 1 steht.
In Abb. 2 gibt es aus demselben Grund Primzahlen nur in den Spalten, die nicht Vielfache von 2, 3, 5, oder 7 sind (210 = 2×3×5×7). Das sind die Spalten, in deren erster Zeile eine zusammengesetzte Zahl steht mit Primfaktoren, die sämtlich größer als 7 sind, oder eine Primzahl oder die Zahl 1 (Eins). Es gibt unterhalb von 210 nur drei zusammengesetzte Zahlen mit Primfaktoren, die alle größer als 7 sind, und zwar 121 (= 11×11), 143 (= 11×13) und 187 (= 11×17). Daher sammeln sich auch in Abb. 2 die Primzahlen zum großen Teil in den Spalten, in deren erster Zeile selber eine Primzahl steht.
Abb. 3 Die natürlichen Zahlen kleiner als 9000, angeordnet in Zeilen mit 89 Spalten (links), 90 Spalten (Mitte) und 91 Spalten (rechts). Weiß: Primzahlen. Während sich die Primzahlen in der Anordnung modulo 90 (Mitte) in senkrechten Geraden sammeln, reihen sie sich in den beiden anderen Anordnungen (modulo 89 bzw. modulo 91) auf Geraden unter den Winkeln ± 45° zur Horizontalen auf. Eine ähnliche Darstellung findet sich in den Bildern der Künstlerin Rune Mields mit dem Titel Sieb des Eratosthenes III
Die Häufung der Primzahlen auf senkrechten Geraden findet im Übrigen nur statt, wenn der Modul (die Anzahl der Spalten) Primfaktoren entält, die in vielen zusammengesetzten Zahlen vorkommen. Neben den Zahlen 30 und 210 sind beispielsweise die Module 42 (= 2×3×7), 60 (= 22×3×5), 84 (= 22×3×7) und 90 (= 2×32×5) geeignet. Dass Abweichungen von diesen Werten zu anderen Anordnungen der Primzahlfelder führen, zeigt Abb. 3. Sie stellt die natürlichen Zahlen kleiner als 9000 dar, und zwar in den Anordnungen modulo 90, modulo 89 (Primzahl) und modulo 91 (= 7×13). Primzahlen sind weiß markiert. In der Anordnung modulo 90 gruppieren sie sich, wie erwartet, auf senkrechten Geraden unterhalb der Primzahlen (und unterhalb der Zahlen 1, 49, 77 und 91) in der obersten Zeile. Denn der Modul 90 enthält die drei Primfaktoren 2, 3 und 5. In den Anordnungen modulo 89 (Primzahl) und modulo 91 (= 7×13) dagegen reihen sie sich auf Geraden unter ± 45° zur Horizontalen auf.
Eine ähnliche Darstellung der Primzahlen wie die der Abbildung 3 findet sich in den Bildern der Künstlerin Rune Mields mit dem Titel „Sieb des Eratosthenes III “ 5 – ein Beispiel dafür, dass konkret-konstruktivistische Kunst 6 mathematische Konzepte in eindrucksvoller Weise darzustellen vermag.
5. Bemerkungen
Die oben angegebene Formel k = m# für die minimale Schrittweite bei gegebener Länge m der Folge gilt für m > 7. Für einige Werte von m < 8 gibt es offenbar Ausnahmen:
– für m = 3 wäre laut Formel k = m# die minimale Schrittweite k = 3# = 2×3 = 6. Mögliche Folgen wären 5, 11, 17 oder 7, 13, 19 oder 11, 17, 23. Es gibt aber Folgen mit k = 2, zum Beispiel die mit 3 beginnenden Folgen 3, 5, 7 und 3, 7, 11.
– Für m = 5 wäre k = 5# = 2×3×5 = 30, tatsächlich gibt es jedoch die Folge 5, 11, 17, 23, 29 mit k = 6.
– für m = 7 müsste sein k = 7# = 2×3×5×7 = 210, es gibt jedoch eine Folge mit k = 150, die bei 7 startet: 7, 157, 307, 457, 607, 757, 907 (das nächste Folgeglied 1057 ist zusammengesetzt, 1057 = 7×151).
– J. K. Andersen7 macht dazu folgende Aussage: „The minimal possible difference in an AP-m is conjectured to be m# for all m > 7, proved for m ≤ 21 as of 2008.”
Weicht man von der Vorschrift k = m# ab, wählt zum Beispiel für m = 6 eine Schrittweite k = 2×3×7 = 42 (statt k = 30), erhält man Folgen, die weniger als 6 Primzahlen enthalten: 5, 47, 89, 173, 215, … oder 7, 49, …, oder 11, 53, 95, …, oder 17, 59, 101, 143, 185.
In der Literatur bezeichnet man eine arithmetische Primzahlfolge der Länge k mit APk. Die Folge AP13 beispielsweise hat eine Schrittweite von 13# = 2×3×5×7×11×13 = 30030 oder ein Vielfaches davon. Die Folge mit dem kleinsten Startwert beginnt bei der Primzahl 14933623, so dass sie in den Tabellen7 als Term 14933623 + 13# × n, n = 0…12 aufgeführt wird. Die längste zur Zeit bekannte arithmetische Primzahlfolge ist AP26 8 : 43142746595714191 + 23681770 · 23# · n, für n = 0…25.
Anmerkungen und Literatur
| 1 | Eine gut verständliche Einführung in die Materie ist der Artikel „Arithmetische Primzahlfolgen beliebiger Länge“ von Christoph Pöppe, Spektrum der Wissenschaft, April 2005, S. 114 |
| 2 | Hardy, G. H. and Littlewood, J. E.: Some Problems of ‚Partitio Numerorum.‘ III. On the Expression of a Number as a Sum of Primes. Acta Math. 44, 1-70, 1923. |
| 3 | Green, B. and Tao, T.: The Primes Contain Arbitrarily Long Arithmetic Progressions. Preprint. 8 Apr 2004. http://arxiv.org/abs/math.NT/0404188. |
| 4 | Die (natürliche) Zahl k modulo einer beliebigen Zahl n ist der Rest, der sich bei der Division von k durch n ergibt. k = 1 (mod n) bedeutet daher: Der Rest der Division von k durch n ist 1 (Eins). Beispiel: Die Zahl 31 ergibt, durch 30 dividiert, den Rest 1. Die mathematisch exakte Schreibweise ist 31 ≡ 1 (mod 30), gelesen „31 kongruent 1 modulo 30 “. Anstelle des Zeichens „ ≡ “ kann man aber auch ein Gleichheitszeichen setzen und entsprechend lesen „31 gleich 1 modulo 30 “. Den Divisor 30 nennt man in diesem Zusammenhang den Modul. |
| 5 | Rune Mields: „Das Sieb des Eratosthenes III “, 1977. Abgebildet in: Guderian, Dietmar: Mathematik in der Kunst der letzten 30 Jahre. Ebringen i. Br., Bannstein-Verlag, 1990 |
| 6 | Guderian, Dietmar: Mathematik in der Kunst der letzten 30 Jahre. Ebringen i. Br., Bannstein-Verlag, 1990 |
| 7 | Siehe z. B. Jens Kruse Andersen :http://users.cybercity.dk/~dsl522332/math/aprecords.htm#history |
| 8 | Entdeckt am 12. April 2010 von Benoit Perichon , siehehttp://users.cybercity.dk/~dsl522332/math/aprecords.htm |