The last log 17. First image is a huge step forward because the 2D visualisation is not just cool-looking but also very information-rich. I will try to organise this new knowledge here, compare with what I knew or guesstimated before, and see where I can go from there.

We have seen that depending on the width parameter, different behaviours appear and not all are desirable. I'll only focus on the "interesting" ones, with widths= 3, 4, 10, 16... And from the little I have seen, I'll consider that their respective structures are identical, or at least obey to the same heuristics.

I expected something along the diagonal. There had to be something there to explain why the orbits had a 2^n + 2^m states, where m seemed related to n for various bit widths. Moreover, the very definition of the Fibonacci sequence says that Y gets the value of X after one step so X > Y, creating a sort of diagonal (with a slope of φ ?) ... But then, you have the wrap-around and carry, and when you keep swapping X and Y, you're simply oscillating around the diagonal line so some sort of symmetric structure had to happen.

Now, let's look at one small scale "model" of the kind of version that interests us, here with WIDTH=4 hence a size of 16. The coordinates are a bit unusual but you'll get used to it, and it's more a practical choice than guided by a theoretical constraint.

So you have a "raster scan" type of coordinates, with 2^WIDTH points horizontally, and 2^(WIDTH+1) vertically because the case of CARRY=1 must also be shown. The new 0 just appears in the middle of the rectangle, made of two squares...

The colour red shows the states belonging to the first orbit (going through 1,0,0) and the colour green show the second orbit. The darker colours correspond to the real orbits, while the brighter ones in the middle are the beginning of trajectories that directly lead to the corresponding orbit.

There are so many things to notice in this picture !

• Let's start with the obvious: the upper square is almost identical to the top square, just invert the bright/dark. The only differences I notice are at the borders. Well, this had to be expected because the addition works the same for every number, but the carry will shift the result to the right by one position.

• When "freewheeling", the orbits occupy the "dark corners" only. The upper-right one corresponds to X>=Y  (as happens during the first iterations of the Fibonacci sequence), while the lower-left one has X<=Y.

• The diagonal states belong to the orbits, which explains why the orbit lengths contain an additional 2^X term. The -1 corresponds to the "stuck state" which, as we have already proved (and has been computed), can't be reached without a big nudge.

• There is this striking central symmetry: For every state (X,Y+C*16), the state at (15-X, 31-(Y+C*16)) has the opposite colour ! Combined with the almost-identical translational copy of the squares, this is impressive and can help reduce storage space if more state mapping is required.

• So the red and green states have the same structure, the same "cardinality" (size), being perfect opposite, but we must also mention that they are not "clumped" together, they mesh nicely and evenly. This is just crazy, how/why can this be so ideal ?

From there, we can expect these heuristics to work for different widths, as observed in smaller versions, if we are looking for an "ideal" configuration:

• The orbit going through 1,0,0 MUST contain more than 1/4th of the states of the space.
• Similarly, you must be able to ride the complementary orbit with coordinates so that
  X1 + X2 = 15, Y1 + Y2 = 15, C1 + C2 =1
  So it's a complete parity rule: change one and you must change all the others (including colour).
  This second orbit inherits the properties of the first one, including its length.

Given that the complementarity is expected in the ideal case, the first rule is enough to verify that one configuration is ideal. So there is no "mapping" to do, no memory to allocate, only an orbit to ride to count its length.

For WIDTH=16, that makes 2³¹ iterations, which takes approximately 1 second on a recent CPU. The number of states quadruples with each incrementation of WIDTH, so the running times would be :

17   4s
18   16
19   1 min
20   4
21   16
22   1h
23   4h
24   16h
25   3 days

And this can not run in parallel !

The search for even larger ideal cases is important, as any new lucky find would provide far longer periods for RNGs, better use of the entropy in the 32-bit registers, stronger protection against alterations... A wonderful find would be 31 because it would enable the use of the "sign bit" of a signed integer, instead of the carry flag, to compare instead of using the carry bit.

I can make small tries by adapting the existing code but this would not be practical after WIDTH=21. Which widths sound like good candidates ? Of course a "bad" version will terminate early but I need more hints to select the larger candidates. So I turn to OEIS:

https://oeis.org/search?q=3,4,10,16

• A051437 : 1, 3, 4, 10, 16, 36, 64, 136, 256, 528, 1024, 2080, 4096, 8256, 16384,...
  "Number of undirected walks of length n+1 on an oriented triangle, visiting n+2 vertices, with n "corners"; the symmetry group is C3. Walks are not self-avoiding." Hmmm C3 sounds nice :-)
• A183527 :  1, 2, 3, 4, 10, 16, 17, 18, 19, 22, 64, 65, 66, 68, 69, 128,...
  "An Ulam-type sequence: a(n) = n if n<=4; for n>4, a(n) = least number > a(n-1) which is a unique sum of 4 distinct earlier terms." why not ?
• There are many more but don't seem related at all...

So I guess I have to run the CPU for a night and get more data before I can make an informed decision for more candidates.

If I get a longer list of "good numbers", I can refine my search for the appropriate existing theory that might be underlying.