|
| |
|
|
A337742
|
|
Cycle length of applying XOR with the previous state and bit rotation on a string of n bits.
|
|
0
|
|
|
|
3, 6, 15, 12, 255, 30, 63, 24, 315, 510, 33825, 60, 159783, 126, 255, 48, 65535, 630, 14942265, 1020, 4095, 67650, 4194303, 120, 17825775, 319566, 1310715, 252, 23353884759, 510, 1023, 96, 1048575, 131070, 16777215, 1260, 7627861917807, 29884530, 5592405
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
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.
It appears that a(n) is divisible by 3 and n.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(2*n) = 2*a(n) (conjectured).
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.
|
|
|
EXAMPLE
|
For n=1, the cycle repeats after 3 steps: 0 -> 1 -> 1 -> 0.
For n=2, the cycle repeats after 6 steps: 00 -> 10 -> 01 -> 11 -> 01 -> 01 -> 00.
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.
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
