Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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