# Adjacent Gray code

Gray code is permutation of $$\{0,1,2,\dots,2^n-1\}$$ such that each of consecutive number is differs only one bit in binary representation.

Example for $$n = 3$$

$$000\\ 001\\ 011\\ 010\\ 110\\ 111\\ 101\\ 100$$

Let $$s_k$$ is bit position of transition $$k$$ to $$k+1$$. In example for $$n=3$$ above are $$s_1=3,s_2=2,s_3=3,s_4=1$$ and so on

I define adjacent gray code is each consecutive number is differs in adjacent bit. It is, if $$s_k=j$$ than $$s_{k+1}$$ is $$j-1$$ or $$j+1$$

Example for $$n=4$$

$$0000\\ 0001\\ 0011\\ 0111\\ 0101\\ 0100\\ 0110\\ 0010\\ 1010\\ 1110\\ 1100\\ 1101\\ 1111\\ 1011\\ 1001\\ 1000$$

Can anyone design a good algorithm to look for adjacent gray code for $$n$$ large enough? Maybe it's acceptable for $$n\leq10$$

• Have you tried constructing such a code explicitly? – Yuval Filmus Mar 6 '19 at 15:54
• WLOG let each Gray code start at all zeroes. Then, for $n = 6$ there does not exist an adjacent Gray code in which the second number is $000001$ or $000010$. Only $000100$ works (and by symmetry $001000$). There does not exist an adjacent Gray code for $n = 7$ at all. – orlp Mar 13 '19 at 4:39
• @orlp how to prove for n=6, only 000100 works? – L Lawliet Mar 15 '19 at 13:30
• @LLawliet I used a brute force algorithm. – orlp Mar 16 '19 at 7:58
• @orlp what kind of BF algo are you using? My BF is just try all permutation and it took very long hours for n = 5 – L Lawliet Mar 17 '19 at 7:08