Ein lustiges Spiel, wenn Sie gelangweilt sind, ist das Diffy-Spiel . Es ist ein Einspieler-Spiel, das ziemlich einfach ist und viel Zeit in Anspruch nehmen kann.

Das Diffy-Spiel funktioniert wie folgt: Sie beginnen mit einer Liste nicht negativer Ganzzahlen, die wir in diesem Beispiel verwenden werden

3 4 5 8

Dann nehmen Sie die absolute Differenz zwischen benachbarten Zahlen

 (8)  3   4   5   8
    5   1   1   3

Dann wiederholst du. Sie wiederholen, bis Sie feststellen, dass Sie in eine Schleife eingetreten sind. Und dann fängt das Spiel in der Regel wieder von vorne an.

3 4 5 8
5 1 1 3
2 4 0 2
0 2 4 2
2 2 2 2
0 0 0 0
0 0 0 0

Oft hat das Spiel kein Ziel, Sie haben nur Zeit, indem Sie in Ihrem Kopf arithmetisch arbeiten. Wenn ich jedoch das Vergnügen habe, dieses Spiel zu spielen, ist es immer mein Ziel, eine Periode auszuwählen und zu versuchen, ein Spiel zu konstruieren, das mit dieser bestimmten Periode eine Schleife bildet.

Nicht alle Spiele sind periodisch, das obige Beispiel ist beispielsweise nicht periodisch, weil es irgendwann ein Spiel mit allen Nullen erreicht und es somit niemals wieder in seine Ausgangsposition zurückbringen kann. Tatsächlich scheint die überwiegende Mehrheit der Spiele nicht regelmäßig zu sein, was die wenigen Spiele betrifft, die ein seltenes Juwel sind.

Bei einem Spiel, das mit einer bestimmten Periode wiederholt wird, ist es trivial, ein anderes Spiel zu erstellen, das mit derselben Periode wiederholt wird, indem nur die Sequenz verdoppelt wird. Zum Beispiel das Spiel:

1 0 1

Spielt genauso wie das Spiel:

1 0 1 1 0 1

In der Tat können wir davon ausgehen, dass beide wirklich das sich unendlich wiederholende Spiel sind:

... 1 0 1 ...

Wir werden sie als ein Spiel für diese Herausforderung betrachten.

In ähnlicher Weise wird durch Multiplizieren der gesamten Sequenz mit einer Konstanten auch die Periode trivial erhalten, sodass wir erneut zwei Spiele zählen, die sich um einen konstanten Faktor unterscheiden, um dasselbe Spiel zu sein.

Die unendlichen Zeichenfolgen ... 1 0 1 ...und ... 0 1 1 ...sind offensichtlich dieselbe Zeichenfolge, die um ein Zeichen verschoben ist. Wir werden diese Spiele nicht als unterschiedliche Spiele betrachten, aber wenn eines das andere erreicht, wird es bei der Bestimmung der Spieldauer nicht als Ende des Zyklus betrachtet. Beispielsweise:

Die beiden Spiele

... 0 0 0 1 0 1 ...  = A
... 0 0 1 1 1 1 ...  = B
... 0 1 0 0 0 1 ...  = A << 4
... 1 1 0 0 1 1 ...  = B << 4
... 0 1 0 1 0 0 ...  = A << 2
... 1 1 1 1 0 0 ...  = B << 2

und

... 0 0 1 0 1 0 ...  = A << 1
... 0 1 1 1 1 0 ...  = B << 1
... 1 0 0 0 1 0 ...  = A << 5
... 1 0 0 1 1 1 ...  = B << 5
... 1 0 1 0 0 0 ...  = A << 3
... 1 1 1 0 0 1 ...  = B << 3

sind beide Spiele mit Punkt 6. Sie teilen an keiner Stelle ihrer Schleifen einen Begriff miteinander (im Gegensatz zu ... 1 1 0 ...und ... 1 0 1 ...die sich erreichen), aber da sie versetzte Versionen voneinander sind, werden sie beim Zählen als dasselbe Spiel betrachtet.

Das Reflektieren (oder Umkehren) einer unendlichen Zeichenfolge ergibt im Wesentlichen dasselbe Verhalten, jedoch nicht unbedingt dieselbe Periode. Betrachten Sie zum Beispiel

... 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 ...

und sein Spiegelbild

... 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 ...

Wenn wir davon ausgehen, dass die nächste Generation auf halbem Weg zwischen den Charakteren produziert wird:

... 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 ...
 ... 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 ...

... 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 ...
 ... 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 ...

dann hätten beide die Position um 3,5 Elemente verschoben. Wir gehen jedoch nicht davon aus, dass die nächste Generation mit diesem halben Versatz hergestellt wird. Daher rundet eine auf eine Verschiebung von 4 Elementen mit einer Periode von 15 und die andere auf eine Verschiebung von 3 Elementen mit einer Periode ab von 5.

Aus diesem Grund betrachten wir eine asymmetrische Zeichenkette und ihre Reflexion als unterschiedlich, obwohl die Zyklen in gewissem Sinne isomorph sind. Wenn sie Teil desselben Zyklus sind, zählt dies natürlich nur als ein Zyklus.

Mit diesen Einschränkungen kann ein wenig Mathematik zeigen, dass es tatsächlich eine endliche Anzahl von Diffy-Zyklen mit einer bestimmten endlichen Periode gibt. Außerdem ist jede unendliche Zeichenkette mit einer endlichen Periode eine unendliche Wiederholung einer endlichen Zeichenkette.

Beachten Sie, dass die Zeichenfolgen länger oder kürzer als die Punkte sein können. Beispielsweise gibt es eine Zeichenfolge der Länge 5 mit der Periode 15 und eine Zeichenfolge der Länge 15 mit der Periode 5. Alle Zeichenfolgen mit der Periode 19 haben die Länge 9709.

Aufgabe

Bei einer nsolchen Zahl , dass n über Standardeingabemethoden größer als 1 ist, wird die Anzahl der unterschiedlichen Diffy-Zyklen mit einer Periode von genau bestimmt n.

(Es scheint, dass in der Literatur 0oft nicht als periodisches Diffy-Spiel angesehen wird. Da es sich um eine Grauzone handelt, werde ich Sie nicht bitten, nach dieser zu suchen. n = 1)

Das ist Code-Golf , also ist das Ziel, die Anzahl der Bytes in Ihrem Quellcode zu minimieren.

Testfälle

2  ->   0
3  ->   1
4  ->   0
5  ->   1
6  ->   1
7  ->   3
8  ->   0
9  ->   4
10 ->   4
11 ->   3
12 ->   5
13 ->   5
14 ->  24
15 ->  77
16 ->   0
17 -> 259
18 -> 259
19 ->  27
20 -> 272
21 -> 811
22 -> 768
23 ->  91
24 -> 340
25 -> 656

Hinweise

Alle periodischen diffy-Spiele enthalten nur Null und eine einzige Konstante. Dies bedeutet, dass jedes periodische Spiel isomorph zu einem diffy-Spiel ist, das nur aus Nullen und Einsen besteht.

Python 2 , 181 Bytes

n=input()
m=2**n
a=[m]*m
r=lambda i:[i*-~m>>k&m-1 for k in range(n)]
def s(i):
 if a[i]&m:a[i]=i;a[i]=s(min(r(i^i*2)))
 return a[i]
print sum(min(r(i)[1:])>i==s(i)for i in range(m))

Probieren Sie es online!

Wie es funktioniert

Die Regeln, die jede Zeile eines binären Diffy-Spiels in die nächste Zeile umwandeln, stimmen mit den Regeln überein, die jede Spalte in die nächste Spalte umwandeln. Daher genügt es , alle unterschiedlichen Zyklen in dem Graphen alles kanonischen längen- zu finden n Spalten, wobei eine Spalte „kanonische“ ist , wenn es lexikographisch kleiner als alle seine Rotationen (dies umfasst nicht automatisch Spalten mit der Periode ist kleiner als n ).

Mit Spalten, die als Binärzahlen 0 ≤ i <2 ^{n dargestellt werden} , sendet die Regel i zur kleinsten Drehung von i XOR ( i ⋅2). (Wenn ich kanonisch bin, ist sein hohes Bit Null und wir müssen uns hier nicht um den Umbruch kümmern.)

Also durchlaufen wir alle möglichen Spalten i , überprüfen die Kanonizität und wenden die Regel dann wiederholt an, bis wir eine Spalte finden, die wir zuvor besucht haben, wobei wir uns die erste solche überarbeitete Spalte merken. Genau eine Spalte in jedem Zyklus ist eine eigene erste überarbeitete Spalte.