|
%I #12 Jan 16 2023 11:15:34
%S 1,2,10,105,3823,2218961
%N Number of distinct binary sequences that can be generated by a general (non-linear) binary feedback shift register of length n, but not by a shorter one.
%C Complementary sequences (e.g.: 111010 and 000101) are taken to be equivalent. Related to maximum order complexity of sequences and also to number of incomplete paths in a De Bruijn graph.
%H C. J. A. Jansen, <a href="https://citeseerx.ist.psu.edu/pdf/027f953e004d0959f3d7fd0abfdad4d206bae451">Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods</a>, Ph.D. Thesis, Delft University of Technology, The Netherlands, 1989, pp. 58-81.
%e For n <= 2, the following sequences can be generated. The periodic part is shown in square brackets. Only sequences starting with 0 are shown, since complementary sequences are equivalent.
%e n | sequences
%e -------------
%e 0 | [0]
%e -------------
%e 1 | [01]
%e | 0[1]
%e -------------
%e 2 | [001]
%e | 0[01]
%e | [0011]
%e | 0[011]
%e | 00[1]
%e | 01[0]
%e | [010]
%e | 011[0]
%e | [0110]
%e | [011]
%Y Cf. A049539.
%K nonn,more
%O 0,2
%A Cees J. A. Jansen (cja(AT)iae.nl)
%E Name clarified, and a(5) from _Pontus von Brömssen_, Jan 12 2023
| 