Indeed, in general with operators Implies , And and Or one gets to 2 n - 1 elements, while with operators Xor and Equal one gets to 2^(2Floor[n/2]) elements.

(It is much easier to implement in Mathematica—as discussed above—since there functions like BitXor can operate on integers of any length.)

And with DNF Boolean expressions (see page 1096 ) functions like Xor are known to require exponentially many terms, even—as discovered in the 1980s—if any limited number of levels are allowed (see page 1096 ).

Showing only the arguments to f , the pictures below illustrate how the flat functions Xor and And are confluent, while the non-flat function Implies is not.

The first n elements can be found efficiently using Module[{a = 1}, Table[First[IntegerDigits[ a, a = BitXor[a, BitOr[2a, 4a]]; 2, i]], {i, n}]] The sequence does not repeat in at least its first million steps, and I would amazed if it ever repeats, but as of now I know of no rigorous proof of this. ( Erica Jen showed in 1986 that no pair of columns can ever repeat, and the arguments on page 1087 suggest that neither can the center column together with occasional neighboring cells.)

Sierpiński pattern Other ways to generate step n of the pattern shown here in various orientations include: • Mod[Array[Binomial, {2, 2} n , 0], 2] (see pages 611 and 870 ) • 1 - Sign[Array[BitAnd, {2, 2} n , 0]] (see pages 608 and 871 ) • NestList[Mod[RotateLeft[#] + #, 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • NestList[Mod[ListConvolve[{1, 1}, #, -1], 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • IntegerDigits[NestList[BitXor[2#, #] &, 1, 2 n - 1], 2, 2 n ] (see page 906 ) • NestList[Mod[Rest[FoldList[Plus, 0, #]], 2] &, Table[1, {2 n }], 2 n - 1] (see page 1034 ) • Table[PadRight[ Mod[CoefficientList[(1 + x) t - 1 , x], 2], 2 n - 1], {t, 2 n }] (see pages 870 and 951 ) • Reverse[Mod[CoefficientList[Series[1/(1 - (1 + x)y), {x, 0, 2 n - 1}, {y, 0, 2 n - 1}], {x, y}], 2]] (see page 1091 ) • Nest[Apply[Join, MapThread[ Join, {{#, #}, {0 #, #}}, 2]] &, {{1}}, n] (compare page 1073 ) The positions of black squares can be found from: • Nest[Flatten[2# /.

Each is roughly of the form BitXor[u[t], s[t]] Sin[ ω t] , where u[t] is a pseudonoise (PN) sequence generated by a linear feedback shift register (LFSR) (see page 1084 ); the idea is that by using a different PN sequence for each signal the corresponding s[t] can be recovered even if thousands are superimposed.

(For Xor , there are 2 possible σ , while for Or there are 3.)