Golomb-Lineale sind Mengen nicht negativer Ganzzahlen, sodass keine zwei Paare von Ganzzahlen in der Menge den gleichen Abstand voneinander haben.
Ist beispielsweise [0, 1, 4, 6]
ein Golomb-Lineal, weil alle Abstände zwischen zwei Ganzzahlen in dieser Menge eindeutig sind:
0, 1 -> distance 1
0, 4 -> distance 4
0, 6 -> distance 6
1, 4 -> distance 3
1, 6 -> distance 5
4, 6 -> distance 2
Der Einfachheit halber wird bei dieser Herausforderung (und da die Übersetzung trivial ist) vorausgesetzt , dass ein Golomb-Lineal immer die Zahl enthält0
(wie im vorherigen Beispiel).
Da diese Menge von Länge ist 4
, sagen wir, dass dies ein Golomb-Lineal der Ordnung ist 4
. Der größte Abstand in dieser Menge (oder Element, da 0
immer in der Menge) ist 6
, sagen wir daher, dass dies ein Golomb-Lineal der Länge ist 6
.
Deine Aufgabe
Finden Golomb Herrscher , um 50
zu 100
(einschließlich) , die so klein haben Längen , wie Sie finden können. Die gefundenen Lineale müssen nicht optimal sein (siehe unten).
Optimalität
Ein Golomb-Ordnungslineal N
gilt als optimal, wenn es kein anderes Golomb-Ordnungslineal N
mit geringerer Länge gibt.
Optimale Golomb-Lineale sind für Befehle unter 28 bekannt , obwohl es mit zunehmender Reihenfolge immer schwieriger wird, Optimalität zu finden und zu beweisen.
Daher wird nicht erwartet, dass Sie das optimale Golomb-Lineal für eine der Anweisungen zwischen 50
und finden 100
(und noch weniger erwartet, dass Sie nachweisen können, dass sie optimal sind).
Die Ausführung Ihres Programms ist zeitlich unbegrenzt.
Grundlinie
Die folgende Liste enthält die Längen der Golomb-Lineale von 50
bis 100
(in der Reihenfolge), die mit einer naiven Suchstrategie ausgewertet wurden (Dank an @PeterTaylor für diese Liste):
[4850 5122 5242 5297 5750 5997 6373 6800 6924 7459 7546 7788 8219 8502 8729 8941 9881 10199 10586 10897 11288 11613 11875 12033 12930 13393 14046 14533 14900 15165 15687 15971 16618 17354 17931 18844 19070 19630 19669 20721 21947 22525 23290 23563 23880 24595 24767 25630 26036 26254 27218]
Die Summe all dieser Längen ist 734078
.
Wertung
Ihre Punktzahl ist die Summe der Längen aller Ihren Golomb Herrschers zwischen 50
und 100
geteilt durch die Summe der Längen von Golomb Herrschern zwischen 50
und 100
in der Basislinie: 734078
.
Falls Sie für eine bestimmte Reihenfolge kein Golomb-Lineal gefunden haben, berechnen Sie Ihre Punktzahl auf die gleiche Weise, indem Sie das Doppelte der Länge in der Grundlinie für diese bestimmte Reihenfolge verwenden.
Die Antwort mit der niedrigsten Punktzahl gewinnt.
Im Falle eines Gleichstands werden die Längen der größten Bestellung verglichen, bei denen sich die beiden Antworten unterscheiden, und die kürzeste gewinnt. Wenn beide Antworten für alle Bestellungen gleich lang sind, gewinnt die Antwort, die zuerst gesendet wurde.
quelle
n
istn(n-1)/2
, da es so viele positive Unterschiede gibt. Daher ist die kleinstmögliche Punktzahl bei dieser Herausforderung147050/734078 > 0.2003193
.Antworten:
C #, 259421/734078 ~ = 0,3534
Methoden
Ich habe schließlich eine mehr oder weniger lesbare Erklärung für die projektive Feldmethode (Singers Methode) in Konstruktionen verallgemeinerter Sidon-Mengen gefunden , obwohl ich immer noch denke, dass sie leicht verbessert werden kann. Es stellt sich heraus, dass es der Affinen-Feld-Methode (Bose-Methode) ähnlicher ist als die anderen Artikel, die ich gelesen habe.
Beachten Sie, dass diese Methoden die bekanntesten Werte für jede Länge größer als 16 ergeben. Tomas Rokicki und Gil Dogon bieten eine Belohnung von 250 USD für jeden, der sie für Längen von 36 bis 40000 schlägt Preis.
Code
Das C # ist nicht sehr idiomatisch, aber ich brauche es, um mit einer alten Version von Mono zu kompilieren. Dies ist trotz der Überprüfung der Argumente kein Qualitätscode für die Produktion. Ich bin mit den Typen nicht zufrieden, aber ich glaube nicht, dass es in C # eine wirklich gute Lösung dafür gibt. Vielleicht in F # oder C ++ mit verrückten Vorlagen.
Ergebnisse
Leider würde das Hinzufügen der Lineale etwa 15.000 Zeichen nach dem Post-Größenlimit erfordern, sodass sie im Pastebin sind .
quelle
Python 3, Punktzahl 603001/734078 = 0,82144
Naive Suche kombiniert mit Erdős-Turan-Konstruktion:
Für ungerade Primzahlen p ergibt sich ein asymptotisch optimales Golomb-Lineal.
quelle
p
ungefähr der Ordnung und Länge2p^2
, während es Golomb-Lineale vonn
ungefähr der Ordnung und Längen^2
asymptotisch gibt.2p^2
undp^2
.Mathematica, Punktzahl 276235/734078 <0,376302
Die Funktion
ruzsa
implementiert eine Konstruktion eines Golobm-Lineals (auch Sidon-Set genannt), das sich in Imre Z. Ruzsa befindet. Lösen einer linearen Gleichung in einer Menge von ganzen Zahlen. I. Acta Arith., 65 (3): 259–282, 1993 . Bei jeder Primzahlp
ergibt diese Konstruktion ein Golomb-Lineal mitp-1
Elementen, die in den Ganzzahlen modulo enthalten sindp(p-1)
(dies ist eine noch stärkere Bedingung als ein Golomb-Lineal in den Ganzzahlen selbst).Ein weiterer Vorteil der Arbeit im Ganzzahlmodulo
m
besteht darin, dass jedes Golomb-Lineal gedreht (die gleiche Konstante wird zu allen Modulo-Elementen hinzugefügtm
) und skaliert werden kann (alle Elemente werden mit der gleichen Konstante multipliziert, solange diese Konstante relativ hoch istm
) das Ergebnis ist immer noch ein Golomb-Herrscher; manchmal wird dadurch die größte ganze Zahl signifikant verringert. Die FunktionscaledRuzsa
versucht alle diese Skalierungen und zeichnet die Ergebnisse auf.manyRuzsaSets
enthält die Ergebnisse dieser Konstruktion und Skalierung für alle ersten 32 Primzahlen (etwas willkürlich gewählt, aber die 32. Primzahl 131 ist deutlich größer als 100); Es gibt fast 57.000 Golomb-Lineale in diesem Satz, was einige Minuten in Anspruch nimmt.Natürlich bilden die ersten
k
Elemente eines Golomb-Lineals selbst ein Golomb-Lineal. Die FunktiontryGolomb
betrachtet also ein solches Lineal, das aus einer der oben berechneten Mengen besteht. Die letzte ZeileTable...
wählt die beste Golomb Herrscher kann es, von jeder Bestellung von50
zu100
, von allen Golomb - Maßstäbe auf diese Weise gefunden.Die gefundenen Längen waren:
Ich wollte das ursprünglich mit zwei anderen Konstruktionen kombinieren, denen von Singer und Bose; aber es scheint, dass Peter Taylors Antwort dies bereits umgesetzt hat, so dass ich diese Längen vermutlich einfach wiedererlangen würde.
quelle
m
frei drehen / skalieren können. Schau dir[0, 1, 4, 6]
Mod 7 an. Wenn ich 1 hinzufüge, bekommen wir[0, 1, 2, 5]
, was kein Golomb-Lineal ist.[0, 1, 4, 6]
ist kein mod-7 Golomb-Lineal, weil es zum Beispiel1 – 0
gleich0 – 6
modulo 7 ist.