Puzzle

I think that one gets the maximum randomness if on average half the bits change on each step. The crypto folk worry about such things a lot. As do the sparse neural code folk.

Joe Gwinn

What I mean is very non-random because it would change more than half if possible.

I couldn't do it in my head, but working it out for the 4 bit case shows that the maximum n is 3, and using the next gray code complemented does cycle through all codes.

Well, if a gray code changes only one bit yet gets through all possible codes, then it's possible to change all-but-one bit and also get through all possible codes. All you have to do is to compute the gray code, and your result is the result of xor-ing each code with its preceding one.

Clifford Heath

I think you wanna find the path along the edges of a graph like this:

That visits all vertices only once and also maximizes the distance traveled. Sort of the inverse traveling-salesman problem. I can't do it in my head even for three bits.

And like Gray codes there's likely more than one equally valid solution for any particular (hyper)cube.

Anti-Gray codes:

It's clear than n cannot be equal to the word size. So, can one prove that it's possible with n = word size - 1?

For a word size of k bits, assume that there is a sequence of 2^k - 1 steps that starting from all zeros, visits every combination once, with the final combination being all ones. Further assume that each step involves flipping at least k - 1 bits.

Now introduce a new bit that also starts at zero. For each step, flip that bit. Since the previous sequence of 2^k - 1 steps flipped at least k - 1 bits, this means that now each step flips at least k bits.

The odd number of steps means that new new bit is now a one. On the next step, flip all of the other bits, but leave the new one alone. Since all the other bits are flipped, that step also flipped at least k bits, and those bits are returned to zero.

Now repeat the above process of flipping the new bit together with at least k - 1 of the other bits, in the same sequence as before. For each step, where the new bit was previously zero, it is now a one, and vice versa, so each combination of the k + 1 bits is visited for the first time.

The last step changes the original k bits to 1, and leaves the new bit as a one.

So, if it's possible for k bits, it's also possible for k + 1 bits.

Now consider the case for k = 2. We can use the sequence 00 01 10 11. So it is possible for k = 2.

This proves by induction that it is possible for all k.

Sylvia.

Related paper:

I think I missed the bit where you proved that the the new sequence visits all states.

We use the same sequence for the initial k bits, twice, and ex hypotesi it visits every combination of the k bits on each pass.

Adding a bit that is alternately 0, then 1, for the first pass of the k bits, and then alternately 1, then 0, for the second pass means that each combination of the k bits has been visited with the additional bit being both 0 and 1. Thus all combinations of the k + 1 bits are visited.

Sylvia.

Ugh, that's completely wrong of course. What I meant was that you complement the gray code, so instead of one bit changing, every bit bit one does.

Ok, that didn't work. But I did search and find the answer... that there is no easy answer. See the following:

Clifford Heath

This is an unsolved problem. See

in addition to the stackexchange page I linked to.

CH

I don't think finding a sequence that maximizes the minimum Hamming distance between consecutive pairs of elements, is the same problem as finding a sequence which maximizes the total of the Hamming distance across pairs of consecutive elements, out of any permutation of all the elements, that is to say the maximum overall path length of the sequence.

It's the latter problem that gets you the maximum number of bits that change at each step or an "anti-Gray" code. You can get an anti-Gray code from any Gray code by applying a sorting function based on the Gray code itself:

I think in the first problem you must inspect the taxicab distance at each step like a vector, the second you're just maximizing the total path length traveled on the graph you don't have to enforce constraints on each step additionally.

The taxicab distance to all other elements of the set, rather. That's why brute force for that one goes factorial on you when you're working with an n-cube.

By any chance was your sequence the same as the original sequence but with every other gray code inverted?

This is more complicated than I expected. It got more attention than I expected too.

By traversing a 3D cube it's easy to see why you can't visit every vertex with diagonals that represent 2-bit changes. You need two 3-bit changes also, which is good, but I don't see a way to generalize the sequence.

000 3 bits 011 2 bits 110 2 bits 101 2 bits 010 3 bits 100 2 bits 001 2 bits 111 2 bits

The method I described initially, looking at each code as gray to get the next code, but complementing the next, works for 4 bits but not 3 or

1. I tried a few other approaches that don't work at all. I'll look at the methods suggested here.

bin gray next gray complemented

000 0 000 0 000 0 001 1 001 1 110 6 010 2 011 3 000 0 011 3 010 2 110 6 100 4 110 6 000 0 101 5 111 7 110 6 110 6 101 5 000 0 111 7 100 4 110 6

bin gray next gray complemented

0000 0 0000 0 0000 0 0001 1 0001 1 1110 E 0010 2 0011 3 0101 5 0011 3 0010 2 1011 B 0100 4 0110 6 0110 6 0101 5 0111 7 1000 8 0110 6 0101 5 1111 F 0111 7 0100 4 0001 1 1000 8 1100 C 1100 C 1001 9 1101 D 0010 2 1010 A 1111 F 1001 9 1011 B 1110 E 0111 7 1100 C 1010 A 1010 A 1101 D 1011 B 0100 4 1110 E 1001 9 0011 3 1111 F 1000 8 1101 D 0000 0

bin gray next gray complemented

00000 00 00000 00 00000 00 00001 01 00001 01 11110 1E 00010 02 00011 03 00000 00 00011 03 00010 02 11110 1E 00100 04 00110 06 00110 00 00101 05 00111 07 11110 1E 00110 06 00101 05 01111 00 00111 07 00100 04 11110 1E 01000 08 01100 0C 01100 00 01001 09 01101 0D 11110 1E 01010 0A 01111 0F 00000 00 01011 0B 01110 0E 11110 1E 01100 0C 01010 0A 00000 00 01101 0D 01011 0B 11110 1E 01110 0E 01001 09 00110 00 01111 0F 01000 08 11110 1E 10000 10 11000 18 01111 00 10001 11 11001 19 11110 1E 10010 12 11011 1B 01100 00 10011 13 11010 1A 11110 1E 10100 14 11110 1E 00000 00 10101 15 11111 1F 11110 1E 10110 16 11101 1D 00000 00 10111 17 11100 1C 11110 1E 11000 18 10100 14 00110 00 11001 19 10101 15 11110 1E 11010 1A 10111 17 01111 00 11011 1B 10110 16 11110 1E 11100 1C 10010 12 01100 00 11101 1D 10011 13 11110 1E 11110 1E 10001 11 00000 00 11111 1F 10000 10 11110 1E

No, some are inverted and some are the same as gray.

bin gray next gray complemented

0000 0 0000 0 0000 0 0001 1 0001 1 1110 E 0010 2 0011 3 0101 5 0011 3 0010 2 1011 B 0100 4 0110 6 0110 6 0101 5 0111 7 1000 8 0110 6 0101 5 1111 F 0111 7 0100 4 0001 1 1000 8 1100 C 1100 C 1001 9 1101 D 0010 2 1010 A 1111 F 1001 9 1011 B 1110 E 0111 7 1100 C 1010 A 1010 A 1101 D 1011 B 0100 4 1110 E 1001 9 0011 3 1111 F 1000 8 1101 D 0000 0

You're in good company. some very good mathematicians have also tried and failed.

BTW the word for an n-D cube is tesseract.

I recently solved a mathematical problem that has some similar characteristics, which was to determine which numbers N have reciprocals that are maximum-length (length N-1) repeating decimals. It turns out to be linked to prime factors are other funky stuff.

Anyhow no-one knows how to construct a formula for this one. If you solve it, you'll be famous!

Clifford Heath

I thought a tesseract is specifically 4D and the generic name for n-D is hypercube.

Oh fun.

I think I got the answer for even numbers of bits but don't have a proof, not that it's a new solution.