The 3𝑥+1 Problem as a String Rewriting System - Joseph Sinyor (International Journal of Mathematics and Mathematical Sciences)
The 3𝑥+1 problem can be viewed, starting with the binary form for any 𝑛∈𝐍, as a string of “runs” of 1s and 0s, using methodology introduced by Błażewicz and Pettorossi in 1983. A simple system of two unary operators rewrites the length of each run, so that each new string represents the next odd integer on the 3𝑥+1 path. This approach enables the conjecture to be recast as two assertions. (I) Every odd 𝑛∈𝐍 lies on a distinct 3𝑥+1 trajectory between two Mersenne numbers (2𝑘−1) or their equivalents, in the sense that every integer of the form (4𝑚+1) with 𝑚 being odd is equivalent to 𝑚 because both yield the same successor. (II) If 𝑇𝑟(2𝑘−1)→(2𝑙−1) for any 𝑟,𝑘,𝑙>0, 𝑙<𝑘; that is, the 3𝑥+1 function expressed as a map of 𝑘's is monotonically decreasing, thereby ensuring that the function terminates for every integer.