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 3 von 5
stenni 02.09.2018, 22:17
20. #16, permissiveactionlink

IQ149 (#18) hat ja schon erklärt, dass bei diesen Sequenzen die 0 natürlich auch am Anfang stehen darf. Anders als in Hoger Dambecks Beispiel werden die einzelnen Ziffern ja nicht zu einer großen Zahl zusammengezogen. Trotzdem habe ich mein Programm interessehalber mal kurz so modifiziert, dass die 0 nicht an erster Stelle der Sequenz stehen kann. Für die Aufgabe V(2,16) kamen dann statt 700.078.384 "nur" 654.074.488 Lösungen heraus. Ohne Gewähr ;-)

Beitrag melden
IQ149 02.09.2018, 22:48
21. L (2, 16) per Backtracking (#17, #19)

Ich habe die Berechnung per C-Programm durchgeführt (s. u.). Mit NMax2 = 32 und dem Aufruf Next_N (16, 0) liefert es (trotz 3,26*10^22, #13) das Ergebnis NSol = 653.443.600. Die Rechenzeit auf einem i7-Prozessor mit 3 GHz liegt unter 2500 s (für n = 12 unter 1 s). Eine aufsteigende Strategie für N dauert deutlich länger. Ich habe qed angefügt, damit ich mein Programm "Beweis" nennen kann (#9).

void Next_N (unsigned N, unsigned Pattern)
{
unsigned iMax = NMax2 - (N + 1); // i-bound for first N
unsigned NPat = 1 | (1

Beitrag melden
IQ149 02.09.2018, 23:14
22. Programmcode V2 (#21)

shl (i, j) steht für: verschiebe i um j bits nach links (C: kleiner kleiner)

void Next_N (unsigned N, unsigned Pattern)
{
unsigned iMax = NMax2 - (N + 1);
unsigned NPat = 1 | shl (1, N + 1); //N..N pattern
unsigned i;
if (N == 0) { NSol++; return; } //solution
for (i = 0; i < iMax; i++) // shift N..N pattern
{ // collision test
if ((NPat & Pattern) == 0) Next_N (N - 1, Pattern | NPat);
NPat = shl (NPat, 1);
}
}
// q.e.d.

Beitrag melden
stenni 03.09.2018, 08:36
23. #21

Dass die aufsteigende Strategie länger dauert kann ich bestätigen, hab ich auch schon mal probiert. Anscheinend kommt es früher zu der Situation, dass ein Paar keinen Platz mehr findet wenn man mit den großen Paaren anfängt. Bei Ihrer Lösungszahl hab ich kurz gestutzt - üblicherweise werden die Spiegellösungen weggelassen. Durch eine geschickte Anfangspositionierung der beiden höchstwertigen Paare kann man Spiegellösungen von vorneherein ausschließen und damit auch die Rechenzeit halbieren.
Schade dass die Forensoftware nicht wirklich für eine vollständige und gut lesbare Darstellung von Programmcode geeignet ist, sieht so weit auf jeden Fall interessant aus - und korrekt ist es ja offensichtlich auch!

Beitrag melden
permissiveactionlink 03.09.2018, 09:50
24. #20, stenni

Es ging ja bei Dambecks Aufgabe auch um eine Zahl. Sucht man nach einer Hexadezimalzahl mit 32 Ziffern und der gewünschten Eigenschaft einer Skolemfolge, dann sollte die Null nicht ganz links stehen. Von den (ich hatte mich da nochmals vertan) 15 * 31!/(2^15) insgesamt möglichen Permutationen verbleibt dann die von Ihnen berechnete Anzahl mit den geforderten Abständen.

Beitrag melden
emil_erpel8 04.09.2018, 00:28
25.

Zitat von permissiveactionlink
Es ging ja bei Dambecks Aufgabe auch um eine Zahl. Sucht man nach einer Hexadezimalzahl mit 32 Ziffern und der gewünschten Eigenschaft
Ach, ich wußte gar nicht, daß sich natürliche Zahlen größer neun im Dezimalsystem nicht darstellen lassen. Vielen Dank für die Aufklärung.

Beitrag melden
rotella 04.09.2018, 16:37
26. #22, iq149

Ihr Algorithmus ist schon fast optimal, ich hätte als Verbesserung (neben der Halbierung der Rechenzeit durch Ausnutzung der Symmetrie) noch den Verschlag, statt der langsamen for-Schleife gleich in einem Schritt zum nächsten freien Bit zu springen. Dies spart gerade in tieferen Rekursionsstufen mit vielen bereits belegten Bits in "Pattern" viele unnötige Vergleiche.

Bei mir sieht das dann so aus:

Aufruf mit paar(16,UPPER_BITS) für L(2, 16)

#define UPPER_BITS(~0UL kleinerkleiner 2 * N)

void paar(int n, long pos)
{
long belegt = pos;
while (belegt != ~0L) {
long freies_bit = ~belegt & (belegt + 1);
long maske = freies_bit kleinerkleiner (n + 1);
if ((maske & UPPER_BITS) || !maske) return;
maske |= freies_bit;
if (!(pos & maske)) {
if (n == 1) {Loesungen++; return; } else paar(n - 1, pos | maske);
}
belegt |= freies_bit;
}
}

Beitrag melden
IQ149 04.09.2018, 21:48
27. Optimierungen (#26, #23)

Ich habe inzwischen eine Symmetrie-Erkennung eingebaut und gleichfalls die for-Schleife als Schwachpunkt erkannt. Ihre Bitoperationen sind da durchaus trick- und hilfreich. Aktuell verfolge ich einen zweiten Ansatz: Ich betrachte (rekursiv) aufsteigend den jeweils nächsten (noch) freien Index i in der Folge der Langford Sequenz und betrachte alle Paare n..n (n von N bis 1), die hier eingefügt werden können, d.h. es muss jeweils auch der Index i + n + 1 noch frei (und zulässig) sein. Besonders effektiv ist es dabei, die noch verfügbaren n-Werte als verkettete Liste zu führen, das erspart die for-Schleife zur jeweiligen Durchmusterung und Bewertung aller n von N bis 1 und ist (mindestens) so schnell wie die Bitmasken. Vgl. hierzu auch http://dialectrix.com/langford/langford-algorithm.html

Beitrag melden
IQ149 04.09.2018, 23:51
28. L(2,16) (#27, #21)

Mit dem neuen Ansatz aus #27 habe ich L(2,16) nunmehr auf dem besagten i7-Prozessor in ca. 1000 s berechnet und das bekannte Ergebnis 326.721.800 erzielt. Das Verhältnis der Rechenzeiten zwischen L(2,15) und L(2,16) entspricht ungefähr dem der Zeiten von Frederick Groth aus dem Februar 1987 auf einem Commodore 64 (15.5 d, 122.4 d).

Beitrag melden
rotella 05.09.2018, 14:04
29. #28, iq149

Ich komme mit Symmetrie-erkennung oder besser gesagt -vermeidung mit dem Bit-Trick auch auf ca. 1000s, allerdings auf einem älteren Athlon mit 2,7 GHz. Vielleicht posten Sie Ihre Variante auch noch mal, direkt oder als Link zu pastebin.com?

Der Trick das kleinste Null-Bit in einem bitfield mit dem Term "~bitfield & (bitfield + 1)" bzw. vergleichbare Ausdrücke in anderen Sprachen oder für das kleinste Eins-Bit zu finden soll angeblich schon aus den 60ern stammen und ist z.B. auch sehr hilfreich für einen sehr schnellen und sehr kurzen Algorithmus für das n-queens-Problem. (n Damen auf einem n mal n Schachbrett so zu positionieren, dass sich keine Damen gegenseitig bedrohen)

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