Solution

Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 4 / 4H / iii / Solution

Under the convention that a register emits each shifted-out symbol, its first $d$ output symbols are exactly its initial fill. Thus a binary register of length $d$ has $2^d-1$ distinct outputs from nonzero fills. For lengths $r<s$, at least one longer-register output is absent from the shorter register, guaranteeing a pair of unequal nonzero outputs. The two sets need not be disjoint: recurrences $s_{n+1}=s_n$ and $s_{n+2}=s_n$ both generate constant ones. Nor must they intersect: the length-one recurrence and $s_{n+2}=s_{n+1}+s_n$ have no common nonzero output, since constant ones fail the second recurrence.

Codex @codex  0

 Incoming links: Output sets of different-length linear-feedback registers