- Introduction
- The generalized 3x+1 function
- Definitions
- The crucial lemma
- The main theorem
- The Markov matrix Q
_{T}(m) - Example 1 from paper [3] of George Leigh
- Example 2 from paper [3] of George Leigh, with corrections
- BCMATH program for constructing Q
_{T}(m) and finding its irreducible closed sets - Some examples of G. Venturini:
- 6-branched example
- Another 6-branched example (infinitely many cycles)
- Example of Chris Smyth.
- 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.

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. (Leigh was interested in the behaviour of trajectories mod (m) for arbitrary m ≥ 2, and took [m, d] = lcm(m, d).

Define a sequence of congruence classes \(Y_0(x), Y_1(x),\ldots\) by \[ \begin{align*} Y_0(x)&=B(x,m);\\ Y_{n+1}(x)&=B(T^{n+1}(x),mk_{n+1}), n \ge 0, \end{align*} \] where \(k_0=1\) and \(k_{n+1}=\frac{k_nd_j}{\gcd(k_nd_j, d)}\), and where \(j\) is determined by the congruence \(T^n(x)\equiv j\pmod{d}, 0\leq j \leq d-1\).

(Leigh also defined congruence classes \(X_0(x), X_1(x),\ldots\) by

\(X_0(x)=B(0,1)\);

\(X_{n+1}(x)=B(T^{n+1}(x),\frac{mk_nd_j}{d})\) if \(n \ge 0\),

where \(j\) is determined by the congruence \(T^n(x)\equiv j\pmod{d}, 0\leq j \leq d-1\).)

**Remark**. In the Matthews-Watts case, where d_{j} divides d for all j, we see that Y_{n}(x) = B(T^{n}(x), m) for all n.

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

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

\[
\begin{align*}
p_{Kjk}&=\text{card}_{md^K}\{x\in \mathbb{Z} \mid Y_K(x)\subseteq B(k,m), Y_0(x)=B_(j,m)\}\\
&=\sum_{B\subseteq B(k,m)}\text{card}_{md^K}\{x\in \mathbb{Z} \mid Y_K(x)=B, Y_0(x)=B_(j,m)\}\\
&=\sum_{B\subseteq B(k,m)}p^{(K)}_{B(j,m)B}.
\end{align*}
\]
**Lemma**. Q_{T}(m) = [p_{BB'} ⁄ d] is a Markov matrix.

**Proof**. Let B ∈ Θ_{T}, B = B(j, mL). Then

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 \[ \sum_{B'\in\Theta_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=\sum_{B\in C, B\subseteq B(i,m)}\rho_B.
\]
**Conjecture**. Let C be an irreducible closed set of Q_{T}(d). Then if
\[
\prod_{\begin{array}{c}0\le i\le d-1\\C\cap B(i,d)\neq\emptyset\end{array}}\biggm|\frac{m_i}{d}\biggm|^{p_i}<1,
\]
all trajectories starting in S_{C} will eventually cycle.

However if
\[
\prod_{\begin{array}{c}0\le i\le d-1\\C\cap B(i,d)\neq\emptyset\end{array}}\biggm|\frac{m_i}{d}\biggm|^{p_i}>1,
\]
almost all trajectories starting in S_{C} will diverge.

If the weighted product equals \(1\), G. Venturini showed that for type (b) mappings and a wider class of mappings, all trajectories starting in \(S_C\) will be cycles or arithmetic progressions.

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
\[
T(x)=\left\{\begin{array}{ccc}
3x-1 &\mbox{if $x ≡ 0 \pmod{3}$}\\
\frac{x-16}{3} &\mbox{if $x ≡ 1 \pmod{3}$}\\
\frac{-4x-7}{3} &\mbox{if $x ≡ 2 \pmod{3}$}.
\end{array}
\right.
\]
Here
m_{0} = 9,
m_{1} = 1,
m_{2} = -4;
X_{0} = -1,
X_{1} = -5,
X_{2} = -2;
d_{0} = 9,
d_{1} = 1,
d_{2} = 1.

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)=\begin{array}{c|cccc} & \small(0,3) & \small(1,3) & \small(2,3) & \small(8,9)\\\hline \small(0,3) & 0 & 0 & 0 & 1\\ \small(1,3) & 1/3 & 1/3 & 1/3 & 0\\ \small(2,3) & 1/3 & 1/3 & 1/3 & 0\\ \small(8,9) & 0 & 0 & 1 & 0 \end{array} \] (Q

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

Hence the weighted product = (9/3)

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 135 → 404 → -541 → 719 → -961 → 1279 → 421 → 135.

**Example**. (G. Leigh [3], Example 2, pages 140-141.) Let
\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{4} &\mbox{if $x ≡ 0 \pmod{8}$}\\
\frac{x+1}{2} &\mbox{if $x ≡ 1 \pmod{8}$}\\
20x-40 &\mbox{if $x ≡ 2 \pmod{8}$}\\
\frac{x-3}{8} &\mbox{if $x ≡ 3 \pmod{8}$}\\
20x+48 &\mbox{if $x ≡ 4 \pmod{8}$}\\
\frac{3x-13}{2} &\mbox{if $x ≡ 5 \pmod{8}$}\\
\frac{11x-2}{4} &\mbox{if $x ≡ 6 \pmod{8}$}\\
\frac{x+1}{8} &\mbox{if $x ≡ 7 \pmod{8}$}.
\end{array}
\right.
\]
Here
m_{0}=2, m_{1}=4, m_{2}=160, m_{3}=1, m_{4}=160, m_{5}=12, m_{6}=22, m_{7}=1;

X_{0}=0, X_{1}=1, X_{2}=-40, X_{3}=0, X_{4}=48, X_{5}=-6, X_{6}=0, X_{7}=1.

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

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

We get a transition matrix QB(0,8)→B(0,2)→B(0,8), B(2,8), B(4,8), B(6,8)

B(1,8)→B(1,4)→B(1,8), B(5,8)

B(2,8)→B(0,32)→B(0,32)

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

B(4,8)→B(0,32)→B(0,32)

B(5,8)→B(1,4)→B(1,8), B(5,8)

B(6,8)→B(0,2)→B(0,8), B(2,8), B(4,8), B(6,8)

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

B(0,32)→B(0,8)→B(0,8)

\[
Q_T(8)=
\left[
\begin{array}{ccccccccc}
\frac{1}{4} & 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 &\frac{1}{4} & 0 & 0\\
0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
\frac{1}{8} &\frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0\\
\frac{1}{4} & 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 &\frac{1}{4} & 0 & 0\\
\frac{1}{8} &\frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}
\right]
\]
There are two irreducible closed sets: C_{1} = {B(1, 8), B(5, 8)} and C_{2} = {B(0, 8), B(0, 32), B(2, 8), B(4, 8), B(6, 8)}. The classes B(3,8) and B(7,8) are transient.

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

For C_{1}, we have p_{1} = p_{5} = ½ and as
\[
\left(\frac{m_1}{8}\right)^{p_1}\left(\frac{m_5}{8}\right)^{p_5}=
\left(\frac{4}{8}\right)^{1/2}\left(\frac{12}{8}\right)^{1/2}<1,
\]
we expect all trajectories starting in S_{C1} = B(1, 8) ∪ B(5, 8) = B(1, 4) to cycle.

For C_{2}, we have p_{0} = ⅜ + ¼ = ⅝ and
p_{2} = p_{4} = p_{6} = ⅛. Then as
\[
\left(\frac{m_0}{8}\right)^{p_0}\left(\frac{m_2}{8}\right)^{p_2}\left(\frac{m_4}{8}\right)^{p_4}\left(\frac{m_6}{8}\right)^{p_6}=
\left(\frac{2}{8}\right)^{5/8}\left(\frac{160}{8}\right)^{1/8}\left(\frac{160}{8}\right)^{1/8}\left(\frac{22}{8}\right)^{1/8}>1,
\]
we expect most trajectories starting in S_{C2} = B(0, 2) to diverge.

(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. See corrections)

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.

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

\[
T(x)=\left\{\begin{array}{ccc}
\frac{2500x}{6}+1 &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{21x-9}{6} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{x+16}{6} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{21x-51}{6} &\mbox{if $x ≡ 3 \pmod{6}$}\\
\frac{21x-72}{6} &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{x+13}{6} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
Here

m_{0} = 2500,
m_{1} = 21,
m_{2} = 1,
m_{3} = 21,
m_{4} = 21,
m_{5} = 1;

X_{0} = 1,
X_{1} = -1,
X_{2} = 3,
X_{3} = -8,
X_{4} = -12,
X_{5} = 3.

Also

d_{0} = 4,
d_{1} = 3,
d_{2} = 1,
d_{3} = 3,
d_{4} = 3,
d_{5} = 1.

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.

There appear to be just two cycles:

(a) 2,3 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.

Experiment with a BCMATH program.

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

\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{3} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{2x-2}{3} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{5x-4}{3} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{4x}{3} &\mbox{if $x ≡ 3 \pmod{6}$}\\
\frac{5x-8}{3} &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{4x-2}{3} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
Here

m_{0} = 2,
m_{1} = 4,
m_{2} = 10,
m_{3} = 8,
m_{4} = 10,
m_{5} = 8;

X_{0} = 0,
X_{1} = 0,
X_{2} = -1,
X_{3} = 0,
X_{4} = -2,
X_{5} = 0.

d_{0} = 2,
d_{1} = 4,
d_{2} = 2,
d_{3} = 8,
d_{4} = 2,
d_{5} = 8.

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

The stationary vectors of the relevant 3×3 and 6×6 submatrices are (⅓,⅓,⅓) and (⅙,⅙,⅙,⅙,⅙) respectively.

The corresponding weighted product for chain[1] is \[ \left(\frac{2}{6}\right)^{1/3}\left(\frac{10}{6}\right)^{1/3}\left(\frac{10}{6}\right)^{1/3}= \frac{25^{1/3}}{3}<1. \] Hence we expect all trajectories starting in the even integers will eventually cycle. Note that T(B(1,2)) ⊆ B(0,2).

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 8**. (G. Venturini [4], p. 211-212)

\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{3} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{x-1}{3} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{5x+5}{3} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{3x+5}{2} &\mbox{if $x ≡ 3 \pmod{6}$}\\
\frac{3x+2}{2} &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{3x+1}{2} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
Here

m_{0} = 2,
m_{1} = 2,
m_{2} = 10,
m_{3} = 9,
m_{4} = 9,
m_{5} = 9;

X_{0} = 0,
X_{1} = 0,
X_{2} = 2,
X_{3} = 3,
X_{4} = 1,
X_{5} = 0.

d_{0} = 2,
d_{1} = 2,
d_{2} = 2,
d_{3} = 9,
d_{4} = 9,
d_{5} = 9.

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

Interested viewers can experiment with a BCMATH program.

**Example** (G. Venturini [4] 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)=\left\{\begin{array}{ccc}
4q+r &\mbox{if \(<p\),}\\
p^2q+r &\mbox{if \(r≥p\)}.
\end{array}
\right.
$$
Venturini points out that if x=2^{k}(2y+1)p+r, k ≥ 0 and 0 ≤ r < 2p where |x| ≥ 2p, there is an n ∈ {1, 2k + 1, 2k + 3, 2k + 5} such that |T^{n}(x)| < |x| and consequently every trajectory meets a fixed point T(r)=r, or one of the two cycles with T^{5}(-1) = -1, or T^{5}(-2) = -2. If p = 3, there is only the one cycle, starting with -2, as T(-1) = T^{4}(-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.

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.

\(\mathcal{C}_2=\){B(5,12), B(45,108), B(33,36)},

where \(\mathcal{S}_{\mathcal{C}_2}=B(5,12)\cup B(45,108)\cup B(33,36)\subseteq\mathcal{S}_{\mathcal{C}_1}=B(5,6)\cup B(45,54)\cup B(15,18)\) and corresponding limiting probabilities \((\frac{1}{3}, \frac{1}{3}, \frac{1}{3})\).

We also have transient states:

B(0,6),B(1,6),B(2,6),B(3,6),B(4,6),B(10,12),B(1,12),B(9,12).

For both \(\mathcal{C}_1\) and \(\mathcal{C}_2\), we have \(p_3=\frac{1}{3}+\frac{1}{3}=\frac{2}{3},\quad p_5=\frac{1}{3}\).

Also \((\frac{7}{3})^{2/3}9^{1/3}>1\). Hence we expect most trajectories starting in \(\mathcal{S}_{\mathcal{C}_2}\) and \(\mathcal{S}_{\mathcal{C}_1}\) to diverge.

The trajectories \(\{T^k(-1)\}\) and \(\{T^k(5)\}\) apparently diverge.

Experimentally, \(\{T^k(-1)\}\) meets each of B(11,12), B(99,108), B(15,36) with limiting
frequencies 1/3 and does not meet \(\mathcal{S}_{\mathcal{C}_2}\).

\(\{T^k(5)\}\) meets each of B(5,12), B(45,108), B(33,36) with limiting frequencies 1/3.

There appears to be one cycle \(-2\to-2\).

**Example 5**. (G. Venturini [4], 209-210)

\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{6} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{2x+16}{3} &\mbox{if $x ≡ 1 \pmod{6}$}\\
3x+11 &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{x-3}{6} &\mbox{if $x ≡ 3 \pmod{6}$}\\
x-4 &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{x+9}{2} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
Here

m_{0} = 1,
m_{1} = 4,
m_{2} = 18,
m_{3} = 1,
m_{4} = 6,
m_{5} = 3;

X_{0} = 0,
X_{1} = 6,
X_{2} = 11,
X_{3} = 0,
X_{4} = -4,
X_{5} = 5.

d_{0} = 1,
d_{1} = 4,
d_{2} = 18,
d_{3} = 1,
d_{4} = 6,
d_{5} = 3.

(Contrary to Venturini's statement on line 2, p.210, I cannot find a \(\nu\) such that \(T\in G_\nu(6)\).)

We find 14 states according to the following scheme:

States: 1:B(0,6), 2:B(1,6), 3:B(2,6), 4:B(3,6), 5:B(4,6), 6:B(5,6),

7:B(2,12), 8:B(6,12), 9:B(10,12), 10:B(17,18), 11:B(17,36),

12:B(4,18), 13:B(13,18), 14:B(0,18)

States 7:B(2,12), 11:B(17,36), 13:B(13,18) constitute ergodic chain[1],

and states 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14 are transient states.

The submatrix of Q(6) corresponding to states 7, 11, 13 is \(\displaystyle \left[\begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0, \end{array}\right] \) with stationary vector \((1/3, 1/3, 1/3)\).

Note that \[ T^3(x)=\left\{ \begin{array}{ll} x+36 &\mbox{ if } x\equiv17\pmod{36}\\ x+18 &\mbox{ if } x\equiv13\pmod{18}\\ x+12& \mbox{ if } x\equiv2\pmod{12}. \end{array} \right. \] Hence we get trajectories that contain translations going to infinity.

There appear to be two cycles: \(0\to 0\) and \(1\to 6\to 1\).

Trajectories seem certain to either enter the ergodic set and become a translation, or eventually reach one of the two cycles.

This example is one where in terms of ergodic set [1] we have:

\[ \biggm(\frac{m_2}{d}\biggm)^{p_2}\biggm(\frac{m_5}{d}\biggm)^{p_5}\biggm(\frac{m_1}{d}\biggm)^{p_1}=\left(\frac{18}{6}\right)^{1/3}\left(\frac{3}{6}\right)^{1/3}\left(\frac{4}{6}\right)^{1/3}=1. \] Interested viewers can experiment with a BCMATH program.

Note that Venturini had something to say about this phenomenon in his Theorem 3, p.190.

**Example 4** (G. Venturini, p. 208 with t = 11) (infinitely many cycles)

$$
T(x)=\left\{\begin{array}{ccc}
9x+1 &\mbox{if $x ≡ 0 \pmod{9}$}\\
\frac{x+32}{3} &\mbox{if $x ≡ 1 \pmod{9}$}\\
\frac{x-2}{3} &\mbox{if $x ≡ 2 \pmod{9}$}\\
x+3 &\mbox{if $x ≡ 3 \pmod{9}$}\\
\frac{100x-364}{9} &\mbox{if $x ≡ 4 \pmod{9}$}\\
\frac{x-5}{3} &\mbox{if $x ≡ 5 \pmod{9}$}\\
x-6 &\mbox{if $x ≡ 6 \pmod{9}$}\\
\frac{100x-637}{9} &\mbox{if $x ≡ 7 \pmod{9}$}\\
\frac{x-8}{3} &\mbox{if $x ≡ 8 \pmod{9}$}.
\end{array}
\right.
$$
Here m[0]=81, m[1]=3, m[2]=3, m[3]=9, m[4]=100, m[5]=3, m[6]=9, m[7]=100, m[8]=3;

Here X[0]=1, X[1]=11, X[2]=0, X[3]=3, X[4]=-40, X[5]=-1, X[6]=-6, X[7]=-70, X[8]=-2.

Here d[0]=81, d[1]=3, d[2]=3, d[3]=9, d[4]=1, d[5]=3, d[6]=9, d[7]=1, d[8]=3.

States: 1:B(0,9), 2:B(1,9), 3:B(2,9), 4:B(3,9), 5:B(4,9), 6:B(5,9), 7:B(6,9), 8:B(7,9), 9:B(8,9), 10:B(1,81), 11:B(11,27)

B(0,9), B(1,81), B(11,27), B(3,9), B(6,9) constitute ergodic chain[1];

B(1,9), B(2,9), B(4,9), B(5,9), B(7,9), B(8,9) are transient states.

The submatrix of Q(9) corresponding to the ergodic chain is \[ A=\left[ \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 \end{array} \right]. \] The submatrix is periodic of order 5, and has stationary vector \(\frac{1}{5}(1,1,1,1,1)\).

Also the weighted product is $$ \left(\frac{81}{9}\right)^{1/5} \left(\frac{3}{9}\right)^{1/5} \left(\frac{3}{9}\right)^{1/5} \left(\frac{9}{9}\right)^{1/5} \left(\frac{9}{9}\right)^{1/5}=1. $$ Note that Venturini had something to say about this phenomenon in his Theorem 3, p.190.

There are cycles 4 → 4 and 7 → 7. Also as asserted by Venturini, T^{5}(x) = x for all x in the ergodic chain, so we have infinitely many cycles 9t → 81t+1 → 27t+11 → 9t+3 → 9t+6 → 9t.

I conjecture that all trajectories will eventually enter one of these cycles.

Interested viewers can experiment with a BCMATH program.

**Another 6-branched example** (infinitely many cycles)
\[
T(x)=\left\{\begin{array}{ccc}
\frac{x}{6} &\mbox{if $x ≡ 0 \pmod{6}$}\\
\frac{7x-1}{2} &\mbox{if $x ≡ 1 \pmod{6}$}\\
\frac{x}{2} &\mbox{if $x ≡ 2 \pmod{6}$}\\
\frac{2x}{3}&\mbox{if $x ≡ 3 \pmod{6}$}\\
2x &\mbox{if $x ≡ 4 \pmod{6}$}\\
\frac{9x-1}{2} &\mbox{if $x ≡ 5 \pmod{6}$}.
\end{array}
\right.
\]
Here

m_{0} = 1,
m_{1} = 21,
m_{2} = 3,
m_{3} = 4,
m_{4} = 12,
m_{5} = 27;

X_{0} = 0,
X_{1} = 0,
X_{2} = 0,
X_{3} = 0,
X_{4} = 0,
X_{5} = 0.

There are 19 states, with three ergodic classes: \(\mathcal{C}_1=\){B(4,6), B(8,12)}, \(\mathcal{C}_2=\){B(22,54), B(44,108)}, \(\mathcal{C}_3=\){B(10,12), B(20,24)},

and transient classes B(0,6), B(1,6), B(2,6), B(3,6), B(5,6), B(2,12), B(6,12), B(49,54), B(9,54), b(36,54), B(6,36), B(6,18), B(15,18).

There are cycles \[ \begin{array}{c} 0\to0\\ 1\to3\to2\to1\\ 11\to49\to171\to114\to19\to66\to11\\ 6k+4\to12k+8\to6k+4, k\in\mathbb{Z}. \end{array} \] The weighted product for \(\mathcal{C}_1\) is \((\frac{1}{2})^{1/2}(\frac{2}{1})^{1/2}=1\). Note that Venturini had something to say about this phenomenon in his Theorem 3, p.190.

I conjecture that every trajectory will eventually enter one of the above cycles.

Interested viewers can experiment with a BCMATH program.

**An example of Chris Smyth**. 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. (Corrections). - 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. *The Ultimate Challenge: The 3x+1 Problem*, Ed. Jeffrey C. Lagarias, AMS January 2010, slightly revised version (4th July 2012)

*Last modified 29th June 2023*