Skip to content

Fadenspiele und das Einmaleins im Kreis

Es ist ein hübsches Spiel für geduldige Kinder: Auf einer Holzplatte ist ein Kreis aufgezeichnet, und auf dem Umfang dieses Kreises sind in gleichmäßigen Abständen p – 1 Nägel eingeschlagen, wobei p in der Größenordnung von einigen Hundert liegt und am besten eine Primzahl ist. Die Nägel n sind fortlaufend nummeriert. Die Aufgabe besteht darin, für alle n von 1 bis p – 1 einen Faden von Nagel n zu Nagel 2n zu ziehen.

Ein Beitrag von Christoph Pöppe

Natürlich wird man das nicht der Reihe nach für n = 1, 2, 3, … machen, sondern in der Reihenfolge 1, 2, 4, 8, … Dann muss man nämlich nicht jedes Mal den Faden abschneiden und festknoten. Wer den Faden zieht, kommt ziemlich bald, nämlich wenn die erste Zweierpotenz den Wert p überschreitet, in die Verlegenheit, modulo p zu rechnen. Das wiederum wird durch die kreisförmige Anordnung der Nägel nahegelegt. Und wenn p nicht gerade eine Zweierpotenz plus 1 ist, dann findet der Faden erst dann zum Nagel 1 zurück, wenn er bereits alle anderen Nägel genau einmal besucht hat. Wieso?

Der Weg des Fadens wird periodisch Wenn der Faden einen nach n Schritten

Wenn der Faden einen nach n Schritten schon besuchten Nagel nach m Schritten nochmals trifft, dann ist 2m = 2n mod p, woraus 2m – n = 1 mod p folgt. Also wäre der Weg des Fadens bereits nach m–n Schritten periodisch. Erst wenn alle anderen Nägel bereits abgegrast sind, bleibt dem Faden nichts anderes übrig, als wieder bei Nagel 1 zu landen. Ja, diese Argumentation läuft auf einen Beweis des kleinen fermatschen Satzes hinaus. Mit einem echten Faden ist man selbst für mäßig große Werte von p eine gute Weile beschäftigt. Weniger geduldige Menschen setzen dafür den Computer ein. Es hilft der Übersicht, wenn man das Fadenstück von einem Nagel zum nächsten in Abhängigkeit von seiner Länge einfärbt.

Bild 1: Für b = 2 sind die Striche von n nach bn Tangenten an eine Kardioide (schwarze Kurve). Dabei kommt es auf den Wert von p (hier 401) nicht besonders an.

Literatur-Tipp

Christoph Pöppe: „Das Einmaleins im Kreis.“ Spektrum der Wissenschaft 7/2022, S. 74–79,

Simon Plouffe: „The shape of bn mod p.“

So entstehen Kardioiden

Was einem beim – echten oder virtuellen – vollendeten Fadenbild ins Auge springt, ist eine hübsche Kurve: die Kardioide, auch „Herzkurve“ genannt (s. Bild 1). Bemerkenswerterweise ist die Kurve selbst nicht Bestandteil des Bildes; vielmehr sind die einzelnen Fadenstücke Tangenten an die Kurve.

So entstehen Epizykloiden

Eine Verallgemeinerung bietet sich an: Man ersetzt den Multiplikator 2 durch eine beliebige natürliche Zahl b. Bereits bei den ersten Versuchen stellt sich heraus: Aus der Kardioide mit der einen nach innen gerichteten Spitze werden Kurven mit b – 1 Spitzen. Es handelt sich um Epizykloiden; das sind die Kurven, die ein am Umfang eines Kreises befestigter Bleistift aufs Papier zeichnet, wenn dieser Kreis auf einem anderen Kreis abrollt. Mit wachsendem b wird der Innenkreis immer größer und der auf ihm abrollende Außenkreis entsprechend immer kleiner, sodass die immer zahlreicheren einwärts gerichteten Spitzen zu einer kaum noch sichtbaren Girlande am Rand des großen Kreises verkümmern. Stattdessen tauchen im Inneren des Kreises neue Strukturen auf, die auf den ersten Blick an gotische Spitzbögen erinnern (s. Bild 2 und Bild 3).

Bild 2: Die Potenzen der Primzahl b = 331 modulo der Primzahl p = 10.037
Bild 3: Für b = 150 und p = 1.009 fällt die an den Rand gedrängte Rollkurve kaum noch auf
Bild 4: Für p = 1.001 und b = 78 ist b – 1 ein Teiler von p, denn 1.001/77 = 13. Dadurch kommt das Muster konzentrischer Kreise zustande.

So entstehen konzentrische Kreise

Mit der Struktur von bn modulo p hat sich der französische Mathematiker Simon Plouffe intensiv befasst. Wenn b – 1 ein Teiler von p ist, es also eine natürliche Zahl k gibt, sodass p = k(b – 1) ist, dann entsteht ein Muster von konzentrischen Kreisen (s. Bild 4). Doch warum ist das so? Wir schreiben die Zahl n zur Basis k, genauer: als ku + v, wobei v zwischen 0 und k–1 liegt. Die Differenz bn – n = (b – 1)n schreibt sich dann folgendermaßen: (ku + v)(b – 1) = k(b – 1)u + v(b – 1) = pu + v(b – 1) Modulo p gerechnet, fällt der erste Term weg, also kommen für die Differenz bn – n überhaupt nur k verschiedene Werte vor, einer für jeden Wert von v. Die Differenz bn – n ihrerseits bestimmt die Länge des Strichs im Einheitskreis und diese wiederum dessen minimalen Abstand vom Kreismittelpunkt. Diese minimalen Abstände sind die Radien der Kreise, die so auffällig ins Auge springen.

So entstehen überlagerte Rollkurven

Setzen wir jetzt b eins höher, so ergibt sich ein deutlich erkennbares Spitzbogenmuster (s. Bild 5). Auch für diesen Fall hilft die Zerlegung von n zur Basis k. Wenn man nämlich jeden Strich entsprechend seinem v-Wert einfärbt, stellt sich heraus, dass das ganze Muster in k gegeneinander verdrehte Kardioiden zerfällt, eine für jeden Wert von v. Wenn man b weiter erhöht, wird aus der Kardioide eine zweispitzige Rollkurve, dann eine dreispitzige und so weiter. Wenn man also von allen möglichen Werten von n nur jeden k-ten verwendet, passt das Muster in das Schema mit den einfachen Rollkurven, das für kleine Werte von b funktioniert. Andere Muster entsprechen merkwürdigerweise einem b-Wert von zum Beispiel 2/3, was auf einen Kreis hinausläuft, der den festen Kreis umgibt und mit seiner Innenseite an ihm entlangrollt. Weitere Erklärungsmöglichkeiten harren noch ihrer Entdeckung. Simon Plouffe hat aus seiner reichhaltigen Bildersammlung ein paar Erfahrungsregeln hergeleitet, aber noch keine Begründung dafür. Es bleibt also noch viel auszuprobieren.

Bild 5: Für p = 1.001 und b = 79 besteht das Muster aus 13 Teilen, die von je einer Kardioide eingehüllt werden. Das tritt deutlich zutage, indem die Striche für alle durch 13 teilbaren Werte von n rot und im Übrigen blau gefärbt werden.

Fadenspiele und Kryptografie

Bemerkenswerterweise hat dieses Spiel mit merkwürdigen Mustern eine Beziehung zur modernen Kryptografie. Zu gegebenen Werten von b und p ist die Funktion f(n) = bn mod p relativ einfach auszurechnen, deren Umkehrung (der „diskrete Logarithmus“) dagegen sehr schwer: Es gibt praktisch keine bessere Möglichkeit, als alle Werte von n der Reihe nach durchzuprobieren. Eine leicht zu berechnende Funktion, deren Umkehrung in akzeptabler Zeit nicht zu finden ist, heißt „Falltürfunktion“; auf solchen Funktionen beruhen zahlreiche Verschlüsselungsverfahren. Dort geht es allerdings um p-Werte in der Größenordnung 21.000. Auch in diesem Fall gibt es für kleine b die bekannten Fadenmuster. Aber die Möglichkeit, dass es von diesen Ausnahmen abgesehen Strukturen im Fadenbild gäbe, die die Berechnung des diskreten Logarithmus vielleicht abkürzen könnten, kann man getrost ausschließen.

Zum Weiterlesen

Tatsächlich gibt es Künstler*innen, die sich die Mühe eines Fadenspiels machen, einer von ihnen ist John Eichinger:

Hier lassen sich Fadenspiele online erstellen:

Beitrag teilen:

Facebook
Twitter
LinkedIn
Pinterest
XING
WhatsApp
Email

Ähnliche Beiträge

Header_MZ Blogbeitrag_04-2023 (11)
28. Mai, 2024
Inmitten der fortschreitenden Debatte über nachhaltige Mobilität ist der Verbrennungsmotor nach wie vor ein zentraler Akteur auf deutschen Straßen und macht den Verkehrssektor zu einem der größten CO2-Verursacher. Um den Klimawandel zu stoppen, müssen wir den CO2-Ausstoß jedoch reduzieren. Die Nutzung erneuerbarer Energien wie Solarenergie, Windenergie, Wasserkraft und Geothermie anstelle von fossilen Brennstoffen könnte genau dazu beitragen. Der Verkehrssektor könnte durch die Umstellung von Verbrennungsmotoren auf Elektroantriebe oder sogenannte E-Fuels nahezu emissionsfrei sein und somit die Umwelt und das Klima schützen und das Leben auf unserem Planeten nachhaltiger gestalten.
Blogbeitrag_Fachkräftemangel
14. Mai, 2024
Obwohl die Digitalisierung ist in den letzten Jahrzehnten viele Bereiche unseres Lebens verändert hat, ist die Integration digitaler Technologien in Bildungseinrichtungen noch nicht so weit fortgeschritten, wie es sich so manche Lehrkraft und so manche Schüler:in wünschen würde. Dabei werden ebendiese Schüler:innen von heute die IT-Fachkräfte von morgen sein.
TED-Talk_Bildung_Header_1920x1080
28. Februar, 2024
Wenn wir uns für ein bestimmtes Thema interessieren und dazu unser Wissen erweitern möchten, ist unsere erste Anlaufstelle oft das Internet, gefolgt von Podcasts, Wissensvideos oder Sachbüchern. TED Talks haben in den vergangenen Jahren in Deutschland zwar sicherlich an Bekanntheit gewonnen, fristen jedoch verglichen mit ihrer Popularität in englischsprachigen Ländern wie den USA oder Großbritannien noch immer ein Schattendasein – das jedoch völlig zu Unrecht.
Header_MZ Blogbeitrag_04-2023 (4)
11. Januar, 2024
Es ist ein hübsches Spiel für geduldige Kinder: Auf einer Holzplatte ist ein Kreis aufgezeichnet, und auf dem Umfang dieses Kreises sind in gleichmäßigen Abständen p – 1 Nägel eingeschlagen, wobei p in der Größenordnung von einigen Hundert liegt und am besten eine Primzahl ist. Die Nägel n sind fortlaufend nummeriert. Die Aufgabe besteht darin, für alle n von 1 bis p – 1 einen Faden von Nagel n zu Nagel 2n zu ziehen.
Header_MZ Blogbeitrag_04-2023
20. Dezember, 2023
Seit ein Artikel in der New York Times im Dezember 2017 über ein geheimes Programm zur Erforschung von unbekannten Luftphänomenen (UAP) im US-Verteidigungsministerium berichtete, häufen sich die Nachrichten zu UAP. Ein ehemaliger Geheimdienstoffizier sagte nun vor dem Kongress aus, dass die USA sogar im Besitz „intakter, nicht menschlicher Technologie“ seien. Sollte uns eine außerirdische Intelligenz besuchen, könnte diese Erkenntnis die Menschheit jedoch in eine kosmische Krise stürzen.
Header_Entdeckt_02-2023 (20)
5. Dezember, 2023
Albert Einsteins Relativitätstheorie dient heute als Werkzeug: Erstmals wurde die Masse eines Sterns anhand der Deformation seiner Raumzeit ringsum gemessen. Schon 1912 hatte Einstein entdeckt, wie ein Stern durch seine Schwerkraft die Lichtstrahlen eines anderen, viel weiter entfernten Sterns geringfügig verbiegt. Weil der Ablenkwinkel winzig ist, schrieb er 1936, nachdem er diesen Gravitationslinseneffekt erneut untersucht hatte: „Selbstverständlich besteht keine Hoffnung, das Phänomen zu beobachten.“
Header_Entdeckt_02-2023 (14)
8. November, 2023
Mit Platz für sieben reguläre Besatzungsmitglieder und einer ununterbrochenen menschlichen Präsenz seit Oktober 2000 ist die Internationale Raumstation (ISS) die größte und erfolgreichste Raumstation aller Zeiten. Ihre Zukunft jedoch wird immer ungewisser.
Header_Entdeckt_02-2023 (4)
10. Oktober, 2023
Je größer die Frequenz einer schwingenden Klaviersaite, umso höher ist der Ton, den der Mensch hört. Allerdings steigt die Tonhöhe nicht gleichmäßig mit der Frequenz an, sondern wird vom Gehör logarithmisch abgeflacht.
Header_Entdeckt_02-2023 (3)
27. September, 2023
Der Tag hat noch gar nicht richtig angefangen, da haben wir schon tausend Dinge im Kopf: schnell anziehen, frühstücken, zur Arbeit hetzen … Kaum dort angekommen, füllt sich der Schreibtisch schneller als ein Fußballstadion beim Finale der Weltmeisterschaft. Der Kopierer streikt, das Meeting wurde vorverlegt und der Kaffee ist alle. Nach nur zwei Stunden Arbeit ist man direkt wieder reif für das Bett, weil man letzte Nacht schon wieder kaum geschlafen hat.
MZ-2023_Beitragsbild (1)
15. September, 2023
Digital First, Textverstehen zweitrangig? Der Eindruck könnte entstehen, wenn man das Leseverhalten von Jugendlichen und jungen Erwachsenen mit den Ergebnissen der empirischen Leseforschung kontrastiert. Denn die Leseforschung sagt, dass wir anspruchsvolle Sachtexte weniger gut verstehen, wenn wir sie digital lesen. Befragt nach ihren Lesegewohnheiten berichten aber Studierende, dass sie mehr als 80  Prozent ihrer Lesezeiten vor dem Bildschirm verbringen. Belletristik wird hingegen lieber auf Papier gelesen als auf dem E-Reader. Dabei gibt die Leseforschung mit Blick auf die narrativen Texte Entwarnung: Ein Nachteil ist mit der digitalen Lektüre nicht verbunden.
MZ-01-23_Beitragsbild BecksEcke
27. Juni, 2023
Ein raffiniertes Konzept könnte die elementarsten Arbeitsschritte eines Rechners auf eine völlig neue Grundlage stellen – aber das wird voraussichtlich nicht passieren.
MZ-02-23_Beitragsbild (4)
16. Juni, 2023
Viel Glück im neuen Jahr – das sollen die kleinen „Glücksklee“-Blumentöpfe verheißen, die alljährlich zu Silvester auf den Markt kommen. Tatsächlich handelt es sich dabei um Sauerklee (Oxalis tetraphylla) aus Mexiko, bei dem alle Blätter grundsätzlich aus vier Einzelblättchen bestehen. Ein Glücksklee (Trifolium repens) verdient aber seinen Namen gerade dadurch, dass er sich nur mit etwas Glück finden lässt. Die normalen Blätter von echtem Klee bestehen aus drei Blättchen, die fingerförmig angeordnet sind. Daher der wissenschaftliche Gattungsname Trifolium, also Dreiblatt. Bei nur einem von 5.000 Blättern sind vier Blättchen vorhanden – solche Seltenheiten gelten in vielen Kulturen als Glücksbringer. Ob Gene oder Umwelt zu Viererklees führen, wird schon seit Jahrzehnten diskutiert. Der Schlüssel zum Glück(sklee) ist zwar noch nicht gefunden, aber sein Versteck konnte eingegrenzt werden.