This question is motivated by [Linear Feedback Shift Registers](https://en.wikipedia.org/wiki/Linear-feedback_shift_register), which cycle through $\{0,1\}^n \setminus \{(0,\ldots,0)\}$ by shifting and applying a small set of XOR operations.


Let $n>1$ be an integer. To any map $f:\{0,1\}^{n} \to \{0,1\}$ we associate a "shifting function" $\sigma\_f: \{0,1\}^n\to \{0,1\}^n$ by $$(b\_0, b\_1, \ldots, b\_{n-1}) \in \{0,1\}^n \; \mapsto \; \big(b\_1, b\_2, \ldots, b\_{n-1}, f(b\_0,b\_1,\ldots,b\_{n-1})\big).$$


**Question.** For what positive integers $n > 1$ is there $f:\{0,1\}^n\to \{0,1\}$ such that $\sigma\_f:\{0,1\}^n \to \{0,1\}^n$ is a [cyclic permutation](https://en.wikipedia.org/wiki/Cyclic_permutation) of $\{0,1\}^n$ having length $2^n = |\{0,1\}^n|$?



Cycling through $\{0,1\}^n$ by shifting and applying a $n$-ary function
Such $f$ exist for all $n.$


The resulting sequences are de Bruijn sequences. Let $a=(a₀, a₁,\ldots )$ be a periodic sequence of period
$T$ with symbols taken from a finite alphabet $A.$


**Definition** The sequence $a$ is a de Bruijn sequence of span $n$ if every block of length $n$
occurs exactly once in (each period of) $a.$


It is straightforward to show that:


**Proposition** Suppose $a$ is a de Bruijn sequence of span $n.$ Then


1. The period of $a$ is $T = | A|^n$.
2. For any $t \leq n$ and for any block $b$ of length $t$ , the number of occurrences of $b$
within a single period of $a$ is $| A|^{n−t}.$


Letting $n=t,$ each block (subsequence) of length $n$ occurs exactly one so a function $f$ that you want can always be defined. for any alphabet size $|A|.$


One can also construct a de Bruijn sequence of span $n+1$ from one of span $n$ recursively. There are many de Bruijn sequences but an algebraic classification of functions yielding them in the general case is lacking, though some function families exists. Books by Golomb (Shift Register Sequences) and Goresky/Klapper (Algebraic Shift Register Sequences) cover some of this topic.


A linear $n-$variable function (LFSR) stated algebraically won't give full period. For an introduction to NLFSRs (which is what you ask) focusing on the important binary alphabet, you can start with Helleseth's talk in the slides linked below and follow the references. Some keywords for sequence families are GMW sequences, WG sequences.


[Helleseth survey talk](https://www.ricam.oeaw.ac.at/specsem/specsem2013/workshop4/slides/helleseth.pdf)


