%I #18 Oct 14 2020 10:59:40

%S 1,2,3,2,4,2,2,4,6,2,4,4,2,6,4,4,8,4,2,6,2,4,8,2,4,8,4,2,6,2,2,8,14,2,

%T 6,4,8,8,4,6,6,8,12,4,4,2,8,6,2,12,8,2,8,8,2,4,4,2,4,12,6,4,6,10,20,2,

%U 4,8,2,12,6,2,2,6,4,8,16,8,2,8,4,4,16,2

%N Number of output sequences from the linear feedback shift register whose feedback polynomial coefficients (excluding the constant term) correspond to the binary representation of n.

%C a(n) > 1 for n > 0.

%C It appears that every term after a(2) is even.

%C It appears that a(2^n) is greater than each preceding term and is greater than or equal to each term up to a(2^(n+1)).

%C If a(n) = 2, then the nonzero shift register sequence is an m-sequence.

%e For n = 3 = 11 in binary, the polynomial is 1+x+x^2 and the 2 shift register sequences are {00..., 01101...}.

%e For n = 4 = 100 in binary, the polynomial is 1+x^3 and the 4 shift register sequences are {000..., 001001..., 011011..., 111...}.

%e For n = 6 = 110 in binary, the polynomial is 1+x^2+x^3 and the 2 shift register sequences are {000..., 0010111001...}.

%e For n = 10 = 1010 in binary, the polynomial is 1+x^2+x^4 and the 4 shift register sequences are {0000..., 0001010001..., 0011110011..., 0110110...}.

%e For n = 11 = 1011 in binary, the polynomial in 1+x+x^2+x^4. Using a Fibonacci LSFR, if the current state of the register is 0001, the next input bit is 0+0+1=1, and the next state is 0011. If the current state is 0100, the next input bit is 0+0+0=0, and the next state is 1000. The 4 shift register sequences are {0000..., 00011010001..., 00101110010..., 1111...}.

%Y a(2^n) = A000031(n+1).

%Y A011260 counts how many 2's are in the interval [2^(n-1),(2^n)-1].

%Y a(n) = 2 if and only if 2n+1 is in A091250.

%Y Cf. A100447, A001037, A000016, A000013 (definition 2), A000020, A058947.

%Y Cf. A011655..A011751 for examples of binary m-sequences.

%K nonn,base

%O 0,2

%A _Michael Schwartz_, Aug 27 2020