The generalized 3x+1 mapping: George Leigh's approach

1. Introduction
2. The generalized 3x+1 function
3. The motivating example
4. Definitions
5. The crucial lemma
6. The main theorem
7. The Markov matrix Q(m)
8. An example from paper [3]
9. A finiteness theorem of G. Venturini
10. A BCMATH program for constructing Q(m) and finding its irreducible closed sets
11. Some examples of G. Venturini
12. BCMATH cycling-finding program.
13. References

This online paper is based on a paper of paper [3] of George Leigh which generalized papers [1,2] by Tony Watts and myself.

George came up with his generalization in the course of doing an honours thesis in 1983. He had in the previous year done a course in Markov chains with Barry Quinn and amazed me by coming up with a Markov chain explanation of the behaviour of 3x+1 type mappings that could not be dealt with by the Matthews-Watts heuristics. George worked over the l-adic integers, where l = lcm(d, m) (see below). This is because of the need to work in a probability space.

However, in my account, I am avoiding the language of Markov chains and we can avoid l-adic integers and work with ordinary congruence classes of integers. Also it seemed simpler to assume that d divides m, so that l = m.

My proof of the main theorem is different from his and is modelled on the one given in my online generalized 3x+1 paper. I have left out details and hope it is correct. The reader may prefer Leigh's proof, which gave me a lot of problems at one stage.

When preparing my generalised 3x+1 survey while on sabbatical in Cambridge in late 1993, due to my tenuous understanding of George's Markov chain approach, I had difficulties in guessing the correct conjectures below which involve S_C. This set seemed to be an appropriate generalization of the Matthews-Watts ergodic set. I wanted to be able to assert that either all trajectories starting in this set either eventually cycled, or else that most diverged.

However I have to confess that I really haven't done enough experimental work to justify what is probably only wishful thinking. It may be safer to merely state things in terms of trajectories starting in a single congruence class.

Also while George had a heuristic section in dealing with any infinite Markov chains that might arise, this was outside my interest or understanding and I have limited my heuristics to the case where his chains are finite.

The only person who seems to have followed up on George's paper was the late G. Venturini who clearly had great insights into George's work. (See paper [4] below.) His paper contains a number of interesting examples and deals only with the important case of m = d. Also he came up with a sufficient condition for the chains to be finite. He defines on page 187 g-ergodic sets, which seem to be our S_C below. Also he had an example where unexpectedly S_C ⊆ S_C'.
Venturini's paper is based on Leigh's Markov chain X_n(x), rather than Y_n(x) and like Leigh, his matrix examples are given for the X_n(x) chain.

Leigh claims that the transition matrix for the X_n(x) chain is smaller in general that that for the Y_n(x) chain. However I prefer the latter, as it generalises the Matthews-Watts Q(m), in the case where d divides m.

I have written an online BCMATH version of Leigh's fortran program for the Y_n(x) Markov matrix Q(m).

T(x) = (m_ix - r_i) ⁄ d if x ≡ i (mod d).

Paper [1] assumes (a) gcd(m_i, d) = 1 for 0 ≤ i ≤ d-1.
Paper [2] assumes either (a) holds or (b) gcd(m_i, d²) = gcd(m_i, d) for 0 ≤ i ≤ d-1 and d divides m.

T(x) = :

12x - 1	if x ≡ 0 (mod 4)
20x	if x ≡ 1 (mod 4)
(3x - 6) ⁄ 4	if x ≡ 2 (mod 4)
(x - 3) ⁄ 4	if x ≡ 3 (mod 4).

Next observe: if x ≡ 0 (mod 4) (state 0)

• T(x) &equiv -1 (mod 16) (state 4)
• T²(x) &equiv -1 (mod 4) (state 3)

• T(x) &equiv 4 (mod 16) (state 5)
• T²(x) &equiv -17 (mod 64) (state 6)
• T³(x) &equiv -5 (mod 16) (state 7)
• T⁴(x) &equiv -2 (mod 4) (state 2).

0	0	0	0	1	0	0	0
0	0	0	0	0	1	0	0
¼	¼	¼	¼	0	0	0	0
¼	¼	¼	¼	0	0	0	0
0	0	0	1	0	0	0	0
0	0	0	0	0	0	1	0
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0

A is primitive (A⁸ is a positive matrix) and its stationary vector is (·1, ·1, ·2, ·2, ·1, ·1, ·1, ·1).

Notice that as sets,

• state 4 ⊆ B(3, 4),
• state 5 ⊆ B(0, 4),
• state 6 ⊆ B(3, 4),
• state 7 ⊆ B(3, 4).

(·1 + ·1, ·1, ·2, ·2 + ·1 + ·1 + ·1) = (·2, ·1, ·2, ·5).

We will eventually see how A allows us to calculate card_4ⁿ⁺¹{B(i, 4) &cap T^-n(B(j, 4))} where t = card_m(A) means that A is composed of t congruence classes (mod m).

The trajectory starting with 21 appears to be divergent.
We note that there appear to be 6 cycles, with starting numbers (and lengths) -1 (1), 5(81), -19(86), -4(3), -6(1), 19133(342).

Definition. For non-zero integers x, integers C(x) and D(x) ≥ 1, are defined by

x = C(x)D(x), where gcd(C(x), d) = 1 and D(x) is a divisor of some power of d.

As George Leigh pointed out in his paper, the condition gcd(m_i,d²)=gcd(m_i,d) is equivalent to d_i divides d.

From now on we assume that d divides m. Also [a, b] denotes lcm(a, b).

Define a sequence of congruence classes Y₀,Y₁,... recursively by Y_n = B(Tⁿ(x), K_n), where

M₀ = 1, K₀ = m and T_n(x) ≡ j_n (mod d), K_n = [M_n, m], M_n+1 = K_nd_jn ⁄ d.

Remark. In the Matthews-Watts case, where d_j divides d for all j, we see that K_n = m for all n.

Lemma. K_n = mK'_n and M_n = (m ⁄ d)M'_n, where K'_n and M'_n divide some power of d.

Proof. True when n = 0, as K₀ = m.
Now assume K_n = m K'_n, where K'_n divides some power of d. Then

Kn+1	= [Mn+1, m] = [Kndjn ⁄ d, m]
	= (Kndjnm ⁄ d)/gcd(Kndjn ⁄ d, m)
	= m(K'ndjn)/gcd(K'ndjn, d)

The result for M'_n then follows.

Definition. Let Θ denote the set of congruence classes of the form B(y, mK), where K divides some power of d.

Then Y_n(x) ∈ Θ for all integers n ≥ 0 and x.

Lemma. Let B_n=B(j_n, mL_n) ∈ Θ for 0 ≤ n ≤ K and let S = {x ∈ ℤ | Y₀(x) = B₀,...,Y_K(x) = B_K}.
Then if S is non-empty, we have

L_n+1 = (L_nd_jn)/gcd(L_nd_jn, d) for 0 ≤ n ≤ K-1.

S = B₀ ∩ T^-1(B₁)∩ ··· ∩ T^-K(B_K).

Theorem. As in the previous lemma, let S = {x ∈ ℤ | Y₀(x) = B₀,...,Y_K(x) = B_K} and let S be a disjoint union of p_B0,...,BK congruence classes (mod md^KL₀). Then

p_B0,...,BK = p_B0,B1 ··· p_BK-1,BK,

We need a

Lemma. Suppose M = (Ld_j)/gcd(Ld_j, d), where L and M divide some power of d.
Then B(j, mL) ∩ T^-1(B(k, mdⁿM)) is a disjoint union of p_jk(mdⁿM, mL) congruence classes (mod mdⁿ⁺¹L) and is constant for n ≥ 0.
In fact

p_jk(mdⁿM, mL) = gcd(d_j, d) if mLd_j ⁄ d divides k - T(j) and 0 otherwise.

x ≡ j (mod mL) & (m_jx-r_j) ⁄ d ≡ k (mod mdⁿM).

(m_jx-r_j) ⁄ d = T(j) + (tmLm_j) ⁄ d ≡ k (mod mdⁿM).

Now

gcd((mmjL) ⁄ d, mdnM)	= (m ⁄ d)gcd(mjL, dn+1M)
	= (m ⁄ d)gcd(djL, dn+1M)
	= (m ⁄ d)gcd(Mgcd(Ldj, d), dn+1M)
	= (mM ⁄ d)gcd(gcd(Ldj, d), dn+1)
	= (mM ⁄ d)gcd(Ldj, d, dn+1)
	= (mM ⁄ d)gcd(Ldj, d)
	= (mLdj) ⁄ d.

mdⁿ⁺¹M ⁄ d_j = mdⁿ⁺¹Ld_j/gcd(Ld_j, d).

Assumption. From now on we assume that the set Θ_T formed by the congruence classes Y_n(x), is finite.

Corollary. Let P = [p_BB'], where B, B' ∈ Θ_T. Then

card_md^K{x ∈ ℤ | Y₀ = B₀, Y_K = B₁} = p^(K)_B0B1, where P^K = [p^(K)_BB'].

From now on, we assume K₀ = 1. Then Y₀(x) = B(x, m).

The following result generalises Corollary 1 of Matthews-Watts:

Corollary. Assuming as usual, that d divides m, let

p_Kjk = card_md^K{x ∈ ℤ | x &equiv j (mod m), T^K(x) &equiv k (mod m)}.

p_Kjk = ∑_{B ⊆ B(k, m)}p^(K)_{B(j, m)B}

Y_n(x) ⊆ B(k, m) ⇔ Tⁿ(x) ≡ k (mod m).

pKjk =	cardmdK{x ∈ ℤ | Yn(x) ⊆ B(k, m), Y0(x) = B(j, m)}
=	∑B ⊆ B(k, m)cardmdK{x ∈ ℤ | Yn(x) = B, Y0(x) = B(j, m)}
=	∑B ⊆ B(k, m)p(K)B(j, m)B.

B = {x ∈ ℤ | Y₀(x) = B} = ∪_{B' ∈ &ThetaT} {x ∈ ℤ | Y₀(x) = B, Y₁(x) = B'}.

∑_{B' ∈ &ThetaT} p_BB' = d.

Even numbers are easy, they just keep being multiplied by 3 ⁄ 2 until you get an odd number, at which point the trajectory enters a cycle of period 2. x = 5 (mod 6) is the interesting case. This one will keep going until you get to 1 or 3 mod 6; unless x = -1 which is a fixed point. 1 and 3 (mod 6) both produce even numbers after one more iteration.

With m = 6, Θ_T is infinite, as Y_n(0) = B(0, 2·3ⁿ⁺¹) for n ≥ 0.

Lemma. Let C be an irreducible closed set of Q(m) and S_C = ∪_{B' ∈ C}B. Then S_C is a T-invariant set.

Proof. Suppose x ∈ S_C. Then x ∈ B, where B ∈ C, so we can take Y₀(x) = B.
Now there exists B" ∈ C such that q_BB' > 0 and hence Y₁(x) = B(T(x), mK₁) ∈ C. Hence T(x) ∈ S_C.

Conjecture. Every divergent trajectory will eventually enter some S_C and will occupy each congruence class B of C with limiting frequency ρ_B, where ρ_B is the stationary value of Q(m) corresponding to B. Then the limiting frequency of occupancy of B(i, m) will be given by

p_i = ∑_{B ∈C, B ⊆ B(i, m)}ρ_B.

∏_0≤i≤d-1|m_i ⁄ d|^p_i < 1,

∏_0≤i≤d-1|m_i ⁄ d|^p_i > 1,

Here is a link to a BCMATH program for constructing the matrix Q(m). It is based on one provided by George Leigh to the author in March 1995.

Example. (G. Leigh [3], Example 1, page 139.) Let T(x) =

3x - 1	if x ≡ 0 (mod 3)
(x - 16) ⁄ 3	if x ≡ 1 (mod 3)
(-4x - 7) ⁄ 3	if x ≡ 2 (mod 3)

The program finds 4 states and transition matrix Q(3) according to the following scheme:

B(0,1)->B(0,3)->B(8,9)
      ->B(1,3)->B(0,1)
      ->B(2,3)->B(0,1)

                B(8,9)->B(8,9)->B(2,3)

                                B(2,3)->B(2,3)->B(0,1)

Q(3)	(0,3)	(1,3)	(2,3)	(8,9)
(0,3)	0	0	0	1
(1,3)	⅓	⅓	⅓	0
(2,3)	⅓	⅓	⅓	0
(8,9)	0	0	1	0

Hence we expect most trajectories to diverge.

The trajectory starting with x = 1 appears to diverge.

There appear to be 3 cycles: -1 → -1, -8 → -8 and 421 → 135 → 404 → -541 → 719 → -961 → 1279 → 421.

Leigh does the case m = 6. We get states B(0,6), B(1,6), B(2,6), B(3,6), B(4,6), B(5,6), B(17,18), B(8,18), with ergodic chain B(1,6),B(3,6),B(5,6),B(8,18).

The stationary vector is (1/5,1/5,2/5,1/5).

Example. (G. Leigh [3], Example 2, pages 140-141.) Let T(x) =

x / 4	if x ≡ 0 (mod 8)
(x+1) / 2	if x ≡ 1 (mod 8)
20x - 40	if x ≡ 2 (mod 8)
(x - 3) / 8	if x ≡ 3 (mod 8)
20x + 48	if x ≡ 4 (mod 8)
(3x - 13) / 2	if x ≡ 5 (mod 8)
(11x - 2) / 4	if x ≡ 6 (mod 8)
(x + 1) / 8	if x ≡ 7 (mod 8)

B(0, 8), B(0, 32), B(1, 8), B(2, 8), B(3, 8), B(4, 8), B(5, 8), B(6, 8), B(7, 8).

¼	0	0	¼	0	¼	0	¼	0
1	0	0	0	0	0	0	0	0
0	0	½	0	0	0	½	0	0
0	1	0	0	0	0	0	0	0
⅛	0	⅛	⅛	⅛	⅛	⅛	⅛	⅛
0	1	0	0	0	0	0	0	0
0	0	½	0	0	0	½	0	0
¼	0	0	¼	0	¼	0	¼	0
⅛	0	⅛	⅛	⅛	⅛	⅛	⅛	⅛

The stationary values are ½, ½ and ⅜, ¼, ⅛, ⅛, ⅛.

For C₁, we have p₁ = p₂ = ½ and as

(½)^½(3/2)^½ < 1,

For C₂, we have p₀ = ⅜ + ¼ = ⅝ and p₂ = p₄ = p₆ = ⅛. Then as

(¼)^⅝20^⅛20^⅛(11/4)^⅛ > 1,

(Leigh uses another Markov chain X_n(x) and arrives at limiting frequencies 4/7, 1/7, 1/7, 1/7, which are erroneous, as one soon discovers on observing the apparently divergent trajectory starting at 46.)

In this example there appear to be 13 cycles, with starting values

0, 1, 10, 13, 61, 158, 205, 3292, 4244, -2, -11, -12, -18.

D_ν(m) = d_j0 ··· d_jν-1, where Tⁱ(x) ≡ j_i (mod d) for 0 ≤ i ≤ ν-1.

1. Venturini defines T to be of type G_ν if T has the property of the last theorem and ν is minimal. Otherwise T is of type G_∞.
2. Venturini gives two examples (6 and 7, pp. 210-211) of mappings T which belong to G_∞ but for which Θ_T has only finitely many states.

Lemma.

K'_n = D_n(m)/D'_n(m), M_n = (m ⁄ d) D_n(m)/D'_n-1(m),

where D₀(m) = 1 = D'₀(m) and D'_n+1(m) = gcd(D_n+1(m), dD'_n(m).)

D'_n(m) = gcd(D_n(m), dD_n-1(m),...,d^n-1D₁(m), dⁿ).

M'_ν+1(m) = M'_ν(T(m)).

D'ν	= gcd(Dν(m), dDν-1(m),...,dν-1D1(m), dν)
	= gcd(Dν(m), dDν-1(m),...,dν-1D1(m))
	= D1(m)gcd(Dν-1(T(m)), dDν-2T((m)),...,dν-1)
	=D1(m)D'ν-1(T(m)).

M'_ν+1(m) = D_ν+1(m)/D'_ν(m) = D₁(m)D_ν(T(m))/D₁(m)D'_ν-1(T(m)) = D_ν(T(m))/D'_ν-1(T(m)) = M'_ν(T(m)).

Hence &Theta_ν is the collection of all B(Tⁿ(x), (m ⁄ d)M'_n(x)), 0 ≤ x < md^ν, n ≤ ν, a finite set of congruence classes the M'_n(x) divide d^ν.

Then as K'_n(x) = [M'_n(x), d], it follows that K'_n(x) divides d^ν for all n > 0 and x ∈ ℤ.

Example. (G. Venturini [4] Example 1, 205-206)

T(x) = :

(2500x ⁄ 6) + 1	if x ≡ 0 (mod 6)
(21x - 9) ⁄ 6	if x ≡ 1 (mod 6)
(x + 16) ⁄ 6	if x ≡ 2 (mod 6)
(21x - 51) ⁄ 6	if x ≡ 3 (mod 6)
(21x - 72) ⁄ 6	if x ≡ 4 (mod 6)
(x + 13) ⁄ 6	if x ≡ 5 (mod 6).

We find 9 states according to the following scheme:

B(0,1)->B(0,6)->B(1,4)
      ->B(1,6)->B(2,3)
      ->B(2,6)->B(0,1)
      ->B(3,6)->B(2,3)
      ->B(4,6)->B(2,3)
      ->B(5,6)->B(0,1)

                B(1,4)->B(1,12)->B(2,6)
                      ->B(5,12)->B(1,2)
                      ->B(9,12)->B(5,6)

                B(2,3)->B(2,6) ->B(0,1)
                      ->B(5,6) ->B(0,1)

                                 B(2,6)->B(2,6)->B(0,1)
                                 B(1,2)->B(1,6)->B(2,3)
                                       ->B(3,6)->B(2,3)
                                       ->B(5,6)->B(0,1)

                                 B(5,6)->B(5,6)->B(0,1)

Q(6)	(0,6)	(1,6)	(2,6)	(3,6)	(4,6)	(5,6)	(1,12)	(5,12)	(9,12)
(0,6)	0	0	0	0	0	0	⅓	⅓	⅓
(1,6)	0	0	½	0	0	½	0	0	0
(2,6)	⅙	⅙	⅙	⅙	⅙	⅙	0	0	0
(3,6)	0	0	½	0	0	½	0	0	0
(4,6)	0	0	½	0	0	½	0	0	0
(5,6)	⅙	⅙	⅙	⅙	⅙	⅙	0	0	0
(1,12)	0	0	1	0	0	0	0	0	0
(5,12)	0	⅓	0	⅓	0	⅓	0	0	0
(9,12)	0	0	0	0	0	1	0	0	0

The stationary vector of Q(6) is (1 ⁄ 202)(18, 20, 53, 20, 18, 55, 6, 6, 6).
Noting that B(1,12) ⊆ B(1,6), B(5,12) ⊆ B(5,6), B(9,12) ⊆ B(3,6), we calculate expected frequencies

p₀=9/101, p₁=13/101, p₂=53/202, p₃=13/101, p₄=9/101, p₅=61/202.

∏_0≤i≤5(m_i ⁄ d)^p_i = (2500 ⁄ 6)^9/101(21 ⁄ 6)^13/101(1 ⁄ 6)^53/202(21 ⁄ 6)^13/101(21 ⁄ 6)^9/101(1 ⁄ 6)^61/202 = (5³⁶7³⁵ ⁄ 2⁸³3⁶⁶)^1/101 < 1.

In fact there appear to be just two cycles:

(a) 2,3,2 and
(b) 6, 2501, 419, 72, 30001, 105002, 17503, 61259, 10212, 4255001, 709169, 118197, 413681, 68949, 241313, 40221, 140765, 23463, 82112, 13688, 2284, 7982, 1333, 4664, 780, 325001, 54169, 189590, 31601, 5269, 18440, 3076, 10754, 1795, 6281, 1049, 177, 611, 104, 20, 6.

Interested viewers can experiment with a BCMATH program.

Example. (G. Venturini [4] Example 7, 210-211)

T(x) = :

x ⁄ 3	if x ≡ 0 (mod 6)
(2x - 2) ⁄ 3	if x ≡ 1 (mod 6)
(5x - 4) ⁄ 3	if x ≡ 2 (mod 6)
4x ⁄ 3	if x ≡ 3 (mod 6)
(5x - 8) ⁄ 3	if x ≡ 4 (mod 6)
(4x - 2) ⁄ 3	if x ≡ 5 (mod 6).

We find 21 states according to the following scheme:

B(0,1)->B(0,6)->B(0,2)
      ->B(1,6)->B(0,4)
      ->B(2,6)->B(0,2)
      ->B(3,6)->B(4,8)
      ->B(4,6)->B(0,2)
      ->B(5,6)->B(6,8)

                B(0,2)->B(0,6)  ->B(0,2)
                      ->B(2,6)  ->B(0,2)
                      ->B(4,6)  ->B(0,2)

                B(0,4)->B(0,12) ->B(0,4)
                      ->B(4,12) ->B(0,4)
                      ->B(8,12) ->B(0,4)

                B(4,8)->B(4,24) ->B(4,8)
                      ->B(12,24)->B(4,8)
                      ->B(20,24)->B(0,8)

                B(6,8)->B(6,24) ->B(2,8)
                      ->B(14,24)->B(6,8)
                      ->B(22,24)->B(2,8)


                                  B(2,8)->B(2,24) ->B(2,8)
                                        ->B(10,24)->B(6,8)
                                        ->B(18,24)->B(6,8)

row/column permutation:
(1, 3, 5, 7, 8, 9, 10, 11, 12, 16, 17, 18, 13, 19, 20, 14, 15, 21, 2, 4, 6)
canonical form of Q(6)=

⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	⅓	⅓	0	0	⅓	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	⅓	⅓	0	0	⅓	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	⅓	0	0	⅓	⅓	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	⅓	0	0	⅓	⅓	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	⅓	⅓	0	0	⅓	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	⅓	0	0	⅓	⅓	0	0	0	0
0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	⅓	⅓	⅓	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	⅓	0	0	⅓	⅓	0	0	0	0

Let S_i be the union of the congruence classes that make up chain[i].
This example is curious, as S₃=S₂=B(0,4) ⊆ S₁=B(0,2) and S₄=B(2,4) ⊆ S₁.

Q(6) is a doubly-stochastic matrix.
So the stationary vectors of the relevant 3×3 and 6×6 submatrices are (⅓,⅓,⅓) and (⅙,⅙,⅙,⅙,⅙) respectively.

The corresponding weighted product for chain[1] and chain[2] is

∏_0≤i≤d-1|m_i ⁄ d|^p_i = (2 ⁄ 6)^⅓(10 ⁄ 6)^⅓(10 ⁄ 6)^⅓ = 25^⅓ ⁄ 3 < 1.

We believe that there are 9 cycles:

cycle 1: 0, 0
cycle 2: -6, -2, -6
cycle 3: 2, 2
cycle 4: -16, -28, -48, -16
cycle 5: 4, 4
cycle 6: -78, -26, -46, -78
cycle 7: -22, -38, -66, -22
cycle 8: -32, -56, -96, -32
cycle 9: 2454, 818, 1362, 454, 754, 1254, 418, 694, 1154, 1922, 3202, 5334, 1778, 2962, 4934, 8222, 13702, 22834, 38054, 63422, 105702, 35234, 58722, 19574, 32622, 10874, 18122, 30202, 50334, 16778, 27962, 46602, 15534, 5178, 1726, 2874, 958, 1594, 2654, 4422, 1474, 2454.
(length of cycle 9 is 41)

Interested viewers can experiment with a BCMATH program.

References

1. K.R. Matthews and A.M. Watts, A generalization of Hasse's generalization of the Syracuse algorithm, Acta Arith. 43 (1984) 167-175.
2. - -, A Markov approach to the generalized Syracuse algorithm, ibid. 45 (1985) 29-42.
3. G.M. Leigh, A Markov process underlying the generalized Syracuse algorithm, ibid. 46 (1986) 125-143.
4. G. Venturini, Iterates of number-theoretic functions with periodic rational coefficients (generalization of the 3x+1 problem), Stud. Appl. Math. 86 (1992), no.3, 185-218.

Last modified 20th June 2008