Discrete Mathematics & Theoretical Computer Science, Vol 5 (2002)

Font Size:  Small  Medium  Large

3x+1 Minus the +

Kenneth G. Monks


We use Conway's Fractran language to derive a function R:Z+ → Z+ of the form R(n) = rin  if  n ≡ i &bmod; d where d is a positive integer, 0 ≤ i < d and r0,r1, ... rd-1 are rational numbers, such that the famous 3x+1 conjecture holds if and only if the R-orbit of 2n contains 2 for all positive integers n. We then show that the R-orbit of an arbitrary positive integer is a constant multiple of an orbit that contains a power of 2. Finally we apply our main result to show that any cycle { x0, ... ,xm-1 } of positive integers for the 3x+1 function must satisfy
∑i∈ E ⌊ xi/2 ⌋ = ∑i∈ O ⌊ xi/2 ⌋ +k.
where O={ i : xi  is odd } , E={ i : xi  is even } , and k=|O|.
The method used illustrates a general mechanism for deriving mathematical results about the iterative dynamics of arbitrary integer functions from Fractran algorithms.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page