Magisches Quadrat der Ordnung 42 aus dritten Potenzen von Primzahlen
Magisches
Quadrat der Ordnung 44 aus vierten Potenzen
Im Jahr 2007 fanden Jaroslaw Wroblewski (Universität von Wroclaw, Polen) and Hugo Pfoertner (MTU Aero Engines, Deutschland) die Lösung dieser beiden interessanten und sehr schwierigen Probleme:
Ihr magisches Quadrat #1 ist die Lösung meines ungelösten Problems, das in der Zeitschrift The Mathematical Intelligencer im Jahr 2005 veröffentlicht wurde. Und ihr magisches Quadrat #2 ist mit einer Verringerung der Ordnung von 243 auf 44 eine gewaltige Verbesserung des bisherigen Rekords. Die folgenden fünf Abschnitte auf dieser Seite berichten über ihre Entdeckungen:
Das erste Problem und sein Kontext
Im Jahr 2005 habe ich die ersten bekannten aus Quadraten von Primzahlen gebildeten magischen Quadrate der Ordungen 4x4 und 5x5 im Anhang meines Artikels über magische Quadrate aus Quadratzahlen angegeben, der in der Zeitschrift The Mathematical Intelligencer veröffentlicht wurde:
29² |
191² |
673² |
137² |
71² |
647² |
139² |
257² |
277² |
211² |
163² |
601² |
653² |
97² |
101² |
251² |
11² |
23² |
53² |
139² |
107² |
13² |
103² |
149² |
31² |
17² |
71² |
137² |
47² |
67² |
61² |
113² |
59² |
41² |
97² |
83² |
127² |
29² |
73² |
7² |
109² |
Was ist schwieriger zu finden als magische Quadrate aus Quadratzahlen? Magische Quadrate aus Kubikzahlen! Das war der Grund, warum als Teil der 10 ungelösten Probleme in meinem Artikel folgende Frage gestellt wurde:
Ungelöstes Problem 6 - Konstruieren Sie ein magisches Quadrat aus dritten Potenzen von Primzahlen.
Zwei Jahre nach seiner Veröffentlichung sind jetzt Wroblewski und Pfoertner die ersten, die eine Lösung dieses Problems finden!
Das zweite Problem und sein Kontext
Seit Leonhard Euler im Jahr 1770 ein 4x4 magisches Quadrat aus Quadratzahlen fand, und später Edouard Lucas im Jahr 1876 erfolglos nach einem 3x3 magischen Quadrat aus Quadratzahlen suchte, wissen wir, dass die Suche nach dem kleinstmöglichen aus Potenzen gebildeten magischen Quadrat ein extrem schwieriges Problem darstellt, egal welche Potenz man betrachtet: DERZEIT KENNEN WIR FÜR KEINE POTENZ > 1 DAS KLEINSTMÖGLICHE MAGISCHE QUADRAT! Wir wissen nicht einmal, ob ein 3x3 magisches Quadrat aus Quadratzahlen möglich ist. Wir wissen auch nicht, ob magische Quadrate aus Kubikzahlen der Ordnungen 4x4, 5x5, 6x6, 7x7 oder 8x8 möglich sind, und so weiter...
Vor dem Wroblewski-Pfoertner-Quadrat stammte das kleinste bekannte magische Quadrat aus vierten Potenzen aus dem 243x243 tetramagischen Quadrat von Pan Fengchu (siehe Multimagische Rekorde): Wenn die Einträge eines tetramagischen Quadrats quadriert werden, oder deren dritte oder vierte Potenz gebildet wird, bleibt ja die magische Eigenschaft jeweils erhalten.
Magisches Quadrat |
Kleinstes mögliches |
Kleinstes bekanntes |
aus Quadratzahlen |
Unbekannt! Eventuell 3x3? |
4x4 (L. Euler, 1770) |
aus Kubikzahlen |
Unbekannt! Eventuell 4x4? |
9x9 (C. Boyer, 2006) |
aus 4. Potenzen |
Unbekannt! |
243x243 (aus
dem tetramagischen Quadrat |
aus 5. Potenzen |
Unbekannt! |
729x729
(aus dem pentamagischen Quadrat |
Wenn wir uns um die Diagonalen nicht kümmern (was semi-magische anstelle von magischen Quadraten bedeutet), dann kennen wir einige Antworten auf die Frage nach den kleinstmöglichen Größen der Quadrate. So kennen wir z.B. semi-magische 3x3-Quadrate aus Quadratzahlen und semi-magische 4x4-Quadrate aus Kubikzahlen. Zu unserem hier betrachteten Problem mit vierten Potenzen kennen wir 4x4, 8x8, 9x9 semi-magische Quadrate.
141014 |
9384 |
9314 |
377624 |
358664 |
208814 |
210384 |
133934 |
248064 |
301914 |
304184 |
92634 |
4134 |
320264 |
317874 |
11064 |
Die Kluft zwischen dem kleinsten semi-magischen und dem kleinsten magischen Quadrat aus vierten Potenzen war unglaublich groß: 4x4 im Vergleich zu 243x243. Mein Frage auf dieser Webseite war folgende:
Wroblewski and Pfoertner sind die ersten, die dieses Problem lösen!
Wroblewskis Beitrag über semi-magische Lösungen
Jaroslaw
Wroblewski (Wroclaw 1962 -)
auf der "LVII Olimpiada Matematyczna" in Polen, im Jahr
2006. Zum Vergrößern auf das Bild klicken.
Jaroslaw Wroblewski & Jean-Charles Meyrignac waren das Siegerteam des Al Zimmermann's programming contest im März-Mai 2007 mit dem Thema "Suche nach Kurchan pan-diagonalen multiplikativen Quadraten". Sie siegten in allen drei Teilen des Wettbewerbs: Siehe dazu http://www.recmath.org/contest/Kurchan/index.php. Zuvor, im Februar 2006, war Jaroslaw Wroblewski der erste, dem es gelang, ein bi-magisches Quadrat mit einer Größe unter 8x8 zu finden: Ein lange erwartetes Ergebnis, seit 1890! Hier ist es zu sehen: 6x6 bi-magisches Quadrat.
Indem er sein im Al Zimmermann's Wettbewerb siegbringendes Rechenprogramm mit Anpassungen für die beiden genannten Probleme wiederverwendete, konnte er zwei entsprechende semi-magische Quadrate produzieren. Das Ergebnis lag am 6.Juni 2007 vor. Er bemerkt dazu: "Ein Nebenprodukt des Wettbewerbs".
Einige seiner Kommentare zur Methode zur Bestimmung von S42.TXT:
1) Wähle die Primzahlen derart aus, dass eine ganzzahlige magische Summe
(Summe_der_Primzahlen)/(Matrixgröße) erreicht wird, und dass diese
dieselbe Parität wie die Quadratgröße hat. (Primzahlen sind ungerade).
2) Wähle eine zufällige Startanordnung und optimiere davon ausgehend.
Mein Verfahren nimmt zwei Zeilen und tauscht zwischen diesen beiden Zeilen
einige Einträge derart aus, dass deren Spaltenpositionen erhalten bleiben
und dass die Summe der Einträge einer der beiden Zeilen so nahe wie möglich an
die magische Summe herankommt. Alternativ werden zwei Spalten gewählt und die
Optimierung wird analog auf diese angewandt. Offenbar konvergiert dieses Verfahren
in Richtung auf ein semi-magisches Quadrat, wenn die Einträge der Matrix mit einigem
Abstand unter 2^(Matrixgröße) liegen. Im Augenblick kann ich Matrixgrößen bis 51
behandeln. Etwas größere Dimensionen wären möglich; dazu müsste aber
ein anderes Programm geschrieben werden.
Ich habe die starke Überzeugung, dass es möglich ist, Reihen und Spalten so
zu permutieren, dass beide Diagonalen magisch werden, aber im Augenblick habe ich
dafür kein geeignetes Rechenprogramm.
Diese semi-magischen Quadrate sind noch keine magischen Quadrate. Wer kann die beiden magischen Diagonalen finden? Diese schwierige Aufgabe wird von Hugo Pfoertner gelöst.
Pfoertners abschließender Beitrag über die Diagonalen
Hugo Pfoertner (Rosenheim 1950 -)
Photo bei einer Konferenz der NATO
Research and Technology Organization, Budapest, 2005. Zum Vergrössern auf das Bild klicken.
Wie Jaroslaw Wroblewski erreichte auch Hugo Pfoertner hervorragende Platzierungen beim gleichen Durchgang des Al Zimmermann's Programmierwettbewerbs. Er belegte die Plätze 13 in der Maximal-Teilaufgabe, 5 in der Minimal-Teilaufgabe und 4 in der Kurchan-Teilaufgabe. Hugo ist im Entwicklungsbereich von MTU Aero Engines in Deutschland tätig. In seiner Freizeit macht es ihm Spaß, mit Computern nach der Lösung mathematischer Probleme zu suchen: Siehe dazu www.pfoertner.org.
Das Auffinden zweier magischer Diagonalen in einem semi-magischen Quadrat ist eine sehr schwierige Aufgabe. Man muss sich vorstellen, dass es in einem 44x44 semi-magischen Quadrat immerhin 44! = 2.66*10^54 mögliche Diagonalen gibt, und dass die Wahrscheinlichkeit dafür, dass die beiden einander kreuzenden Diagonalen beide die korrekte Summe erhalten, die beim 44x44-Problem den riesigen Wert 123784061778806 hat, extrem klein ist.
Hugo Pfoertner begann mit dem kleineren Quadrat, 42x42, und fand nach einem Monat, am 9. Juli 2007, eine Lösung mit den passenden beiden Diagonalen: Das erste Problem war gelöst! Für dieses erste gefundene Quadrat liefen 10 CPUs (Itanium-2 oder 3.4GHz Pentium) ca. 4 Wochen lang.
Und am 8 Oktober 2007 erhielt ich von Hugo die folgende Nachricht:
Das 44x44 Problem mit vierten Potenzen ist jetzt gelöst. Es hat ziemlich
massive Rechenleistung benötigt, die erforderlichen Permutationen zu finden.
Die Suche nach einer passenden Diagonale mittels Zeilenvertauschungen begann am 11. Juni
und produzierte eine passende Matrix am 27. August. Mit dieser Matrix als
Startlösung wurden dann simultane Zeilen- und Spaltenvertauschungen durchgeführt,
die schließlich am 7. Oktober auf eine Matrix mit passender Anti-Diagonale führten.
Während der meisten Zeit lief das Permutationsprogramm auf 57 Prozessoren eines 5 Jahre alten
SGI-Rechners http://www.sgi.com/products/remarketed/origin3000.
Dieser Rechner, dessen Ausserdienststellung geplant war, war zuvor eines
der Arbeitspferde in MTUs F&E-Bereich. Wegen des geplanten Abbaus war
nur mehr eine geringe reguläre Auslastung auf der Maschine verblieben. Zusätzlich konnte die Leerlaufzeit auf 14 Prozessoren von SGI Altix Rechnern genutzt werden.
http://www.sgi.com/products/remarketed/altix350.
Die akkumulierte CPU-Zeit, um eine Matrix mit passender Diagonale zu finden, betrug 148 Monate
auf den Origin 3000 Prozessoren und 22.4 CPU-Monate auf den Itanium-2 Prozessoren der
Altix Rechner. Um eine passende Anti-Diagonale zu finden, wurden
80 CPU-Monate auf der Origin 3000 and 17.5 CPU-Monate auf den Altix 350-Rechnern benötigt.
In Summe wurden 18.8 CPU-Jahre auf der Origin 3000 und 3.3 CPU-Jahre auf Altix 350 verbraucht.
Das gefundene magische Quadrat ist vermutlich eines der aufwändigeren Exemplare seiner Art ;-)
Hugo Pfoertner dankt seinem Arbeitgeber, der Firma MTU Aero Engines, dafür, dass er diese leistungsfähigen Ressourcen nutzen konnte.
Die Lösungen mit den beiden magischen Quadraten
Das sind die beiden hervorragenden und eindrucksvollen Wroblewski-Pfoertner-Quadrate:
Mit ihrem ersten Quadrat ist mein Ungelöstes Problem 6 jetzt gelöst. Und mit ihrem zweiten Quadrat ist es jetzt möglich, die oben angegebene Tabelle der Rekorde zu aktualisieren:
Magisches Quadrat |
Kleinstes mögliches |
Kleinstes bekanntes |
aus Quadratzahlen |
Unbekannt! Eventuell 3x3? |
4x4 (L. Euler, 1770) |
aus Kubikzahlen |
Unbekannt! Eventuell 4x4? |
9x9 (C. Boyer, 2006) |
aus 4. Potenzen |
Unbekannt! |
44x44 (J. Wroblewski - H. Pfoertner, 2007) |
aus 5. Potenzen |
Unbekannt! |
729x729
(aus dem pentamagischen Quadrat |
Vielleicht werden jetzt auch andere versuchen, diese Ergebnisse mit Quadraten zu verbessern, die kleiner sind als 44x44 oder 42x42? Falls ja, bitte ich um eine Nachricht!
Als (vorläufiges?) Fazit einige Anmerkungen von Jaroslaw:
Wir wissen, dass ein 12x12 magisches Quadrat aus dritten Potenzen von Primzahlen existiert,
aber der Beweis liefert kein Konstruktionsverfahren (man verwendet das bekannte trimagische
12x12; nimmt 144 Primzahlen in arithmetischer Folge, deren Existenz aus dem
Green-Tao-Satz folgt;
dann ersetzt man jede Zahl 'n' im trimagischen 12x12 durch den n-ten Term der arithmetischen Folge).
Im Augenblick sehe ich nicht, wie man die Größe 42x42 des jetzt bekannten Beispiels mit der
Vorgehensweise, die ich angewandt habe, wesentlich verringern könnte.
WICHTIG! Im August 2008 hat sich obiger Status geändert, durch neuere kleinere magische Quadrate aus Kubikzahlen, Quadrate der 4. Potenz und Quadrate der 5. Potenz! Sehen sie hier.
Zurück zur Homepage http://www.multimagie.com