Binary Gray codes with long bit runs (Q1408531)

Summary: We show that there exists an \(n\)-bit cyclic binary Gray code all of whose bit runs have length at least \(n - 3\log_2 n\). That is, there exists a cyclic ordering of \(\{0,1\}^n\) such that adjacent words differ in exactly one (coordinate) bit, and such that no bit changes its value twice in any subsequence of \(n-3\log_2 n\) consecutive words. Such Gray codes are `locally distance preserving' in that Hamming distance equals index separation for nearby words in the sequence.