[math-fun] opposite of Gray code
The "Gray code" is a fast way to produce the integers 0,1,2,..2^p-1 in an order such that each differs from predecessor in exactly 1 bit. Q1 (easy). Find an anti-Gray code where each differs from predecessor in exactly p-1 bits. Q2 (not so easy). Find a "mid-gray" code where each differs from predecessor in exactly p/2 bits (p>1 even). Note this is impossible if p is a multiple of 4. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Not so easy to do exactly---but you get a decent approximation by simply running a p-bit block cipher in counter mode. On Thu, May 29, 2014 at 3:47 PM, Warren D Smith <warren.wds@gmail.com> wrote:
The "Gray code" is a fast way to produce the integers 0,1,2,..2^p-1 in an order such that each differs from predecessor in exactly 1 bit.
Q1 (easy). Find an anti-Gray code where each differs from predecessor in exactly p-1 bits.
Q2 (not so easy). Find a "mid-gray" code where each differs from predecessor in exactly p/2 bits (p>1 even). Note this is impossible if p is a multiple of 4.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (2)
-
Mike Stay -
Warren D Smith