login
Cycle length of applying XOR with the previous state and bit rotation on a string of n bits.
0

%I #37 Jun 16 2022 10:25:17

%S 3,6,15,12,255,30,63,24,315,510,33825,60,159783,126,255,48,65535,630,

%T 14942265,1020,4095,67650,4194303,120,17825775,319566,1310715,252,

%U 23353884759,510,1023,96,1048575,131070,16777215,1260,7627861917807,29884530,5592405

%N Cycle length of applying XOR with the previous state and bit rotation on a string of n bits.

%C Begin with a string of n 0's. As the first step, change the string's first 0 to a 1. For each succeeding step, if a bit was changed during the previous step, set the next bit to 1; otherwise set the next bit to 0. (Wrap around to the beginning of the string as the final bit's "next bit".) Count the steps until the string reaches all 0's, with 00..001 at the preceding step, so it will repeat as from the start.

%C It appears that a(n) is divisible by 3 and n.

%F a(2*n) = 2*a(n) (conjectured).

%F Conjecture: a(n) = 2^A007814(n) * (2^A007733(n) + q) * k, where q = -1 if n is in A038837, otherwise q = 1. General formula for k is unknown.

%e For n=1, the cycle repeats after 3 steps: 0 -> 1 -> 1 -> 0.

%e For n=2, the cycle repeats after 6 steps: 00 -> 10 -> 01 -> 11 -> 01 -> 01 -> 00.

%e For n=3, the cycle repeats after 15 steps: 000 -> 100 -> 010 -> 011 -> 100 -> 111 -> 101 -> 001 -> 010 -> 101 -> 111 -> 001 -> 011 -> 001 -> 001 -> 000.

%o (PARI) a(n) = {my(v1 = vector(n), v2 = vector(n), v3, w1 = v1, pos = 1, nb=1, w2); v2[1] = 1; w2 = Vecrev(v2); while (1, v3 = vector(n, k, bitxor(v1[k], v2[k])); v1 = v2; v2 = vector(n, k, if (k==1, v3[n], v3[k-1])); nb++; if ((v2 == w1) && (v1 == w2), return(nb)););} \\ _Michel Marcus_, Jun 09 2021; corrected Jun 16 2022

%Y Cf. A007733, A007814, A038837.

%K nonn,hard

%O 1,1

%A _Artem Yashin_, Sep 17 2020