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

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

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

Table of n, a(n) for n=1..39.

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

Cf. A007733, A007814, A038837.

Sequence in context: A285948 A285835 A285823 * A066904 A310124 A059969

Adjacent sequences: A337739 A337740 A337741 * A337743 A337744 A337745

Keyword

nonn,hard

Author

Artem Yashin, Sep 17 2020

Status

approved