Der Mai stellte sich als kalt heraus, die Heizung wurde ausgeschaltet und die Rechenleistung (und die Heizleistung) waren nicht vorhanden, aber sie waren im Leerlauf. Warum laden Sie sie nicht mit etwas Nutzlosem , das sich erwärmt und unterhält?Aber ich werde von weitem anfangen. Neulich stieß ich auf ein Problem für eine High School mit folgendem Wortlaut: „Mehrere aufeinanderfolgende positive ganze Zahlen wurden hintereinander so geschrieben, dass die Summe aller drei aufeinanderfolgenden Zahlen vollständig durch die am weitesten links stehende Zahl dieses Tripels teilbar ist. "Was ist die maximale Anzahl von Zahlen, die ausgeschrieben werden können, wenn die letzte Zeilennummer ungerade ist?Mit dieser Einschränkung ist es leicht zu beweisen, dass es in jedem Tripel ungerader Zahlen mehr als gerade Zahlen gibt. Und da der Unterschied zwischen ihnen nicht mehr als eins sein kann, ist die maximale Länge der Sequenz auf fünf Zahlen begrenzt. Als Beispiel können wir die Sequenz 4 5 3 2 1 angeben .Detaillierte Nachweise finden Sie hier.Aber was ist, wenn wir die angegebene Einschränkung der Seltsamkeit der letzten Zahl aufheben? Dann können Sie rechts die Zahlen 7 6 8 hinzufügen und die Reihenfolge auf acht Zahlen erweitern. Sie können auch ein Dutzend hinzufügen und die fehlenden neun links anbringen. Nun, und wahrscheinlich wird dies nicht die einzige und nicht die längste Permutation sein.Als ich versuchte, logisch zu argumentieren, fand ich keine Beweise für die Einschränkungen solcher Sequenzen und beschloss, einen Taschenrechner zur Analyse in die Heizung des Hauses einzubeziehen . Grobe erschöpfende Suche aller N ! Optionen zeigten schnell das Scheitern der Methode, aber die Richtungsaufzählung ermöglichte signifikante Fortschritte, und das Ergebnis war gleichzeitig erwartet und unerwartet.Es stellte sich heraus, dass für alle N bis einschließlich 29 solche Permutationen von Zahlen von 1 bis N tatsächlich für die Längen 27 und 29 in einer einzigen Variante gefunden werden. Aber dann gibt es Lücken. Für Permutationen mit den Größen 30, 31, 32 und 33 gibt es keine Lösungen, für die Zahl 34 gibt es eine.eine solche33 23 10 13 7 6 1 29 27 2 25 21 4 17 15 19 11 8 3 5 31 9 22 14 30 26 34 18 16 20 12 28 32 24
Andererseits zwei Leerzeichen. Für die Werte 37 und 38 sind solche Sequenzen nicht einfach und dann ein Fehler. Ich war sogar verzweifelt, die nächsten zehn erwiesen sich als völlig leer, aber das Glück lächelte, für N = 51 ist die notwendige Permutation immer noch gefunden.da ist sie46 45 1 44 49 39 10 29 21 37 5 32 23 41 51 31 20 11 9 2 43 35 8 27 13 14 25 3 47 40 7 33 16 17 15 19 26 50 28 22 6 38 34 4 30 18 42 48 36 12 24
Es gibt sogar zwei von ihnen, aber sie kreuzen sich größtenteils.Weiter ist wieder Leere geplant, zumindest für die Nummern 52 und 53 gibt es keine Lösungen, aber ich habe nicht weiter gesucht. Trotzdem wächst die Wartezeit mit jedem Schritt exponentiell und das Haus ist schon viel wärmer geworden. Ich habe mich entschlossen, vorerst dort anzuhalten.Wenn Sie die gefundene Anzahl möglicher Optionen in einer Tabelle reduzieren, können Sie das folgende Diagramm erstellen.
Ja, es gibt etwas, über das Sie meditieren können.Im ursprünglichen Problem war es nicht erforderlich, die natürliche Serie von einer zu starten. Die Hauptsache ist, dass alle Zahlen von a bis b in der Sequenz gefunden werden. Aber ich habe es versucht, es wird nur schlimmer, es gibt noch weniger Möglichkeiten. Was in der Tat erklärbar ist. Je größer die Zahl in der linken Position des Tripels ist, desto geringer kann die Multiplizität durch die Summe der beiden anderen erhalten werden, d.h. Je weniger Optionen verfügbar sind. Nun, die Frage nach der Obergrenze der Länge solcher Sequenzen bleibt offen. Mit dem Wachstum der Dimensionalität verringert sich die Erfolgswahrscheinlichkeit deutlich, wird sie jedoch zunichte gemacht? Oder sie werden, wenn auch selten, auf solche (un) interessanten Permutationen stoßen.Schließlich können Sie vielleicht den Code des Heizprogramms mitbringen,Es stimmt, er ist auf Haskellimport Data.List (delete)
import Control.Parallel.Strategies
import System.Environment
pvc :: Int -> Int -> [Int] -> [[Int]]
pvc a b [] = [[a,b]]
pvc a b xs = [a:ys |
x <- xs,
mod (a + b + x) a == 0,
ys <- pvc b x (delete x xs)]
gen :: Int -> [[[Int]]]
gen n =
let ab = [(a, b) | a <- [1..n], b <- delete a [1..n]]
in map hlp ab `using` parList rseq
where
hlp (a,b) = pvc a b $ delete a $ delete b [1..n]
main = do
[n] <- getArgs
print $ concat $ gen $ read n