@oros I like your method so much, maybe we can go for a general proof?
We are trying to convert the assertion 2^k - 3^x = n (for some n<x) into a Collatz cycle.
We start with some parity sequence v and flip various instances of 10 to 01 until we reach some \beta(v^\prime) \equiv 0 \mod n.
It’s a great strategy to prove that the differences produced by individual flips cover all residues. Then one of the flips will combine with \beta(v) to make \beta(v^\prime) \equiv 0 \mod n.
And ensuring distinct residues by spacing the flips in an arithmetic progression – yeah! This is great, especially the part where 3^{x-2m} \equiv 3^x. And we can rely on 3 being coprime with n.
One problem is that n might be close to x (our original assertion only required n<x), which raises two questions:
-
having just a bit over x/2 flips can’t cover all the residues of n
-
those flips won’t be in an arithmetic progression in the Sturmian word base v
For point 2, let’s trying dropping the Sturmian word, and use this simpler construction as a base v instead:
(110)^{\lfloor x/2 \rfloor}(0|1)0^*
Now we get the arithmetic progression back. It’s funny that the (110)^* idea was part of my hand solution for n=5.
In this case, I don’t think we need the k = \lceil x \log_2(3) \rceil restriction anymore. More 1s will result in a negative cycle, and if we have fewer ones, we just replace some 110 with 010, preserving the flip locations. (But thank you for reminding me to start a topic on whether k = \lceil x \log_2(3) \rceil is ok, which I will do!)
For point 1, I think > x/2 flips should actually suffice if the residues are all distinct, because in that case, the sum of the differences produced by 2 flips (suitably chosen) should provide the right residue to force \beta(v^\prime) \equiv 0 \mod n.
Suppose \beta(v) \equiv c, and the flip-difference mods are \{d_1, d_2, \ldots d_m\}. Consider also a parallel list \{-c-d_1, -c-d_2, \ldots -c-d_m\}.
Since m > x/2 > n/2, there will be at least one overlap in the values of the two lists. Its location in the first list gives us one flip, and its location in the second list gives us the other flip. For example, if d_1 = - c - d_2, then \beta(v^\prime) = c + d_1 + d_2 = c + (- c - d_2) + d_2 \equiv 0 \mod n.
It seems surprising that two flips on a simple, regular parity sequence would be enough to turn the equation into a Collatz counter-example … interested in any comments …