s(n) = • n if n mod 4 = 0, • 1 if n mod 4 = 1, • n + 1 if n mod 4 = 2, • 0 if n mod 4 = 3. Or alternatively: • s(4n) = 4n • s(4n + 1) = 1 • s(4n + 2) =

s(n) = • n if n mod 4 = 0, • 1 if n mod 4 = 1, • n + 1 if n mod 4 = 2, • 0 if n mod 4 = 3. Or alternatively: • s(4n) = 4n • s(4n + 1) = 1 • s(4n + 2) = 4n + 3 • s(4n + 3) = 0 Proof by induction: • s(4n + 1) = s(4n) ⊕ (4n + 1) = 4n ⊕ (4n + 1) = 1 • s(4n + 2) = s(4n + 1) ⊕ (4n + 2) = 1 ⊕ (4n + 2) = 4n + 3 • s(4n + 3) = s(4n + 2) ⊕ (4n + 3) = (4n + 3) ⊕ (4n + 3) = 0 • s(4n + 4) = s(4n + 3) ⊕ (4n + 4) = 0 ⊕ (4n + 4) = 4n + 4