A049538 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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”).

Other ways to Give

A049538

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.

1, 2, 10, 105, 3823, 2218961

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=0..5.

C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph.D. Thesis, Delft University of Technology, The Netherlands, 1989, pp. 58-81.

EXAMPLE

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.

n | sequences

-------------

0 | [0]

-------------

1 | [01]

| 0[1]

-------------

2 | [001]

| 0[01]

| [0011]

| 0[011]

| 00[1]

| 01[0]

| [010]

| 011[0]

| [0110]

| [011]

CROSSREFS

Cf. A049539.

Sequence in context: A273965 A273961 A365507 * A217901 A127728 A306064

Adjacent sequences: A049535 A049536 A049537 * A049539 A049540 A049541

KEYWORD

nonn,more

AUTHOR

Cees J. A. Jansen (cja(AT)iae.nl)

EXTENSIONS

Name clarified, and a(5) from Pontus von Brömssen, Jan 12 2023

STATUS

approved