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 4 von 5
IQ149 05.09.2018, 21:21
30. Langford Programm (#29)

Meine Buchführung war etwas verrutscht. Ich benötige für L(2,16) aktuell 450s. Den Programmcode finden Sie unter https://pastebin.com/m9Ayr8NT. Die ersten 16 Milliarden Lösungen für L(2,19) habe ich mit dem Programm in knapp 7,5 h gefunden, das würde auf eine Gesamtzeit von ca. 5 Tagen hinauslaufen.

Beitrag melden
rotella 07.09.2018, 11:43
31. #30, iq149

Vielen Dank für den Link zu Ihrer Implementierung mit den verketteten Listen. Diese Version ist tatsächlich deutlich schneller als meine ursprüngliche Version mit den Bitoperationen.

Ich habe jetzt ihren neuen Algorithmus als Grundlage genommen und ihre Listen wiederum durch Bitoperationen ersetzt, sozusagen das Beste aus beiden Ideen zusammengeklaut. ;-)

Diese neue Version verdoppelt die Geschwindigkeit dann fast noch mal - bei mir von 590s auf nur noch 320s. Ich benutze die Funktion ffsll() aus string.h die evtl. unter Windows nicht zur Verfügung steht. In diesem Fall kann der Aufruf durch die Ersatzimplementierung replcmnt_ffsll() im Programmcode - bei leichtem Geschwindigkeitsverlust - verwendet werden. Den Programmcode finden Sie unter https://pastebin.com/3G70ne36

Beitrag melden
IQ149 08.09.2018, 01:21
32. Rechenzeiten (#31, #30)

Ihr Programm läuft bei mir für L(2,15) auch schneller als meines, aber bei L(2,19) bricht es deutlich ein. Es findet dort die erste Mrd Lösungen in 7590 s, meines hingegen in 5670 s. Ich habe in meinem Programm zwischenzeitlich einige Verbesserungen vorgenommen, insbesondere sind die Symmetrie- und die Sackgassen-Erkennung aus der v-Schleife herausgewandert, die Suche nach der nächsten freien Position im Tableau wird beschleunigt (s-Speedup) und die letzte freie Stelle wird mitverfolgt (jMax) (https://pastebin.com/sHRm8cd0). Der Kerngedanke ist gleich geblieben: Fülle die freien Stellen von links nach rechts, teste dabei die noch verfügbaren Paare mit fallenden Werten (k). Eine Erklärung für das L(2,19) Phänomen habe ich bisher nicht gefunden.

Beitrag melden
rotella 08.09.2018, 11:24
33. #32

Ich denke, es gibt auch kein echtes Problem, die Zeiten für die erste Milliarde sind nur auf den ersten Blick paradox.

Bei meiner Implementierung arbeite ich nämlich mit steigenden Werten für k, während Sie mit fallenden Werten arbeiten. Für die Gesamtlaufzeit spielt das bei dieser Art der Suche keine Rolle, ganz im Gegensatz zu dem ersten Algorithmus, wo nacheinander die verschiedenen k-Werte durchlaufen wurden, während beim neuen Algorithmus die verschiedenen Indizes i durchlaufen werden. Aber wenn man nur ein Teilergebnis betrachtet, kommt man mit fallenden k Werten zuerst schneller zu Treffern.

Ich fürchte daher auch, dass Ihre Hochrechnung für L(2,19) leider zu optimistisch ist.

Momentan habe ich noch einen dritten Ansatz, in dem man beide Algorithmen mischt, also zuerst sagen wir für L(2,16) die "Klammern" 16, 15 und evtl. noch weitere nach der ersten Methode setzt (So könnte man auch gleich die Symmetrie ausschließen) und danach die Lücken für i = 0 bis 31 füllt mit der zweiten Methode. Müsste man mal testen, wo das optimale Mischungsverhältnis beider Methoden liegt...

Ihren neuen Programmcode probiere ich natürlich auch noch aus...

Beitrag melden
IQ149 08.09.2018, 12:52
34. Sie haben Recht (#33)

Für die ersten 36 Mrd Lösungen von L(2,19) hat mein Programm 59910 s gebraucht, Ihres hingegen nur 51890 (mit Schrittweite 8 in ffsll). Bereits nach 20 Mrd hatten Sie mich überholt, denn mein Programm hat (bisher) relativ konstante Zuwächse pro 4 Mrd Paket, Ihres hingegen zunehmend kleinere. Meine ursprünglichen Zeiten bezogen sich übrigens auf 4 Mrd (nicht 1 Mrd). Vielleicht gibt es ja demnächst ein Langford FPGA-Design.

Beitrag melden
schwertas 09.09.2018, 19:12
35. Anordnungen ausprobieren

Wenn . eine belibige Ziffer ergibt gibt es foldgenden Lösungsweg:
Durch die Regel bedingt müssen unteschiedlich lange Ziffer-Fehlstelle Gruppen auf die 8 Stellen verteilt werden, wobei sich die Gruppen überlappen dürfen, jedoch nur eine Ziffer auf jeder Position der Zahl stehen kann.
Zuerst plaziere ich die 4 er Gruppe, da sie am unflexibelsten angeordnet werden kann:
Möglichkeiten:
4....4.. (1)
.4....4. (2)
..4....4 (3)
Durch Anordnen der 3er Gruppe ergibt sich
aus (1)
4.3..43. (1-1)
4..3.4.3 (1-2)
aus (2)
34..3.4. (2-1)
.4.3..43 (2-2)
aus (3)
3.4.3..4 (3-1)
.34..3.4 (3-2)
Durch Anordung der 2er Gruppe ergibt sich
aus (1-1)
423.243.
4.3.2432
aus (1-2)
42.324.3
aus (2-1)
342.324.
aus (2-2)
.423.243
aus (3-1)
3.423.24
aus (3-2)
.342.324
Aus diesen Möglichkeiten fallen jeztz alle heraus, deren zwei freie Plätze nicht im Abstand von 2 Positionen sind.
Also bleiben nur die beiden angegebenen Lösungen übrig.

Beitrag melden
schwertas 09.09.2018, 20:14
36. Anordnungen ausprobieren (ordentlich lesbar)

Wenn . eine belibige Ziffer ergibt, gibt es folgenden Lösungsweg:

Durch die Regel bedingt müssen unteschiedlich lange Ziffer-Fehlstelle Gruppen auf die 8 Stellen verteilt werden, wobei sich die Gruppen überlappen dürfen, jedoch nur eine Ziffer auf jeder Position der Zahl stehen kann.

Zuerst plaziere ich die 4 er Gruppe, da sie am unflexibelsten angeordnet werden kann:

Möglichkeiten:

4....4.. (1)

.4....4. (2)

..4....4 (3)

Durch Anordnen der 3er Gruppe ergibt sich

aus (1) 4.3..43. (1-1)

4..3.4.3 (1-2)

aus (2)

34..3.4. (2-1)

.4.3..43 (2-2)

aus (3)

3.4.3..4 (3-1)

.34..3.4 (3-2)

Durch Anordung der 2er Gruppe ergibt sich

aus (1-1)

423.243.

4.3.2432

aus (1-2)

42.324.3

aus (2-1)

342.324.

aus (2-2)

.423.243

aus (3-1)

3.423.24

aus (3-2)

.342.324

Aus diesen Möglichkeiten fallen jeztz alle heraus, deren zwei freie Plätze nicht im Abstand von 2 Positionen sind. Also bleiben nur die beiden angegebenen Lösungen übrig.

Beitrag melden
rotella 10.09.2018, 11:18
37. #33, #34

Mit der Mischung beider Algorithmen lässt sich tatsächlich noch mal ca. 23% Rechenzeit sparen. Die besten Ergebnisse kann man erzielen, wenn zuerst die größten sechs k-Werte, also NMax-5...Nmax, nach der ersten Suchmethode gefunden werden und danach mit der zweiten Suchmethode der Reihe nach die noch nicht besetzten Indices gefüllt werden.

DIe Suchzeit für NMax=16 verkürzt sich bei mir dadurch von 291s auf 224s.

Für L(2,18) ergeben sich so 21500s, geschätzt sollte die Suche für L(2,19) dann nur noch 2,8 Tage dauern.

Die Erweiterung des Programmcodes findet sich hier https://pastebin.com/wiRs5vgX

Beitrag melden
IQ149 11.09.2018, 11:50
38. Ergebnisse (#37, #31)

Ich habe inzwischen mit Ihrem Programm (#31) L(2,19) berechnet. Es findet in 3,10 Tagen 256.814.891.280 Lösungen. Genauere Daten gibt es hier: https://pastebin.com/XVFHP33f. Mit der neuen Version (#37) werde ich das auch noch einmal testen.

Beitrag melden
stenni 13.09.2018, 12:06
39. Optimierung der Bitscan-Funktion (#37, #38)

Zunächst mal meinen Respekt für rotella und IQ149, die durch ihre kreativen und eleganten Ansätze dem guten alten Backtracking-Algorithmus so erstaunlich auf die Sprünge geholfen haben. Ein großes intellektuelles Vergnügen, vielen Dank dafür!
Als kleine Optimierung für die ffsll-Funktion (mit Einschränkung der Portabilität) habe ich in rotellas letzter Version die Intrinsic-Funktion _BitScanForward64 verwendet, die den bsf-Befehl der x86-Prozessoren benutzt und damit nochmals eine Beschleunigung von gut 5% erreicht.
#include
Body der Inlinefunktion ersetzen durch:
unsigned long bitPos;
if (_BitScanForward64(&bitPos, n))
return(bitPos+1);
else
return 0;

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