Find Diffy Games

Question

A fun game to play if you are bored is the Diffy Game. It is a one player game that is pretty simple and can consume a good deal of your time.

The Diffy game works like as follows: You start with a list of non-negative integers, in this example we will use

3 4 5 8

Then you take the absolute difference between adjacent numbers

 (8)  3   4   5   8
    5   1   1   3

Then you repeat. You repeat until you realize you have entered a loop. And then generally the game starts from the beginning again.

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

Often the game has no goal, you are just biding time by doing arithmetic in your head. However when I have the pleasure of playing this game my goal is always to try and pick a period and try to construct a game that loops with that particular period.

Not all games are periodic, the example above is not periodic for example because it eventually reaches a game with all zeros and thus can never make it back to its starting position. In fact it seems that the vast majority of games are not periodic making the few games that are a rare gem.

---

Given a game that loops with a particular period it is trivial to make another game that loops with the same period by just doubling the sequence. For example the game:

1 0 1

Plays out exactly the same as the game:

1 0 1 1 0 1

In fact, we can consider that both are really the infinitely repeating game:

... 1 0 1 ...

We will consider them one game for the sake of this challenge.

In a similar fashion multiplying the entire sequence by a constant will also trivially preserve the period so we once again are going to count any two games that differ by a constant factor to be the same game.

---

The infinite strings ... 1 0 1 ... and ... 0 1 1 ... are obviously the same string shifted by one character. We will not count these as different games, but when one reaches the other it will not be considered the end of the cycle when determining the period of a game. For example:

The two games

... 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

and

... 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

are both games with period 6. They share no term with each other at any point in their loops (unlike ... 1 1 0 ... and ... 1 0 1 ... which reach each other) but because they are shifted versions of each other they are considered the same game when counting.

---

Reflecting (or reversing) an infinite string gives essentially the same behavior, but does not necessarily give the same period. Consider, for example,

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

and its reflection

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

If we considered the next generation to be produced at a half-way point between the characters:

... 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 ...

then both would have shifted position by 3.5 elements. However, we don't consider the next generation to be produced with that half-element offset, so one rounds up to a 4-element shift giving a period of 15, and the other rounds down to a 3-element shift giving a period of 5.

For this reason we consider an asymmetric string and its reflection to be distinct, even though the cycles are in some sense isomorphic. Of course, if they form part of the same cycle then it only counts as one cycle.

---

With these restrictions a little mathematics can show that there are in fact a finite number of Diffy cycles with any given finite period. Moreover, every infinite string with a finite period is an infinite repetition of a finite string.

Note that the strings can be larger or shorter than the periods. For example, there is a string of length 5 with period 15, and a string of length 15 with period 5. All of the strings with period 19 are of length 9709.

Task

Given a number n such that n is larger than 1 via standard input methods determine the number of distinct Diffy cycles with a period of exactly n.

(It seems that, in the literature, 0 is often not considered a periodic Diffy game. Since this is a gray area I will not ask you to solve for n = 1)

This is code-golf, so the goal is to minimize the number of bytes in your source code.

Test Cases

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

Hints

All Periodic diffy games will contain only zero and a single constant, this means every periodic game will be isomorphic to some diffy game consisting only of zeros and ones.

Answer 1

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))

Try it online!

How it works

The rules that transform each row of a binary diffy game into the next row are the same as the rules that transform each column into the next column. Therefore, it suffices to find all distinct cycles within the graph of all canonical length-n columns, where a column is “canonical” if it is lexicographically smaller than all of its rotations (this automatically excludes columns with period smaller than n).

With columns represented as binary numbers 0 ≤ i < 2ⁿ, the rule sends i to the smallest rotation of i XOR (i⋅2). (If i is canonical, its high bit is zero and we do not need to worry about wraparound here.)

So we loop through all possible columns i, check for canonicity, then repeatedly apply the rule until we find a column we’ve visited before, memoizing the first such revisited column. Exactly one column in each cycle will be its own first revisited column.