M-Sequence Period

Problem

Simulate an n-bit shift register with the given feedback taps starting from the state [1, 0, ..., 0]. Each step computes the feedback as the XOR of the tapped bits and shifts it in at the front. Return the number of steps until the initial state repeats; return 0 if some state repeats before the initial state returns, which means the sequence is not maximal.

Hint

A maximal-length LFSR visits every nonzero state exactly once.

Test cases

case 1

in: [2,[0,1]]

expected: 3

case 2

in: [3,[0,2]]

expected: 7

case 3

in: [4,[0,3]]

expected: 15

case 4

in: [4,[1,3]]

expected: 6

case 5

in: [5,[1,4]]

expected: 31

Starter codePython

def m_sequence_period(n, taps):
    # Your code here
    pass

5 test cases · run your code against them in the editor