Primzahlen Quadrat < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:49 So 09.01.2011 | | Autor: | Ferma |
Hallo,
mit 30 Primzahlen soll ein magisches Quadrat 6. Ordnung erstellt werden. Die fehlenden 6 Zahlen werden mit 0 ergänzt. Ich habe ein Makro in VBA geschrieben. Anscheinend gibt es zu viele Möglichkeiten. Nach 12 Stunden habe ich abgebrochen. Hat jemand Erfahrung in dieser Richtung?
Viele Grüße
Ferma
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:00 So 09.01.2011 | | Autor: | abakus |
> Hallo,
> mit 30 Primzahlen soll ein magisches Quadrat 6. Ordnung
> erstellt werden. Die fehlenden 6 Zahlen werden mit 0
> ergänzt. Ich habe ein Makro in VBA geschrieben.
> Anscheinend gibt es zu viele Möglichkeiten. Nach 12
> Stunden habe ich abgebrochen. Hat jemand Erfahrung in
> dieser Richtung?
> Viele Grüße
> Ferma
Hallo,
es wäre natürlich interessant gewesen, den Grundansatz zu deinem Makro zu erfahren. Hast du "einfach so" mit einer Primzahlenliste rumprobiert?
Hast du in irgend einer Weise berücksichtigt, dass Primzahlen (mit Ausnahme von 2 und 3) die Form 6k+1 oder 6k-1 haben?
Gruß Abakus
|
|
|
| |
|
Hallo Ferma,
hast Du Dir diese Aufgabe selbst gestellt? Warum dann die sechs Nullen?
Gibt es für die eine Sonderbedingung (z.B. das Damenproblem, oder etwa sudokuartig)?
Ich habe mit solchen Dingen auch herumgespielt, vor langer Zeit. Rein gefühlsmäßig würde ich sagen, dass es nicht nur viele, sondern wahrscheinlich unendlich viele Lösungen gibt, sofern es überhaupt eine gibt. Dazwischen scheint nicht viel zu liegen.
Und warum hast du nach 12 Stunden abgebrochen? Weil der Output ausuferte, oder weil es bis dahin keinen gab?
Hast Du das (triviale) Kriterium berücksichtigt, dass die Summe aller verwendeten Primzahlen ein Vielfaches von 6 sein muss? Was ist die Struktur Deines Makros? (um die Fragen von abakus nochmal aufzugreifen  )
Etwas mehr Information wäre hilfreich, vor allem zur Intention der Frage "hat jemand Erfahrung in dieser Richtung?".
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:00 So 09.01.2011 | | Autor: | Ferma |
Hallo,
hier mein Ansatz:
k = 421
F = Array(19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, _
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157)
For Each a1 In F
For Each a3 In F
If Vers(Array(a1, a3)) Then
For Each a4 In F
If Vers(Array(a1, a3, a4)) Then
For Each a5 In F
If Vers(Array(a1, a3, a4, a5)) Then
For Each a6 In F
If Vers(Array(a1, a3, a4, a5, a6)) And a1 + a3 + a4 + a5 + a6 = k Then
Vers ist eine Funktion, die auf Ungleichheit prüft. k ist die Summe der Zeilen, Spalten und Hauptdiagonalen. Ich habe diese Aufgabe so in einem Medium gefunden. Seit 2 Wochen arbeite ich daran. Die Summe der Zahlen ist teilbar durch 6(2526/6=421) Es gibt 1367 mögliche 5-er Kombinationen. Um diese ihrerseits je 6 zu kombinieren, das ergibt einige Billiarden Möglichkeiten. Der Weg ist für mich vorrangig, nicht das Ergebnis. Es soll viele Lösungen geben. Vielleicht verlange ich diesmal zu viel?!
Gruß, Ferma
|
|
|
| |
|
Hallo Ferma,
ah, es gibt vorgegebene Zahlen. Ich dachte, es ginge um 30 beliebige Primzahlen.
Es gibt [mm] \bruch{36!}{6!} [/mm] Möglichkeiten, diese Zahlen im Quadrat anzuordnen, mehr als [mm] 5*10^{38}.
[/mm]
Diese Zahl ist mit brute-force-Methoden nicht mehr handhabbar, du würdest viel länger rechnen als 12 Stunden...
Eine erhebliche Einschränkung ist die bekannte Summe jeder Zeile und Spalte, aber obwohl sie den größten Einfluss hat, dürfte nur schwer anzugeben sein, wie weit die Beschränkung geht.
Genauer anzugeben sind aber ein paar Symmetriebetrachtungen. Es gebe folgende Operationen:
1) Drehung des Quadrats um 90°
2) Spiegelung an der mittleren senkrechten Achse
3) Spiegelung an der Diagonalen von links oben nach rechts unten
4) Vertauschung zweier beliebiger Spalten
5) Vertauschung zweier beliebiger Zeilen
Nennen wir zwei Lösungen nun unabhängig voneinander (oder verschieden), wenn sie durch keine Folge dieser Operationen ineinander überführt werden können.
Diese Überlegung erlaubt uns, nun ohne Beschränkung der Allgemeinheit (oBdA) folgendes festzulegen:
a) Die Zahl in der linken oberen Ecke ist die 19.
b) In der ersten Zeile des Quadrats sind die Zahlen aufsteigend von links nach rechts angeordnet, etwaige Nullen stehen am Ende der Zeile (also rechts).
c) In der ersten Spalte des Quadrats sind die Zahlen aufsteigend von oben nach unten angeordnet, etwaige Nullen stehen am Ende der Spalte (also unten).
d) Die zweite Zahl der ersten Zeile ist kleiner als die zweite Zahl der ersten Spalte.
Mit dieser Festlegung finden wir nun nur noch Lösungen, die unabhängig voneinander sind. Zugleich finden wir alle solchen Lösungen.
Übrigens tragen die Symmetriebetrachtungen bzw. Umformungen zu keiner allzu erheblichen Einsparung bei. Es ist zwar nur noch [mm] \bruch{1}{2^2*(6!)^2}=\bruch{1}{2073600} [/mm] der insgesamt möglichen Kombinationen zu betrachten, aber auch das reduziert deren Zahl ja erst einmal nur auf etwa [mm] 2,5*10^{32}.
[/mm]
Trotzdem wirst Du feststellen, dass durch die Festlegung der Zeilen- und Spaltensumme allein der ersten Zeile und ersten Spalte die Möglichkeiten ganz erheblich beschränkt sind.
Alle anderen Zeilen und Spalten außer den jeweils ersten müssen übrigens nicht geordnet sein!
Ich hoffe, das hilft Dir weiter, Deinen Algorithmus erheblich zu beschleunigen.
Viel Erfolg!
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:46 So 09.01.2011 | | Autor: | Ferma |
Hallo,
die Anzahl der 6-er Kombinationen aus 36(30 Primzahlen und 6 Nullen), welche die Bedingung =421 erfüllen, ist 8262. Um alle Möglichkeiten zu testen, müsste man 6 aus 8262 ohne Zurücklegen berechnen. Das sind dann ca.4,4*10^20. Geteilt durch Deine Zahl (2073600) gibt das 2,1*10^14 Möglichkeiten. Immerhin...Aber viel weiter gekommen bin ich nicht, mit meinem Problem ;)
VG
Ferma
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:26 So 09.01.2011 | | Autor: | reverend |
Hallo Ferma,
doch, damit bist du schon viel weiter.
Die Vorgehensweise ist nun wohl diese:
1) man ermittelt, beginnend mit der 19, die jeweils nächstkleinste Zahl, so dass genau die Summe 421 erreicht wird (ggf. mit Nullen auffüllen).
Das ist die erste Zeile. Festhalten.
2) dto., aber nur mit den jetzt noch zur Verfügung stehenden Zahlen, allerdings wieder beginnend mit der 19, und die zweite Zahl muss größer sein als die zweite Zahl der ersten Zeile.
Damit hat man die erste Spalte. Festhalten.
Ab hier wirds etwas vertrackter, wodurch allerdings die Rechenzeit insgesamt kurz wird, weil es eben immer weniger Möglichkeiten gibt.
3) Man ermittelt die "kleinste" zweite Zeile, deren erste Zahl ja bereits feststeht. Damit liegen fünf neue Zahlen fest.
4) Für jede dieser fünf Zahlen muss nun geprüft werden, ob zusammen mit der zweiten Zahl der ersten Zeile und vier noch "freien" Zahlen wieder die Summe 421 darstellbar ist, nämlich als zweite Spalte.
Die Verschachtelung geht entsprechend weiter: dritte Zeile und dritte Spalte (jeweils nur noch 4 Zahlen), vierte Zeile und vierte Spalte (noch je 3), fünfte Zeile und Spalte. Schluss.
Du wirst feststellen, dass Du "meistens" schon nach dem vierten oder fünften Schritt nicht mehr weiterkommst und wieder eine Ebene höher zurücksteigst.
Die sechste Zeile und Spalte erledigen sich von selbst, da ist ja nur noch die Ecke unten rechts mit der letzten übrigen Zahl zu füllen, und auch die Summen sind dann gesichert.
Ich würde behaupten, dass man auf diesem Weg selbst ohne Computer innerhalb etwa ein, zwei Stunden eine Lösung findet, und mit einer vernünftigen rekursiven Programmierung schätze ich die Laufzeit für die Ermittlung aller Lösungen auf einem gewöhnlichen PC auf deutlich unter einer Stunde.
Noch eine kombinatorische Bemerkung:
> die Anzahl der 6-er Kombinationen aus 36(30 Primzahlen und
> 6 Nullen), welche die Bedingung =421 erfüllen, ist 8262.
> Um alle Möglichkeiten zu testen, müsste man 6 aus 8262
> ohne Zurücklegen berechnen.
Nein, weil es ja im Quadrat sechs solche Zeilen geben muss. Dann sind es nur 1377 mögliche Kombinationen. Allerdings wissen wir noch nicht viel über deren Anordnung, außer dass die Kombination mit der 19 in die erste Zeile gehört und in der Ordnung feststeht, und dass alle Spalten wieder die Summe 421 haben müssen, und dass die erste Spalte geordnet ist. Und noch die Bedingung [mm] a_{21}>a_{12}. [/mm] Da wird das Sieben nicht lange dauern, obwohl vorerst jede der 1377 Zusammenstellungen in fünf Zeilen noch permutiert werden kann, aber eben nur mit einigen Nebenbedingungen.
So hätte man höchstens [mm] 1377*(6!)^5 [/mm] Prüfungen vorzunehmen, aber wie gesagt, werden die weiteren Einschränkung diese Zahl (ca. [mm] 2,7*10^{17}) [/mm] rapide beschneiden.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:22 So 09.01.2011 | | Autor: | felixf |
Moin,
> Ich habe mit solchen Dingen auch herumgespielt, vor langer
> Zeit. Rein gefühlsmäßig würde ich sagen, dass es nicht
> nur viele, sondern wahrscheinlich unendlich viele Lösungen
> gibt, sofern es überhaupt eine gibt. Dazwischen scheint
> nicht viel zu liegen.
es gibt immer eine, also bei "normalen" magischen Primzahlquadraten, egal welcher Groesse (also ausser $2 [mm] \times [/mm] 2$). Das folgt laut ![[]](/images/popup.gif) Wikipedia aus dem Satz von Green und Tao.
Dass es dann unendlich viele gibt finde ich auch nicht ueberraschend. Ich vermute, das folgt ebenfalls aus Green-Tao (man fuegt einfach zusaetzliche Bedingungen hinzu, die die bisherigen Loesungen ausschliessen, und bekommt damit dann weitere Loesungen). Das muesste man sich aber mal genauer anschauen...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:29 So 09.01.2011 | | Autor: | reverend |
Hallo Felix,
danke für den Hinweis. Das kannte ich bisher nur unbewiesen (Vermutung von G.H.Hardy, meine ich). Die Tatsache an sich wundert mich allerdings wenig.
Liebe Grüße
reverend
|
|
|
|
