- Introduction
- The generalized 3x+1 function
- The motivating example
- Definitions
- The crucial lemma
- The main theorem
- The Markov matrix Q
_{T}(m) - An example from paper [3]
- A finiteness theorem of G. Venturini
- A BCMATH program for constructing Q
_{T}(m) and finding its irreducible closed sets - Some examples of G. Venturini: Example 1, Example 2, Example 3, Example 4,
- Example of Chris Smyth.
- BCMATH cycling-finding program
- References

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

George came up with his approach 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. The reader may prefer Leigh's proof.

The only person who seems to have followed up on George's paper was 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'}.

(I did not find his papers easy reading.)

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.

The transition matrix for the X_{n}(x) chain is smaller in general than that of the Y_{n}(x) chain. However I prefer the latter, as it generalises the Matthews-Watts Q_{T}(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_{T}(m).

Let d ≥ 2 and m

T(x) = (m_{i}x - r_{i}) ⁄ d if x ≡ i (mod d).

Paper [1] assumes (a) gcd(m_{i}, d) = 1 for 0 ≤ i ≤ d-1, while paper [2] assumes either (a) holds or (b) gcd(m_{i}, d^{2}) = gcd(m_{i}, d) for 0 ≤ i ≤ d-1 and d divides m.

12x - 1 | if x ≡ 0 (mod 4) | |

T(x) = | 20x | if x ≡ 1 (mod 4) |

(3x - 6) ⁄ 4 | if x ≡ 2 (mod 4) | |

(x - 3) ⁄ 4 | if x ≡ 3 (mod 4). |

Also gcd(m

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

- T(x) ≡ -1 (mod 16) (state 4)
- T
^{2}(x) ≡ -1 (mod 4) (state 3)

- T(x) ≡ 4 (mod 16) (state 5)
- T
^{2}(x) ≡ -17 (mod 64) (state 6) - T
^{3}(x) ≡ -5 (mod 16) (state 7) - T
^{4}(x) ≡ -2 (mod 4) (state 2).

starting in state i, for 0 ≤ i, j ≤ 7:

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 |

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).

A
We will eventually see how A allows us to calculate card_{4n+1}{B(i, 4) ∩ 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.

Also let d
As George Leigh pointed out in his paper, the condition gcd(m_{i},d^{2})=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_{0}(x),Y_{1}(x),... recursively by Y_{n}(x) = B(T^{n}(x), K_{n}), where

M_{0} = 1, K_{0} = m and T_{n}(x) ≡ j_{n} (mod d),
K_{n} = [M_{n}, m], M_{n+1} = K_{n}d_{jn} ⁄ d.

(Leigh also defines congruence classes X_{0}(x),X_{1}(x),... recursively by X_{n}(x) = B(T^{n}(x), M_{n}).)

**Remark**. In the Matthews-Watts case, where d_{j} divides d for all j, we see that K_{n} = m for all n.

**Lemma**. For n ≥ 0, K_{n} = mk_{n} and M_{n+1} = (m ⁄ d)M'_{n+1}, where k_{n} and M'_{n+1} divide some power of d.

**Proof**. True when n = 0, as K_{0} = m.

Now assume K_{n} = m k_{n}, where k_{n} divides some power of d. Then

K_{n+1} | = [M_{n+1}, m] = [K_{n}d_{jn} ⁄ d, m] |

= (K_{n}d_{jn}m ⁄ d)/gcd(K_{n}d_{jn} ⁄ d, m) | |

= m(k_{n}d_{jn})/gcd(k_{n}d_{jn}, 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_{0}(x) = B_{0},...,Y_{K}(x) = B_{K}}.

Then if S is non-empty, we have

L_{n+1} = (L_{n}d_{jn})/gcd(L_{n}d_{jn}, d) for 0 ≤ n ≤ K-1.

S = B_{0} ∩ T^{-1}(B_{1})∩ ··· ∩ T^{-K}(B_{K}).

**Theorem**. As in the previous lemma, let
S = {x ∈ ℤ | Y_{0}(x) = B_{0},...,Y_{K}(x) = B_{K}}. Then S is a disjoint union of
p_{B0,...,BK} congruence classes (mod md^{K}L_{0}) where

p_{B0,...,BK} =
p_{B0,B1} ···
p_{BK-1,BK},

Leigh's proof depends on the following result (equation (42), p. 132): There exists U, w, gcd(w,d)=1, such that for all integers a,

T^{n}(x+aU)=T^{n}(x)+awM_n.

**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^{n}M)) is a disjoint union of p_{jk}(md^{n}M, mL) congruence classes (mod md^{n+1}L), where

p_{jk}(md^{n}M, mL) =
gcd(Ld_{j}, d) if mLd_{j} ⁄ d divides k - T(j) and 0 otherwise.

x ≡ j (mod mL) & (m_{j}x-r_{j}) ⁄ d ≡ k (mod md^{n}M).

(m_{j}x-r_{j}) ⁄ d = T(j) + (tmLm_{j}) ⁄ d ≡ k (mod md^{n}M).

Now

gcd((mm_{j}L) ⁄ d, md^{n}M) | = (m ⁄ d)gcd(m_{j}L, d^{n+1}M) |

= (m ⁄ d)gcd(d_{j}L, d^{n+1}M) | |

= (m ⁄ d)gcd(Mgcd(Ld_{j}, d), d^{n+1}M) | |

= (mM ⁄ d)gcd(gcd(Ld_{j}, d), d^{n+1}) | |

= (mM ⁄ d)gcd(Ld_{j}, d, d^{n+1}) | |

= (mM ⁄ d)gcd(Ld_{j}, d) | |

= (mLd_{j}) ⁄ d. |

Hence the solution for x is unique (mod (d

md^{n+1}M ⁄ d_{j} = md^{n+1}Ld_{j}/gcd(Ld_{j}, d).

Proof of Theorem. (Added 9th April 2010). We use induction on K. It's clearly true when K=1.

Let
S = {x ∈ ℤ | Y_{0}(x) = B_{0},...,Y_{K+1}(x) = B_{K+1}}.

If S is non-empty, it can be written as
S = B_{0} ∩ T^{-1}(B_{1}∩⋯∩ T^{-K}(B_{K+1})).

By the induction hypothesis, B_{1}(x) ∩⋯∩ T^{-K}(B_{K+1}) is a disjoint union of p_{B1B2}⋯p_{BKBK+1} congruence classes mod md^{K}L_{1} of the form B(u, md^{K}L_{1}) say.

Then u ≡ j_{1} (mod mL_{1}) and j_{1} ≡ T(j_{0}) (mod mL_{1}).
Hence u ≡ T(j_{0}) (mod mL_{1}).
Hence u ≡ T(j_{0}) (mod mL_{0}d_{j0}/gcd(L_{0}d_{j0}, d)) and hence (mod mL_{0}d_{j0}/d).

Then by the Lemma, B_{0} ∩ T^{-1}(B(u, md^{K}L_{1})) is a disjoint union of gcd(L_{0}d_{j0}, d) = p_{BoB1} congruence classes (mod md^{K+1}L_{0}). This gives a total of p_{B0B1}⋯p_{BKBK+1} congruence classes (mod md^{K+1}L_{0}) and the induction goes through.

**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_{0}(x) = B_{0}, Y_{K}(x) = B_{1}} = p^{(K)}_{B0B1}, where P^{K} = [p^{(K)}_{BB'}].

The following result generalises Corollary 1 of Matthews-Watts:

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

p_{Kjk} = card_{mdK}{x ∈ ℤ | x ≡ j (mod m), T^{K}(x) ≡ k (mod m)}.

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

Y_{K}(x) ⊆ B(k, m) ⇔ T^{K}(x) ≡ k (mod m).

p_{Kjk} = | card_{mdK}{x ∈ ℤ | Y_{K}(x) ⊆ B(k, m), Y_{0}(x) = B(j, m)} |

= | ∑_{B ⊆ B(k, m)}card_{mdK}{x ∈ ℤ | Y_{K}(x) = B, Y_{0}(x) = B(j, m)} |

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

B = {x ∈ ℤ | Y_{0}(x) = B} = ∪_{B' ∈ ΘT} {x ∈ ℤ | Y_{0}(x) = B, Y_{1}(x) = B'}.

However B is also a disjoint union of d congruence classes (mod mLd). Hence

∑_{B' ∈ ΘT} p_{BB'} = d.

Now using an earlier-mentioned result of Leigh, the congruence classes B'=B(T(x)+tM_{n+1}, K_{n+1}) belong to Ω and satisfy q_{BB'}>0 and hence belong to C. The desired result then follows on taking t=0.

**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_{T}(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|^{pi} < 1,

However if

∏_{0≤i≤d-1}|m_{i} ⁄ d|^{pi} > 1,

Here is a link to a BCMATH program for constructing the matrix Q_{T}(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

3x - 1 | if x ≡ 0 (mod 3) | |

T(x) = | (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_{T}(3) according to the following scheme:

B(0,3)→B(8,9)→B(8,9) B(1,3)→B(0,1)→B(0,3) →B(1,3) →B(2,3) B(2,3)→B(0,1)→B(0,3) →B(1,3) →B(2,3) B(8,9)→B(2,3)→B(2,3)States:

1:B(0,3), 2:B(1,3), 3:B(2,3), 4:B(8,9),

Q_{T}(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 |

Now B(8,9) ⊆ B(2,3). Consequently p

Hence the weighted product ∏

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

x / 4 | if x ≡ 0 (mod 8) | |

(x+1) / 2 | if x ≡ 1 (mod 8) | |

20x - 40 | if x ≡ 2 (mod 8) | |

T(x) = | (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) |

X

We find there are 9 classes in Θ_{T}:

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).

The Markov matrix Q

¼ | 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_{1}, we have p_{1} = p_{2} = ½ and as

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

For C_{2}, we have p_{0} = ⅜ + ¼ = ⅝ and
p_{2} = p_{4} = p_{6} = ⅛. 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_{ν}(x)= d_{j0} ··· d_{jν-1}, where T^{i}(x) ≡ j_{i} (mod d) for 0 ≤ i ≤ ν-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_{∞}. - 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}(x) = D_{n}(x)/D'_{n}(x), M'_{n}(x) = (m ⁄ d) D_{n}(x)/D'_{n-1}(x),

where D_{0}(x) = 1 = D'_{0}(x) and D'_{n+1}(x) = gcd(D_{n+1}(x), dD'_{n}(x).)

D'_{n}(x) = gcd(D_{n}(x), dD_{n-1}(x),...,d^{n-1}D_{1}(x), d^{n}).

M'_{ν+1}(x) = M'_{ν}(T(x)).

D'_{ν}(x) | = gcd(D_{ν}(x), dD_{ν-1}(x),...,d^{ν-1}D_{1}(x), d^{ν}) |

= gcd(D_{ν}(x), dD_{ν-1}(x),...,d^{ν-1}D_{1}(x)) | |

= D_{1}(x)gcd(D_{ν-1}(T(x)), dD_{ν-2}T((x)),...,d^{ν-1}) | |

=D_{1}(x)D'_{ν-1}(T(x)). |

M'_{ν+1}(x) = D_{ν+1}(x)/D'_{ν}(x) =
D_{1}(x)D_{ν}(T(x))/D_{1}(x)D'_{ν-1}(T(x)) =
D_{ν}(T(x))/D'_{ν-1}(T(x)) = M'_{ν}(T(x)).

**Example 1**. (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). |

m

X

Also

d

We find 9 states according to the following scheme:

B(0,6)→B(1,4)→B(1,12) →B(5,12) →B(9,12) B(1,6)→B(2,3)→B(2,6) →B(5,6) B(2,6)→B(0,1)→B(0,6) →B(1,6) →B(2,6) →B(3,6) →B(4,6) →B(5,6) B(3,6)→B(2,3)→B(2,6) →B(5,6) B(4,6)→B(2,3)→B(2,6) →B(5,6) B(5,6)→B(0,1)→B(0,6) →B(1,6) →B(2,6) →B(3,6) →B(4,6) →B(5,6) B(1,12)→B(2,6)→B(2,6) B(5,12)→B(1,2)→B(1,6) →B(3,6) →B(5,6) B(9,12)→B(5,6)→B(5,6)

Q_{T}(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 |

States 1, 7, 3, 2, 4, 5, 6, 8, 9 constitute an ergodic chain.

The stationary vector of Q_{T}(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_{0}=9/101,
p_{1}=13/101,
p_{2}=53/202,
p_{3}=13/101,
p_{4}=9/101,
p_{5}=61/202.

∏_{0≤i≤5}(m_{i} ⁄ d)^{pi} = (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^{36}7^{35} ⁄ 2^{83}3^{66})^{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 2**. (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). |

m

X

d

We find 21 states according to the following scheme:

B(0,6)→B(0,2)→B(0,6) →B(2,6) →B(4,6) B(1,6)→B(0,4)→B(0,12) →B(4,12) →B(8,12) B(2,6)→B(0,2)→B(0,6) →B(2,6) →B(4,6) B(3,6)→B(4,8)→B(4,24) →B(12,24) →B(20,24) B(4,6)→B(0,2)→B(0,6) →B(2,6) →B(4,6) B(5,6)→B(6,8)→B(6,24) →B(14,24) →B(22,24) B(0,12)→B(0,4)→B(0,12) →B(4,12) →B(8,12) B(4,12)→B(0,4)→B(0,12) →B(4,12) →B(8,12) B(8,12)→B(0,4)→B(0,12) →B(4,12) →B(8,12) B(4,24)→B(4,8)→B(4,24) →B(12,24) →B(20,24) B(12,24)→B(4,8)→B(4,24) →B(12,24) →B(20,24) B(20,24)→B(0,8)→B(0,24) →B(8,24) →B(16,24) B(6,24)→B(2,8)→B(2,24) →B(10,24) →B(18,24) B(14,24)→B(6,8)→B(6,24) →B(14,24) →B(22,24) B(22,24)→B(2,8)→B(2,24) →B(10,24) →B(18,24) B(0,24)→B(0,8)→B(0,24) →B(8,24) →B(16,24) B(8,24)→B(4,8)→B(4,24) →B(12,24) →B(20,24) B(16,24)→B(0,8)→B(0,24) →B(8,24) →B(16,24) B(2,24)→B(2,8)→B(2,24) →B(10,24) →B(18,24) B(10,24)→B(6,8)→B(6,24) →B(14,24) →B(22,24) B(18,24)→B(6,8)→B(6,24) →B(14,24) →B(22,24)States:

1:(0,6), 2:(1,6), 3:(2,6), 4:(3,6), 5:(4,6), 6:(5,6), 7:(0,12), 8:(4,12), 9:(8,12), 10:(4,24), 11:(12,24), 12:(20,24), 13:(6,24), 14:(14,24), 15:(22,24), 16:(0,24), 17:(8,24), 18:(16,24), 19:(2,24), 20:(10,24), 21:(18,24),

Q_{T}(6) | (0,6) | (1,6) | (2,6) | (3,6) | (4,6) | (5,6) | (0,12) | (4,12) | (8,12) | (4,24) | (12,24) | (20,24) | (6,24) | (14,24) | (22,24) | (0,24) | (8,24) | (16,24) | (2,24) | (10,24) | (18,24) |

(0,6) | ⅓ | 0 | ⅓ | 0 | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(1,6) | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(2,6) | ⅓ | 0 | ⅓ | 0 | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(3,6) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(4,6) | ⅓ | 0 | ⅓ | 0 | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(5,6) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 |

(0,12) | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(4,12) | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(8,12) | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(4,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(12,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(20,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 |

(6,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ |

(14,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 |

(22,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ |

(0,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 |

(8,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

(16,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 |

(2,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ |

(10,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 |

(18,24) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ⅓ | ⅓ | ⅓ | 0 | 0 | 0 | 0 | 0 | 0 |

1, 3, 5, constitute ergodic chain[1] ie. B(0,6), B(2,6), B(4,6);

7, 8, 9, constitute ergodic chain[2] ie. B(0,12), B(4,12), B(8,12);

10, 11, 12, 16, 17, 18, constitute ergodic chain[3] ie. B(4,24), B(12,24), B(20,24), B(0,24), B(8,24), B(16,24);

13, 19, 20, 14, 15, 21, constitute ergodic chain[4] ie. B(6,24), B(2,24), B(10,24), B(14,24), B(22,24), B(18,24);

2, 4, 6 are the transient states ie. B(1,6), B(3,6), B(5,6).

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_{T}(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_{3}=S_{2}=B(0,4) ⊆ S_{1}=B(0,2) and S_{4}=B(2,4) ⊆ S_{1}. Also S_{1}=S_{2}∪S_{4}.

Q_{T}(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|^{pi} = (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.

Venturini gave two examples of mappings where the chain {Y_{n}} is infinite. In his Example 8, p. 211, heuristic reasoning implied that all trajectories eventually cycle. There appear to be 8 cycles. In his Example, section 7.4, p. 212, he could prove that all trajectories eventually cycle into specified cycles.

**Example 3**. (G. Venturini [4] Example 8, p. 211-212)

T(x) = :

x ⁄ 3 | if x ≡ 0 (mod 6) |

(x - 1) ⁄ 3 | if x ≡ 1 (mod 6) |

(5x + 5) ⁄ 3 | if x ≡ 2 (mod 6) |

(3x + 5) ⁄ 2 | if x ≡ 3 (mod 6) |

(3x + 2) ⁄ 2 | if x ≡ 4 (mod 6) |

(3x - 1) ⁄ 2 | if x ≡ 5 (mod 6). |

m

X

d

Y_{0}(3)=B(3,6),
Y_{1}(3)=B(16,18),
Y_{2}(3)=B(52,54),
Y_{3}(3)=B(160,162), etc.

There appear to be 8 cycles: 0 (1), -2 (1), 2, (3), 8, (3), -10 (4), -82 (7), -52 (7), 6038 (52).

**Example 4**. (G. Venturini [4] Example section 7.4, p. 212) This is a 2p-branched map, where p > 1 is odd. As pointed out by G. Venturini, the chain has infinitely many states and the behaviour of the iterates can be established directly.

T(2pq + r)=4q + r if r < p,

T(2pq + r)=p^{2}q + r if r ≥ p.

Venturini points out that if x=2

cycle 1: -1, -p^{2} + p - 1, -p + 1, -p^{2} + p + 1, -2p + 3, -1.

cycle 2: -2, -p^{2} + 2p - 2, -p, -p^{2} + p, -2p + 2, -2.

T(2pq + r)=p^{2}q + r if r < p

T(2pq + r)=4q + r if r ≥ p,

Venturini remarks that the above two cycles are replaced by similar ones starting with 2p and 2p + 1, with only one cycle when p = 3, starting with 7.

cycle 1: 2p, p^{2}, 3p - 2, p^{2} + p - 2, 4p - 4, 2p.

cycle 2: 2p + 1, p^{2}+1, 3p - 1, p^{2} + p - 1, 4p - 3, 2p+1.

T(x)=

int(7x/6) | if x ≡ 0 (mod 6) |

int(21x/6) | if x ≡ 1 (mod 6) |

3x | if x ≡ 2 (mod 6) |

int(4x/6) | if x ≡ 3 (mod 6) |

2x | if x ≡ 4 (mod 6) |

int(27x/6) | if x ≡ 5 (mod 6). |

C_{1}={B(4,6), B(8,12), B(24,36)

C_{2}={B(22,54), etc}

C_{3}={B(10,12), B(20,24), B(60,72).

**Example 6**. T(x) = 3x ⁄ 2 if x is even, int(2x ⁄ 3) if x is odd, was suggested by
Chris Smyth when the author visited Edinburgh in 1993. Here all trajectories eventually enter a cycle, namely cycles 6n → 9n → 6n (n nonzero) and 6n+3 → 4n+2 → 6n+3, or the fixed points 0 and -1. This was pointed out by George Leigh in an email of 14th December 1993.

The chain {Y_{n}} is infinite, as Y_{n}(0) = B(0, 2·3^{n+1}) for n ≥ 0.

- K.R. Matthews and A.M. Watts,
*A generalization of Hasse's generalization of the Syracuse algorithm*, Acta Arith.**43**(1984) 167-175. - - -,
*A Markov approach to the generalized Syracuse algorithm*, ibid.**45**(1985) 29-42. - G.M. Leigh,
*A Markov process underlying the generalized Syracuse algorithm*, ibid.**46**(1986) 125-143. - 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 7th April 2016*