International Journal of Mathematics and Mathematical Sciences
Volume 2010 (2010), Article ID 458563, 6 pages
Research Article

The 3 𝑥 + 1 Problem as a String Rewriting System

Quatronet Corporation, 50 Almond Ave, Thornhill, Ontario, L3T 1L2, Canada

Received 11 May 2010; Accepted 31 December 2010

Academic Editor: Kenneth Berenhaut

Copyright © 2010 Joseph Sinyor. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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.