Finding cycles of generalized 3x+1 functions

Then T(x) = ⌊m_ix ⁄ d⌋ + x_i, if x ≡ i (mod d).

We search all trajectories x, T(x), T²(x),... where |x| ≤ R ⁄ 2 = 60000 ⁄ 2 for cycling by Floyd's method of testing for equality of n^th and 2n^th iterates for n ≤ U = 1000000.
If |Tⁿ(x)| > J = 10¹², we suspect this trajectory to be divergent.

Caution: Because of the limitations of BCMATH on large array sizes, J will be too small for some mappings T.
For example, the 3-branched mapping T(x):= x ⁄ 3 if x ≡ 0 (mod 3), ⌊2x ⁄ 3⌋ if x ≡ 1 (mod 3), ⌊13x ⁄ 3⌋ if x ≡ 2 (mod 3), the trajectory {Tⁿ(47)} is declared divergent, which it is not.

Example. The 3x+1 mapping T(x)=x ⁄ 2 if x is even, (3x+1) ⁄ 2 if x is odd, corresponds to m₀=1, m₁=3, x₀=0, x₁=1. There appear to be 5 cycles, starting points 1, 0, -1, -5, -17.

Conjectures

1. There will be only finitely many (≥ 1) cycles.
2. If ∏_0≤i≤d-1 |m_i| < d^d, then all trajectories will eventually become periodic.
3. If ∏_0≤i≤d-1 |m_i| > d^d, then most trajectories will be divergent.

• We may miss some cycles, because at least one of R, J or U is not large enough. Initially I set R = 100000, but this caused memory problems. To get a better idea of the cycles, one should use the authors' faster and more powerful C program CALC.
• We display at most one apparently divergent trajectory - the one with smallest sized starting point.
• The presence of large trajectories makes the program very slow. In which case one should use CALC, especially if one wants to use a larger value for R.
• We choose the smallest sized cycle element as starting point.
• The viewer is given the option of viewing the complete cycles.
• We place an upper limit on the number of cycles - 100 and point out that
  • for large odd k, the 3x+k function can have many cycles;
  • there are examples of non relatively-prime type where there are infinitely many cycles eg. T(2x) = 2x+1, T(2x+1) = 2x.

Last modified 26th June 2006
Return to main page