It seems that the Pisano-Carry configuration needs more theoretical analysis and exploration. In fact, it needs a whole theory, because I can't find any. So I'm starting to map all the state spaces for register widths <= 16. I might find something interesting to help explore further...
First, let's see the size of the primary orbits.
Width states length ratio(%) 3 128 35 27.34 4 512 135 26.36 5 2048 84 0.41 6 8192 693 8.45 7 32768 1170 3.57 8 131072 115 0.08 9 524288 2600 0.49 10 2097152 524799 25.02 11 8388608 1046076 12.47 12 33554432 2062103 6.14 13 134217728 413028 0.3 14 536870912 66448450 12.37 15 2147483648 204484 0.001 16 8589934592 2147516415 25.0003
So it seems that the width of 16 bits is a magical value, a very very lucky one !
Another good candidate would be the width 10, with one orbit that is 2¹⁹+2⁹-1.
Less interesting candidates are 11 and 14.
The rest looks not promising at all.
It seems that the secondary orbits don't all start at the same index so let's further explore with orbits.c...
Width states orbit lengths orbits joins 2nd index 3 128 2x 35 2 2x28 7,0,0 4 512 2x 135 2 2x120 3,0,0 5 2048 4,42,84 16 6 8192 6x 693 6 673,670 7 32768 10 to 1170 26 8 131072 115 too many 9 524288 130,200,2600 114 10 2097152 524799 2 2x523776 3,0,0 11 8388608 197 to 1046076 8 12 33554432 29 to 2062103 14 13 134217728 206514, 413028 too many 14 536870912 50 to 66448450 8 15 2147483648 204484 too many 16 8589934592 2147516415 2 3,0,0
So all the sizes do not behave like the others... Width 8 looks like a lost cause. 3, 4 and 10 look like scale models of the 16 version.
Note : for ALL the cases so far, points outside of the existing orbits lead to another orbit, there is no "trajectory" longer than 1 step.
UPDATE 20210913
New computations yielded some more precise results.
bit orbit orbit Width Size count lengths 1 2 1 2 2 4 2 9 3 8 2 35 4 16 2 135 5 32 16 4,42,84 6 64 6 693 7 128 26 10 18 39 90 234 390 1170 8 256 572? 115 9 512 114 4,130,200,2600 10 1024 2 524799 11 2048 8 1046076,5844,179 12 4096 14 29,71107,2062103 13 8192 196 4, 206514, 413028 14 16384 8 50, 1328969, 66448450 15 32768 5251? 204484 16 65536 2 2147516415
.
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.
Who has a 64GB PC with 1 or 2h of CPU time ?
Are you sure? yes | no
You need someone with access to machines-to-be-tested in a data centre. Just two years back I could have run a test on a machine with 32 cores and 768GB RAM...
Just a hunch: maybe a HLL can help?
https://en.wikipedia.org/wiki/HyperLogLog
Are you sure? yes | no
with 768GB, I could go up to ...
8GB : 16 bits
32GB : 17
128 : 18
512: 19 bits
However such a size makes storage and transmission *hard*.
There is the possibility to use only 2 bits instead of 1 byte per state but then I will miss extra info such as the number of orbits.
I've slept on it and came to some heuristics to get the orbit structure without mapping the whole orbits in RAM, trading RAM for CPU time, and only recording states on the Y=0 column, like I did earlier.
Looking at HLL...
I'm not sure I get it but it is a different class of algo to learn :-)
It doesn't seem to be useful in my case but I'll keep it in mind.
Thanks @Thomas !
Are you sure? yes | no