Binary and related representations Moser–de Bruijn sequence

plot of number of sequence elements



n


{\displaystyle n}

divided





n




{\displaystyle {\sqrt {n}}}

, on logarithmic horizontal scale

it follows either binary or base-4 definitions of these numbers grow in proportion square numbers. number of elements in moser–de bruijn sequence below given threshold



n


{\displaystyle n}

proportional





n




{\displaystyle {\sqrt {n}}}

, fact true of square numbers. in fact numbers in moser–de bruijn sequence squares version of arithmetic without carrying on binary numbers, in addition , multiplication of single bits respectively exclusive or , logical conjunction operations.

in connection furstenberg–sárközy theorem on sequences of numbers no square difference, imre z. ruzsa found construction large square-difference-free sets that, binary definition of moser–de bruijn sequence, restricts digits in alternating positions in base-



b


{\displaystyle b}

numbers. when applied base



b
=
2


{\displaystyle b=2}

, ruzsa s construction generates moser–de bruijn sequence multiplied two, set again square-difference-free. however,

this set sparse provide nontrivial lower bounds furstenberg–sárközy theorem.