Forum: Wissenschaft
Rätsel der Woche: Harmonische Zahl gesucht
SPIEGEL ONLINE

Gibt es eine achtstellige Zahl, in der jede der Ziffern 1, 2, 3, 4 zweimal vorkommt - und in der sich diese acht Ziffern harmonisch aneinanderfügen?

Seite 2 von 5
turbokaktus 02.09.2018, 09:28
10.

Bis auf Spiegelungen gibt es für die 4_4 genau zwei Positionen, für die die anderen möglichen Besetzungen recht schnell nachgeprüft sind. Daher sind 41312432 und ihr Spiegelbild die einzigen Lösungen.

Beitrag melden
Strichnid 02.09.2018, 13:16
11.

Mein Ansatz war glaube auch recht simpel. Ich habe die drei Möglichkeiten, die 4en und 3en zu kombinieren (ohne Spiegelung, 4 immer vor 3) untersucht. Diese müssen sich zwangsläufig durchdringen:

1. 4 _ 3 _ _ 4 3 _
2. 4 _ _ 3 _ 4 _ 3
3. _ 4 _ 3 _ _ 4 3

Man erkennt sehr schnell, dass, wenn man nicht irgendwo eine 3 und 4 nebeneinanderschreibt, wo jeweils rechts und links Platz ist (wie in Variante 1.), es keine Möglichkeit gibt, die 2 _ _ 2 unterzubringen, sobald man die 1 _ 1 eingetragen hat.

Beitrag melden
sblz 02.09.2018, 15:35
12. Fallunterscheidung nicht vollständig?

Ich frage mich, ob die Fallunterscheidung, die Herr Dambeck vornimmt, vollständig ist: es muss ja schon noch die Variante betrachtet werden, dass eine der Vieren von zwei Einsen umgeben ist. Führt dann zwar auch zum Widerspruch, es gibt also keine Lösung mehr, aber gehört ja zur vollständigen Analyse dazu.

Beitrag melden
permissiveactionlink 02.09.2018, 17:44
13. Irgendwie beruhigend,

denn mit 16 Ziffern (0 bis F) klappt es offenbar diesmal bei sehr vielen Permutationen ! Es handelt sich zwar nicht um eine Langford-, sondern um eine Skolem-Sequenz (Elemente von 0 bis n-1 statt von 1 bis n), aber im hexadezimalen Fall gibt es immerhin 326.721.800 mögliche Lösungen (mit gespiegelten Sequenzen doppelt so viele). Was aber nur einen winziger Bruchteil aller möglichen derartigen Permutationen (32!/(2^17) = 2.007.528.968.305.156.937.921.280.000.000 , mit gespiegelten Sequenzen doppelt so viele) darstellt. 1,63*10^-22.

Beitrag melden
stenni 02.09.2018, 18:20
14. @permissiveactionlink: Da verwechseln Sie was

326.721.800 ist die Anzahl der Lösungen für die Langfordsequenz 1 - 16. Die Skolemsequenz 0 - 15 hat dagegen 700.078.384 Lösungen. Siehe mein bereits geposteter Link:
http://dialectrix.com/langford.html. Als alter Langford-Fan hab ich's schon vor Jahren selber per Programm geprüft: Es stimmt ;-)

Beitrag melden
IQ149 02.09.2018, 18:27
15. Erstaunlicherweise (#13)

ist 326.721.800 auch die Anzahl der tatsächlichen Lösungen für das Langford-Problem mit den Zahlen 1 bis 16, also L (16, 2), wie man z. B. unter dem Link aus Beitrag #2 nachlesen kann. Hier allerdings in dezimaler Schreibweise, nicht in hexadezimaler.

Beitrag melden
permissiveactionlink 02.09.2018, 18:55
16. #14, stenni

Das ist gut möglich, denn auf die Schnelle hatte ich übersehen, dass sich nicht nur die Ziffern selbst unterscheiden, sondern diesmal auch mit kleinstem Abstand Null ( und nicht 1) nebeneinander stehen dürfen, höchstens jedoch mit Abstand 15 ( und nicht 16, wie in der Langford-Sequenz). Und natürlich darf die Null niemals ganz links stehen. Kaum zu glauben, dass sich dadurch die Anzahl möglicher Permutationen dennoch beinahe verdoppelt. Interessant ist die Frage, wieviele Permutationen dann insgesamt möglich wären, wenn die Null nicht ganz links stehen darf. Wenn ich nicht abermals falsch liege, sollten das (31*30*(30!)/(2^15)) Möglichkeiten sein.

Beitrag melden
h.weidmann 02.09.2018, 20:15
17.

Zitat von stenni
326.721.800 ist die Anzahl der Lösungen für die Langfordsequenz 1 - 16. Die Skolemsequenz 0 - 15 hat dagegen 700.078.384 Lösungen. Siehe mein bereits geposteter Link: http://dialectrix.com/langford.html. Als alter Langford-Fan hab ich's schon vor Jahren selber per Programm geprüft: Es stimmt ;-)
Haben Sie Ihr Programm selbst geschrieben? Und wie lange hat es gebraucht für n = 16?

Ich habe mir mal das da heruntergeladen und kompiliert:
http://dialectrix.com/langford/langford.c

Für n = 12 braucht es weniger als eine Sekunde. Aber schon bei n = 15 hab ich die Geduld verloren.

Beitrag melden
IQ149 02.09.2018, 20:26
18. Besser sorgfältig als schnell (#16)

Eine Langford-Sequenz ist eine Folge der Länge 2n mit den Folgengliedern 1, 1, 2, 2, ..., n, n mit der Eigenschaft, dass zwischen je zwei Gliedern mit dem Wert k immer genau k weitere Folgenglieder liegen. Eine Skolem-Sequenz ist eine solche Folge mit den Gliedern 0, 0, 1, 1, ..., n-1, n-1. Deshalb kann eine Skolem-Sequenz auch mit Null beginnen. Recht banal ist dabei die Frage, wie viele Permutationen der 2n Folgenglieder es insgesamt gibt.

Beitrag melden
stenni 02.09.2018, 21:48
19. @h.weidmann (#17)

Ja, das fatale an den Langford-Sequenzen ist das exponentielle Wachstum der Rechenzeit :-). Das Programm von John Miller arbeitet auf den ersten Blick ähnlich wie meins, d.h. ein Backtracking-Algorithmus setzt zuerst das höchstwertige Paar und geht dann weiter zu den niederwertigeren Paaren bis eine Lösung gefunden wurde oder eine Sackgasse erreicht ist und geht dann wieder eins hoch um die nächste Position zu probieren. Allerdings habe ich den zeitkritischen Teil in x86-Assembler implementiert und arbeite mit Bitfeldern. Für die Aufgabe L(2,15) braucht mein 5 Jahre altes Notebook mit i5-Prozessor 203 Sekunden, für L(2,16) 1839 Sekunden. Tja und für L(2,19) hat mir bislang auch die Geduld gefehlt...
Als nächsten Optimierungsschritt würde ich das Problem gerne in Abschnitte unterteilen und jeden Abschnitt in einem Thread auf seinem eigenen Prozessorkern starten. Bräuchte nur etwas Zeit zur Forschung und neue Hardware (mindestens 6-Kerner) ;-).

Beitrag melden
Seite 2 von 5
Diskussion geschlossen - lesen Sie die Beiträge!