Discrete Mathematics & Theoretical Computer Science (Dec 2002)
3x+1 Minus the +
Abstract
We use Conway's Fractran language to derive a function R: Z + → Z + of the form R(n) = r i n if n ≡ i mod d where d is a positive integer, 0 ≤ i < d and r 0,r 1, ... r d-1 are rational numbers, such that the famous 3x+1 conjecture holds if and only if the R-orbit of 2 n 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 { x 0, ... ,x m-1 } of positive integers for the 3x+1 function must satisfy ∑ i∈ E ⌊ x i/2 ⌋ = ∑ i∈ O ⌊ x i/2 ⌋ +k. where O={ i : x i is odd}, E={ i : x i 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.