Collatz Attack!

Diese Herausforderung basiert auf einigen neuen Erkenntnissen im Zusammenhang mit der Collatz-Vermutung und wurde im Geiste eines kollaborativen Polymath-Projekts entworfen . Das Lösen der vollständigen Vermutung wird von Experten der Mathematik- / Zahlentheorie als äußerst schwierig oder möglicherweise unmöglich angesehen, aber diese einfachere Aufgabe ist durchaus machbar und es gibt viele Beispiele für Beispielcode. Im besten Fall könnten neue theoretische Erkenntnisse über das Problem gewonnen werden, die auf den Einträgen / dem Einfallsreichtum / der Kreativität der Teilnehmer beruhen.

Der neue Befund lautet wie folgt: Stellen Sie sich eine zusammenhängende Reihe von ganzen Zahlen [ n1 ... n2 ] vor, sagen wir m total. Weisen Sie diese Ganzzahlen einer Listenstruktur zu. Nun kann eine verallgemeinerte Version der Collatz-Vermutung wie folgt vorgehen. Iterieren Sie eine der m (oder weniger) Ganzzahlen in der nächsten Liste basierend auf einigen Auswahlkriterien / Algorithmen. Entfernen Sie diese Ganzzahl aus der Liste, wenn sie 1 erreicht. Die Collatz-Vermutung entspricht eindeutig der Bestimmung, ob dieser Prozess für alle Auswahlmöglichkeiten von n1, n2 immer erfolgreich ist .

Hier ist die Wendung, eine zusätzliche Einschränkung. Addieren Sie bei jedem Schritt die m aktuellen Iterationen in der Liste. Betrachten Sie dann die Funktion f (i), wobei i die Iterationsnummer und f (i) die Summe der aktuellen Iterationen in der Liste ist. Suchen Sie nach f (i) mit einer bestimmten "schönen" Eigenschaft.

Das gesamte / Gesamtkonzept ist besser / gründlicher dokumentiert hier (mit vielen Beispielen in Rubin). Das Ergebnis ist, dass ziemlich einfache Strategien / Heuristiken / Algorithmen existieren, die zu einer "ungefähr monoton abnehmenden" f (i) führen , und dass auf dieser Seite viele Beispiele angegeben sind. Hier ist ein Beispiel für die grafische Ausgabe (über Gnuplot dargestellt):

Hier ist also die Herausforderung: Verwenden Sie Variationen der vorhandenen Beispiele oder völlig neue Ideen, um einen Auswahlalgorithmus zu erstellen, der dazu führt, dass f (i) "so nahe wie möglich monoton abnimmt". Die Teilnehmer sollten eine Grafik von f (i) in ihre Einreichung aufnehmen. Die Wähler können anhand dieses Diagramms und der algorithmischen Ideen im Code abstimmen.

Der Wettbewerb basiert nur auf n1 = 200 / n2 = 400 Parametern! (das gleiche auf der Beispielseite.) Aber hoffentlich werden die Teilnehmer andere Regionen erkunden und auch versuchen, ihre Algorithmen zu verallgemeinern.

Beachten Sie, dass eine Taktik, die hier sehr nützlich sein kann, Algorithmen vom Gradientenabstiegstyp oder genetische Algorithmen sind.

Kann dies alles im Chat für interessierte Teilnehmer weiter diskutieren.

Für einige Schiedsrichter eine weitere Codegolf-Collatz-Herausforderung: Collatz Conjecture (von Doorknob )

Ich habe in Python 2 Code geschrieben, um Algorithmen für diese Herausforderung auszuführen:

import matplotlib.pyplot as plt

def iterate(n):
    return n*3+1 if n%2 else n/2
def g(a):
    ##CODE GOES HERE
    return [True]*len(a)
n1=input()
n2=input()
a=range(n1,n2+1)
x=[]
y=[]
i=0
while any(j>1 for j in a):
    y.append(sum(a))
    x.append(i)
    i+=1
    b=g(a)
    for j in range(len(a)):
        if b[j]:
            a[j]=iterate(a[j])
plt.plot(x,y)
plt.show()

g(x) Nimmt die Liste der Werte und gibt eine Liste der Bools zurück, um festzustellen, ob jeder geändert werden soll.

Dazu gehört das erste, was ich versucht habe, als Zeile direkt nach dem Kommentar, in der alle Werte in der Liste wiederholt wurden. Ich schaff das:

Es sieht nicht annähernd monoton aus, also habe ich versucht, nur Werte zu iterieren, die die Summe verringern würden, falls es welche gibt, und diejenigen zu iterieren, die sie sonst am wenigsten erhöhen würden:

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m=[n[i]-a[i] for i in range(l)]
return [m[i]==min(m) for i in range(l)]

Leider endet das nicht (zumindest für n1=200, n2=400). Ich habe versucht, die Werte zu verfolgen, die ich zuvor gesehen hatte, indem ich Folgendes initialisiert habe c=set():

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m={i:n[i]-a[i] for i in range(l)}
r=[i for i in m if m[i]==min(m.values())]
while all([a[i] in c for i in r]) and m != {}:
    m={i:m[i] for i in m if a[i] not in c}
    r+=[i for i in m.keys() if m[i]==min(m.values())]
for i in r:
    c.add(a[i])
return [i in r for i in range(l)]

Das endet aber auch nicht.

Ich habe noch nichts anderes ausprobiert, aber wenn ich neue Ideen habe, werde ich sie hier posten.

Python 3

Meine Hauptidee war es, jede Zahl-Collatz-Sequenz der f(i)Funktion einzeln hinzuzufügen , so dass die Gesamtzunahme von minimiert wird f(i). Die resultierende Funktion nimmt nicht streng ab, hat aber eine schöne Struktur (meiner Meinung nach :)). Das zweite Diagramm wurde mit einem längeren Intervall für f(i)und einer etwas anderen Bestrafungsfunktion erstellt. Code on Gist.

Bei Verwendung der (3 * n + 1) / 2-Regel anstelle der 3 * n + 1-Regel erzeugt der Algorithmus eine vollständig monotone f(i)! Ich bin sicher, dass diese Modifikation die Grafiken von vzn auch viel glatter machen könnte. Das zweite Diagramm wurde mit einem längeren Intervall für erstellt f(i). Code on Gist.

Beide Ergebnisse sind für größere [n,2*n]Bereiche ähnlich .