Great!
Shooting for m < cx instead of m < x simplifies things a lot.
You get some local diversity in the “flip” residues by showing d_i and d_{i+1} are not in the same class. That explains, to some degree, why there’s so much more observable diversity than would be expected by random chance!
I’m unable to characterize the diversity otherwise … residues get repeated here and there, maybe not as frequently as you’d expect randomly, but more frequently than you want …
For this method to work, you really need to take m of the form 2^k-3^x with x>m/0.58 which we know is not possible. So it seems difficult to verify the diversity of residues.
A workaround is to choose m among the divisors of 2^k-3^x and such that m < 0.58x. For example, if we take k=249 and x=157, then m=67 is a suitable choice to check the method. Then we find that 11 residues are repeated twice among the first 66 residues. The first repetition occurs for d_{21} and we get all residues after 91 swaps. So it turns out that some repetitions cannot be ruled out. This is due to the fact that 67 is also a divisor of 2^{48}-3^{30}, 2^9-3^7 and 2^{12}-3^2. The last part of the proof is difficult to implement.
Maybe the value c=0.58 is simply too optimistic. Or maybe this method does not work at all and we should consider simultaneous swaps as in your third try…
I also really want a constructive way to create the parity vector v whose \beta(v) is a multiple of 2^k - 3^k. It’s so fun to do that for specific cases like 2^k - 3^x = 11.
(You can even start with the circuit, and move one or two “straggler” ones to the right until \beta is a multiple of 2^k-3^x. You just need a distinct “move-straggler pattern” for each kind of x mod n-1. That two-straggler plan works until you reach n=31, when you need a third straggler.)
Barring a constructive way to create v, a non-constructive proof might have to suffice …