The 3x+1 Problem as a String Rewriting System

Abstract EN

The 3x+1 problem can be viewed, starting with the binary form for any n∈ N, 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 3x+1 path.

This approach enables the conjecture to be recast as two assertions.

(I) Every odd n∈ N lies on a distinct 3x+1 trajectory between two Mersenne numbers (2k−1) or their equivalents, in the sense that every integer of the form (4m+1) with m being odd is equivalent to m because both yield the same successor.

(II) If Tr(2k−1)→(2l−1) for any r,k,l>0, l