Powered by MathJax

Generalized 3x+1 mappings

  1. Introduction
  2. Mappings of type (a) and (b)
  3. Asymptotic behaviour of T-K(B(j, m))
  4. Strongly-mixing property of relatively-prime type mappings
  5. The Markov matrix QT(m)
  6. A simple formula for QT(m)
  7. Irreducible closed sets of QT(m) and ergodic sets of T
  8. Transient classes
  9. Behaviour of divergent trajectories
  10. Conjecture 1
  11. Conjecture 2
  12. Examples [1], [2], [3], [4], [5], [6] [7] of generalized 3x+1 mappings of relatively prime type
  13. Examples [1], [2], [3], [4], [5-prize problem] of mappings satisfying condition (b), but not of relatively prime type
  14. BCMATH cycling-finding program.
  15. References

Introduction

In a paper titled Über Hasses Verallgemeinerung des Syracuse - Algorithmus (Kakutanis Problem), Acta Arith. 34 (1978) 219-226, Herbert Möller studied a d-branched mapping which generalized the famous 3x+1 mapping of Lothar Collatz. The mapping gives rise to a related mapping T: ℤ → ℤ, as follows: Let Rd be a list of representatives from the nonzero residue classes mod d, d > 1. Then if gcd(m,d)=1,

\[ T(x)=\left\{\begin{array}{ccc} \frac{x}{d} &\mbox{if $x ≡ 0 \pmod{d}$,}\\ \frac{mx-r}{d} &\mbox{if $mx ≡ r \pmod{d}, r \in R_d$}. \end{array} \right. \] Then Möller made a conjecture, which restated for T, says that the sequence of iterates x, T(x), T(2)(x),..., eventually cycles for all integers x, if and only if m < dd/(d-1) and that ff this inequality is satisfied, then the number of cycles is finite.
We study a more general function T: ℤ → ℤ with d (> 1) branches, defined in terms of d non-zero integers m0,...,md-1 and d integers x0,...,xd-1:

\[ T(x) = \left\lfloor\frac{m_ix}{d}\right\rfloor + x_i, \mbox{ if $x \equiv i \pmod d$}. \] Equivalently, if r0,...,rd-1 satisfy ri ≡ imi (mod d) for i = 0,...,d-1, then

\[ T(x) = \frac{m_ix - r_i}{d} \mbox{ if $x\equiv i\pmod d$}. \] The 3x+1 (Collatz 1937) mapping T(x)=x ⁄ 2 if x is even, (3x+1) ⁄ 2 if x is odd, corresponds to m0=1, m1=3, x0=0, x1=1.

Starting in 1982, Tony Watts and I investigated the frequencies of occupation of congruence classes mod m of trajectories arising from generalised 3x+1 functions. (See earlier 3x+1 interests)
Experimentally we observed in cases (a) and (b) below, that (apparently) divergent (ie. unbounded) trajectories were attracted to what we called ergodic sets mod m of a Markov matrix QT(m), with limiting frequencies that we were later able to predict.

(a) gcd(mi, d) = 1 for 0 ≤ i ≤ d-1, or

(b) gcd(mi, d2) = gcd(mi, d) for 0 ≤ i ≤ d-1 and d divides m.

Here QTij(m) = pij(m) ⁄ d, where pij(m) is the number of congruence classes mod md which comprise B(i, m) ∩ T-1(B(j, m)), where B(i, m) denotes the congruence class of integers x ≡ i (mod m).

(See a program for constructing QT(m) and finding the ergodic sets and transient classes, using the Fox_Landi algorithm with labels 0,1,...,m-1.)

In the case when neither condition (a) nor (b) holds, it is still possible to get conjectural information using Markov matrices and this was pointed out by George Leigh in 1983.

The asymptotic behaviour of T-K(B(j, m))

Theorem 0. T-1(B(j, m)) is a disjoint union (possibly empty) of ∑' gcd(mi, m) congruence classes (mod md), where Mi = (mii - ri ) ⁄ d and the dash denotes a summation over 0 ≤ i ≤ d-1 and where gcd(mi, m) divides j - Mi.
Proof. We have to solve the congruences

x ≡ i (mod d) and (mix - ri ) ⁄ d ≡ j (mod m)

for i = 0,...,d-1.
Let x = i+dy. Then we have to solve

(mi(i + dy) - ri ) ⁄ d ≡ j (mod m), i.e., miy ≡ j - Mi (mod m).

This congruence is soluble if and only if gcd(mi, m) divides j - Mi, in which case there are gcd(mi, m) solutions for y (mod m) and hence for x (mod md).

Lemma 1. (The Chinese remainder theorem)

Let D = gcd(m, d), L = lcm(d, m). Then the congruences

x ≡ i (mod d) and x ≡ k (mod m)

are soluble if and only if i ≡ k (mod D) and the solution is unique (mod L).

Lemma 2. Let pkj(n, m) be the number of congruence classes mod nd contained in B(k, m) ∩ T-1(B(j, n)), where m divides n.
Then pkj(n, m) is given by the following formula:

Let D = gcd(m, d), L = lcm(d, m) and let Sk,D consist of the integers i≡ k (mod D), 0 ≤ i ≤ d-1. Also for i ∈ Sk,D, let xi denote the solution of

x ≡ i (mod d) and x ≡ k (mod m), 0 ≤ x ≤ L-1.

Finally let Mi = (mi xi - ri ) ⁄ d if i ∈ Sk,D. Then

pkj(n, m)=∑' gcd(mi, n, nd ⁄ m),

where the dash denotes summation over those i ∈ Sk,D such that (m ⁄ D)gcd(mi, n, nd ⁄ m) divides j - Mi.

Proof. We have

B(k, m) ∩ T-1(B(j, n)) = {x ∈ ℤ | x ≡ k (mod m) & T(x) ≡ j (mod n)}.

Hence for each i = 0,..., d-1, we have to solve the congruences

x ≡ i (mod d), x ≡ k (mod m), (mix - ri ) ⁄ d ≡ j (mod n)

Write x = xi + Ly, i ∈ Sk,D. Then we have to solve

(mi(xi + Ly) - ri ) ⁄ d ≡ j (mod n), or (mim ⁄ D)y ≡ j - Mi (mod n).

This congruence is soluble if and only if t = gcd(mim ⁄ D, n) divides j - Mi, in which case the solution for y is unique (mod n ⁄ t). Now

gcd(mim ⁄ D, n) = (m ⁄ D)gcd(mi, n, nd ⁄ m)

Hence, in the case of solubility, the solution for x is unique mod

Ln ⁄ t = LDn ⁄ mgcd(mi, n, nd ⁄ m) = nd ⁄ gcd(mi, n, nd ⁄ m).

Hence there are gcd(mi, n, nd ⁄ m) solutions for x (mod nd).

Lemma 3. Under conditions (a) or (b) above, if α ≥ 1,

pkj(mdα, m) = pkj(m, m),

Proof. By Lemma 2,

pkj(mdα, m) = ∑' gcd(mi, mdα, dα+1),

where the summation is over those i ∈ Sk,D satisfying

(m ⁄ D) gcd(m i, mdα, dα+1) divides j - Mi.

However

gcd(m i, mdα, dα+1) = gcd(mi, dα gcd(m, d)).

So if condition (a) holds, the rhs = 1; while if condition (b) holds, the rhs is equal to gcd(mi, dα+1) = gcd(mi, d).
Consequently in both cases, the rhs is constant for α ≥ 0 and hence pkj(mdα, m) = pkj(m, m).

Theorem 1. Write pkj(m, m)=pkj(m). Then under conditions (a) or (b) above, the cylinder

B(i0, m) ∩ T-1(B(i1, m)) ∩ ··· ∩ T-K(B(iK, m))

consists of pi0i1(m) ··· piK-1iK(m) congruence classes (mod mdK).

Proof. We argue by induction.

B(i0, m) ∩ T-1(B(i1, m)) ∩ ··· ∩ T-(K+1)(B(iK+1, m)) = B(i0, m) ∩ T-1{B(i1, m) ∩ ··· ∩ T-K(B(iK+1, m))}

Now by the induction hypothesis, B(i1, m) ∩ ··· ∩ T-K(B(iK+1, m)) consists pi1i2(m) ··· piKiK+1(m) congruence classes (mod mdK).
If B(L, mdK) is such a congruence class, then it is contained in B(i1, m) and hence L ≡ i1 (mod m). Also
B(i0, m) ∩ T-1 (B(L, mdK)) is a disjoint union of pi0L(mdK, m) congruence classes (mod mdK+1).
But by Lemma 3,

pi0L(mdK, m) = pi0L(m, m) = pi0i1(m, m).

Hence B(i0, m) ∩ T-1{B(i1, m) ∩ ··· ∩ T-K(B(iK+1, m))} is a disjoint union pi0i1(m) pi1i2(m) ··· piKiK+1(m) congruence classes (mod mdK+1) and the induction goes through.

Corollary 1. Under conditions (a) or (b), if pKjk(m) is the number of congruence classes (mod mdK) contained in B(j, m) ∩ T-K(B(k, m)), then

[pKjk(m)]=[pjk(m)]K.

Theorem 2. Let qjk(m) = pjk(m) ⁄ d. Then QT(m) = [qjk(m)] is a Markov matrix, i.e.. a matrix with non-negative entries, each of whose row sums equals 1.

Proof. \[ B(j,m)=B(j,m)\cap\mathbb{Z}=B(j,m)\cap T^{-1}(\mathbb{Z})=\bigcup_{0\leq k\leq m-1}\left\{B(j,m)\cap T^{-1}(B(k,m))\right\}. \] Hence B(j,m) is a disjoint union of \(\displaystyle\sum_{0\leq k\leq m-1}p_{jk}(m)\) congruence classes (mod md).
But B(j,m) is a disjoint union of d congruence classes (mod md), so \[ \sum_{0\leq k\leq m-1}p_{jk}(m)=d. \]

Simplified formula for qij(m) when d divides m.

If d divides m, the formula for qij(m) simplifies to

qij(m) = gcd(mi, d) ⁄ d, if j ≡ T(i) (mod (m ⁄ d)gcd(mi, d)), otherwise qij(m) = 0.

Hence in the relatively prime case, if d divides m, the formula for qij(m) reduces to

qij(m) = 1 ⁄ d, if j ≡ T(i) (mod m ⁄ d), otherwise 0.

Example. (3x+1 mapping, m = 3.)

\[ Q_T(3)=\left[ \begin{array}{ccc}\frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 0 & 1\\ 0 &\frac{1}{2} & \frac{1}{2} \end{array} \right]. \] Under the row/column relabelling (0, 1, 2) → (1, 2, 0),
\[ Q_T(3)\to A=\left[ \begin{array}{ccc} 0 & 1 & 0\\ \frac{1}{2} & \frac{1}{2} & 0\\ 0 &\frac{1}{2} & \frac{1}{2} \end{array} \right]. \]

\[ A^n=\left[ \begin{array}{ccc} (1+(-1)^n/2^{n-1})/3&(2-(-1)^n/2^{n-1})/3 & 0 \\ (1-(-1)^n/2^n)/3&(2+(-1)^n/2^n)/3 & 0 \\ (1+(-1)^n/2^{n+1})/3 -1/2^{n+1} & (2-(-1)^n/2^{n+1})/3 -1/2^{n+1} & 1/2^n \end{array} \right]. \]

Example. (Relatively-prime case)
If A = B(j, da) and B = B(k, db), then T-k(A) ∩ B is a disjoint union of dk-b congruence classes (mod dk+a) if k ≥ b.
(This fact is the basis of the strongly-mixing property, when the mapping is extended to the d-adic integers.

Proof. Express A and B as cyclinders.

Irreducible closed sets of QT(m) and ergodic sets of T

A non-empty subset S of {0,...,m-1} is called a closed set of QT(m) if j ∈ S and qjk > 0 ⇒ k ∈ S.

These are in 1-1 correspondence with the T-invariant subsets of ℤ composed of congruence classes (mod m): \[ S=\left\{j_1,\ldots,j_n\right\}\leftrightarrow\Phi(S)=B(j_1,m)\cup\cdots\cup B(j_n,m). \] Proof. Suppose S is closed. We show S' = Φ(S) is T-invariant.
This is equivalent to showing that S' ⊆ T-1(S'), i.e., T-1(ℤ - S') ∩ S' = ∅.
So suppose B(j, m) ⊆ S' and B(k, m) ⊆ ℤ - S'. Then j ∈ S and k ∉ S and hence qjk = 0. Hence B(j, m) ∩ T-1(B(k, m)) = ∅, as required. The argument is reversible.

We call the minimal T-invariant subsets of ℤ consisting of congruence classes (mod m) ergodic sets (mod m) of T. Clearly these are in 1-1 correspondence with the irreducible closed sets of QT(m).

The set {0,...,m-1} decomposes into a disjoint union of t irreducible sets and other elements called transient.
Correspondingly ℤ decomposes into a union of ergodic sets (mod m) and a collection of transient congruence classes.

With a suitable relabelling of the rows and columns, QT(m) can be transformed into the following form:

\[ \left[ \begin{array}{ccccc} A_1 & 0 & \cdots & \cdots & 0\\ 0 & A_2 & \cdots & \cdots & 0\\ \cdots & \cdots & \cdots & \cdots & 0\\ 0 & 0 & \cdots & A_t & 0\\ B_1 & B_2 & \cdots & B_t & C \end{array} \right] \]

where matrices A1,...,At and C correspond to the irreducible closed sets and transient classes, respectively.

Theorem 3. If gcd(mi, m) = 1 for i = 0,...,d-1, then QT(m) is doubly stochastic, i.e., each column sum is equal to 1.
Proof. \[ T^{-1}(B(k,m)) =\bigcup_{0\leq j\leq m-1}B(j,m)\cap T^{-1}(B(k, m)). \] Hence T-1(B(k, m)) is a disjoint union of \(\displaystyle\sum_{0\leq j\leq m-1}p_{jk}(m)\) congruence classes (mod md).
However from Theorem 1, this number is d if gcd(mi, m) = 1 for i = 0,...,d-1. Hence \[ \sum_{0\leq j\leq m-1}p_{jk}(m)=d. \] Theorem 4. If m divides mi, where gcd(m, d) = 1, then QT(m) has only one irreducible closed set. Moreover if gcd(mi, d) = 1 for i = 0,...,d-1, then the corresponding submatrix A is primitive, i.e., a suitable power is positive.
Proof. (Tony Watts 1983) Let Mi = (mii - ri) ⁄ d, where m divides mi. Also let x = amd + bd + i. Then

T(x)= (mi(amd + bd + i) - ri) ⁄ d = ammi + mib + Mi ≡ Mi (mod m).

But if 0 ≤ j ≤ m-1, there exists an integer b such that

amd + bd + i ≡ j (mod m).

Hence B(j, m) ∩ T-1(B(Mi, m)) ≠ ∅ and so qjMi > 0. Thus all the elements in column Mi (mod m) are positive and hence by examining the above normal form of QT(m), we see that t = 1.

For the second part, assume gcd(mi, d) = 1 for i = 0,...,d-1. By standard theory, if A is not primitive, it is periodic with period s and As has s irreducible closed sets. However it is easy to see from Corollary 1 that

QTs(m) = (QT(m))s.

Hence QTs(m) has s irreducible closed sets.

However Ts has ds branches and associated "mi" equal to mi1 ··· mis, where 0 ≤ i1,...,is ≤ d-1; also each of these numbers is relatively prime to ds. Hence by the first part of the proof, QTs(m) has but one irreducible closed set.

Corollary 2. If m divides mi, where gcd(mj, d) = 1 for j = 0,...,d-1, then Q(mk) has only one irreducible closed set. Moreover the corresponding submatrix is primitive.
Proof. Suppose gcd(mi, d) = 1 for i = 0,...,d-1. Then the dk cylinders

B(i0, d) ∩ T-1(B(i1, d)) ∩ ··· ∩ T-(k-1)(B(ik-1, d))

are precisely the dk congruence classes (mod dk).

Now suppose m divides mi. Then

B(i, d) ∩ T-1(B(i, d)) ∩ ··· ∩ T-(k-1)(B(i, d)) = B(j, dk)

for some j and hence

Th(j) ≡ i (mod d) for h = 0,...,k-1.

Consequently mik is one of the "mi" for Tk. Also mk divides mik. So applying the previous theorem, we deduce that QTk(mk) has only one irreducible closed set.

However from Corollary 1,

QTk(mk) = (QT(mk))k,

so it follows that QT(mk) has precisely one irreducible closed set.

Remark. A complete description of the ergodic sets in the relatively-prime case was done in paper [5].

Theorem. Let N1 be the set of positive integers composed of primes which divide at least one mi and let N2 be the set of positive integers which are relatively prime to each mi. Also let

Δi,j = rj(d-mi) - ri(d-mj) for 0 ≤ i < j ≤ d-1

and \[ \Delta=\gcd_{0\leq i\lt j\leq d-1}\Delta_{i,j}. \] Then
  1. If m ∈ N2 and gcd(m, Δ) = 1, then ℤ is the only ergodic set (mod m).
  2. If m ∈ N2 and gcd(m, Δ) = δ > 1, then the ergodic sets (mod m) are the ergodic sets (mod δ).
  3. If m ∈ N1, there is only one ergodic set (mod m) with possibly some transient classes.
  4. If m = m1m2, (m1 > 1 and m2 > 1) where m1 ∈ N1 and m2 ∈ N2, then the ergodic sets (mod m) are the intersections of an ergodic set (mod m1) with an ergodic set (mod m2), where m2 | Δ and m2 ∈ N2.

Behaviour of divergent trajectories

Experimentally, it appears that divergent trajectories occupy congruence classes with limiting frequencies. i.e., \[ \lim_{N\rightarrow\infty}\frac{1}{N}\#\left\{k < N \mid T^k(x)\equiv j\pmod{m}\right\} \] exists if \(|T^k(x)|\rightarrow\infty\).

It is not difficult to show that if limiting frequencies f0,...,fd-1 (mod d) exist, then

|Tk(x)|1/k → ( |m0|f0···|md-1|fd-1 ) / d,

as k → ∞.
(This follows, by taking logarithms, from the identity

\[ T^k(x)=\frac{x}{d^k}\prod_{0\leq i\leq k-1}m_i(x)\prod_{0\leq i\leq k-1}\frac{1-r_i(x)}{m_i(x)T^i(x)}. \] Here (i) we are assuming that Ti(x) ≠ 0 and (ii) if Ti(x) ≡ j (mod d), we let mi(x) = mj and ri(x) = rj.)

Conjecture 1.
Under the conditions (a) gcd(mi, d) = 1 for 0 ≤ i ≤ d-1, or (b) gcd(mi, d2) = gcd(mi, d) for 0 ≤ i ≤ d-1 and d divides m, a divergent trajectory {Tk(x)} will eventually enter some ergodic set S (mod m).
If B(j, m) ⊆ S, the limiting frequency \[ \lim_{N\rightarrow\infty}\frac{1}{N}\#\left\{k < N \mid T^k(x)\equiv j\pmod{m}\right\}=\mu_S(j,m), \] where μS(j, m) is the j (mod m) component of the stationary vector of Q(m) for the irreducible closed set corresponding to S.

A standard result from the theory of Markov matrices tells us that \[ \mu_S(j,m)= \lim_{N\rightarrow\infty}\frac{1}{N}\sum_{k<N}\frac{card_{md^k}(T^{-k}(B(j,m))\cap S)}{card_{md^k}(S)}, \] where t = cardmdk(A) means that A is composed of t congruence classes (mod mdk).
If there are no periodic matrices in the canonical form of Q(m), the Cesàro limit can be replaced by the ordinary limit.

Without the summation sign, this limit is perhaps what one would expect the limiting frequency to be.

Conjecture 2. Let S be an ergodic set (mod d). Then

  1. If \[ \prod_{B(i,d)\subseteq S}\mid\frac{m_i}{d}\mid^{\mu_S(i,d)} < 1, \] then all trajectories starting in S will eventually become periodic.
  2. If \[ \prod_{B(i,d)\subseteq S}\mid\frac{m_i}{d}\mid^{\mu_S(i,d)} > 1, \] then almost all trajectories starting in S will be divergent. i.e., except for an exceptional set S of integers n satisfying #{n ∈ S | -X ≤ n ≤ X} = o(X).
If we are dealing with a type (b) mapping \(T\) with positive \(m_0,\ldots,m_{d-1}\) and the weighted product equals \(1\), G. Venturini showed what happens with his Theorem 3.

In the relatively prime case (a), Q(da) is doubly-stochastic and ℤ is the only ergodic set (mod da). The corresponding stationary vector has all its components equal to 1 ⁄ da. Hence we have

Conjecture 3. Suppose gcd(mi, d) = 1 for 0 ≤ i ≤ d-1. Then

  1. There are finitely (≥ 1 - see Lagarias - survey) many cycles.
    The reader can find cycles by using the author's BCMATH program.
  2. If |m0···md-1| < dd, then all trajectories will eventually cycle.
  3. If |m0···md-1| > dd, then almost all trajectories will eventually diverge.
  4. If the trajectory {Tk(x)} is divergent, then \[ \lim_{N\rightarrow\infty}\frac{1}{N}\#\left\{k < N \mid T^k(x)\equiv j\pmod{d^a}\right\}=\frac{1}{d^a}. \] Equivalently, since B(j0, d) ∩ T-1(B(j1, d)) ∩ ··· ∩ T-(a-1)(B(ja-1, d)) runs over the da congruence classes (mod da), \[ \lim_{N\rightarrow\infty}\frac{1}{N}\#\left\{k < N \mid T^k(x)\equiv j_0\pmod{d},\ldots, T^{k+a-1}(x)\equiv j_{a-1}\pmod{d}\right\}=\frac{1}{d^a}. \]
In addition, the number of cycles is conjectured to be finite.

Remarks

  1. The cycling situation is not so clear if condition (b) holds, though it seems likely that we only get infinitely many cycles for trivial reasons. eg. The mapping T(2n) = 2n+1, T(2n+1) = 2n.
    Also see an example (not of type (a) or (b)) of Chris Smyth.
  2. By choosing integers m0,...,md-1 so that the product of their absolute values is close to, but less than dd, we expect some trajectories may take many iterations to reach a cycle and some cycles to be rather long.

Examples of generalized 3x+1 mappings of relatively prime type

  1. (The 3x+1 mapping). Here 1·3 < 22 and so condition (1) is satisfied.
    Hence we expect all trajectories to cycle. In fact there appear to be only five cycles:

    (a) 0, 0;
    (b) 1, 2, 1;
    (c) -1, -1;
    (d) -5, -7, -10, -5;
    (e) -17, -25, -37, -55, -82, -41, -61, -91, -136, -68, -34, -17.

    (The reader is invited to experiment with a BCMATH program.)

    It can be shown that if 3 does not divide m, then ℤ is the only ergodic set S (mod m), whereas is 3 divides m, ℤ-3ℤ is the only ergodic set S (mod m). (The reader can experiment with a BCMATH program.)
    In both cases, the matrix corresponding to S is primitive.

  2. (The 3x+k mapping, k odd). Here 1 · 3 < 22 and so condition (1) is satisfied.
    Hence we expect all trajectories to cycle and that there will be finitely many cycles.

    Experimentally, we find that as k varies, the number of cycles is unbounded, as is the greatest length of a cycle.
    In fact, in answer to a question from the author, Alan Jones showed that with k = 2N - 9, N = 2c + 1, the integers 2r + 3, 1 ≤ r ≤ c generate c different cycles each of length N.

    The number of cycles for the mappings with k = 5t appears to grow monotonically, as does the maximum cycle length.

  3. More generally, consider the mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{x+a}{2} &\mbox{if $x ≡ 0 \pmod{2}$}\\ \frac{3x+b}{2} &\mbox{if $x ≡ 1 \pmod{d}$}. \end{array} \right. \] where a is even and b is odd. Again we expect all trajectories to eventually cycle. We always get at least the following 5 cycles, which generalize those of the 3x+1 mapping:

    1. a, a;
    2. -b, -b;
    3. b+2a, 2b+3a, b+2a;
    4. -5b-4a, -7b-6a, -10b-9a, -5b-4a;
    5. -17b-16a, -25b-24a, -37b-36a, -55b-54a, -82b-81a, -41b-40a, -61b-60a, -91b-90a, -136b-135a, -68b-67a, -34b-33a, -17b-16a.

  4. The 3-branched mapping defined by \[ T(x)=\left\{\begin{array}{ccc} \frac{x}{3} &\mbox{if $x ≡ 0 \pmod{3}$}\\ \frac{2x-2}{3} &\mbox{if $x ≡ 1 \pmod{3}$}\\ \frac{13x-2}{3} &\mbox{if $x ≡ 2 \pmod{3}$} \end{array} \right. \] is of relatively prime type and as 1 · 2 · 13 < 33, we expect all trajectories to cycle. We have found only seven cycles, with starting values 0, 2, 47, -2, -10, -22 and -265138. The trajectory starting with x = 338 takes 7161 iterations to reach 2. Also the maximum size of an iterate is that of T2726(338), which has 73 digits!
  5. The 4-branched mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{x}{4} &\mbox{if $x ≡ 0 \pmod{4}$}\\ \frac{3x-3}{4} &\mbox{if $x ≡ 1 \pmod{4}$}\\ \frac{5x-2}{4} &\mbox{if $x ≡ 2 \pmod{4}$}\\ \frac{17x-3}{4} &\mbox{if $x ≡ 3 \pmod{4}$.} \end{array} \right. \] Here 1 · 3 · 5 · 17 = 255 = 44 - 1.
    We have found 17 cycles, starting at 0, -3, 2, 3, 6 (length 1747), -18, -46, -122, -330, -117, -137, -186, -513 (length 1426), -261, -333, 5127, -5205.
  6. (The 5x+1 mapping). Here 1·5 > 22 and so condition (2) is satisfied.
    Hence we expect almost all trajectories to diverge. For such trajectories we expect |Tk(x)|1/k → √5 ⁄ 2.
    The trajectory starting with x=7 appears to diverge.
    In fact there appear to be only five cycles, with starting values 0, 1, 13, 17 and -1.

    Divergent trajectories appear to occupy the congruence classes (mod 5) with limiting frequencies 0, 1 ⁄ 15, 2 ⁄ 15, 8 ⁄ 15 and 4 ⁄ 15.

    \[ Q(5)=\left[ \begin{array}{ccccc} 1/2 & 0 & 0 & 1/2 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 1/2 & 0 & 1/2 & 0\\ 0 & 0 & 0 & 1/2 & 1/2\\ 0 & 0 & 1/2 & 1/2 & 0 \end{array} \right]. \] Here 1, 2, 3, 4 form an ergodic set for Q(5) and 0 is the only transient state.

    On relabelling the states as 1, 2, 3, 4, 0, Q(5) transforms to canonical form \[ \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0\\ 1/2 & 0 & 1/2 & 0 & 0\\ 0 & 0 & 1/2 & 1/2 & 0\\ 0 & 1/2 & 1/2 & 0 & 0\\ 0 & 0 & 1/2 & 0 & 1/2 \end{array} \right] \] and the stationary vector of the submatrix formed by the first 4 rows and columns is \((\frac{1}{15}, \frac{2}{15},\frac{8}{15},\frac{4}{15}\)).

    The zero limiting frequency is easily explained: if x = 2c + 1, then T(x) = 5c + 3, so clearly every trajectory starting from a non-zero integer will eventually reach B(3, 5).

  7. (The 5x-3 mapping). Here B(0,3) and B(1,3) ∪ B(2,3) are ergodic sets (mod 3). This may be seen directly or from \[ Q(3)=\left[ \begin{array}{ccc} 1 & 0 & 0\\ 0 & 1/2 & 1/2\\ 0& 1/2 & 1/2 \end{array} \right]. \] The trajectory starting with -7 appears to be divergent.
    There appear to be 10 cycles, with starting numbers 0, -1, 1, -3, 3, -39, -43, -51, -53, -61.
  • Examples of generalized 3x+1 mappings satisfying condition (b), but not of relatively prime type

    1. The 3-branched mapping defined by \[ T(x)=\left\{\begin{array}{ccc} \frac{x}{3}-1 &\mbox{if $x ≡ 0 \pmod{3}$}\\ \frac{x+5}{3} &\mbox{if $x ≡ 1 \pmod{3}$}\\ 10x-5 &\mbox{if $x ≡ 2 \pmod{3}$.} \end{array} \right. \] Here \[ Q(3)=\left[ \begin{array}{ccc} 1/3 & 1/3 & 1/3\\ 1/3 & 1/3 & 1/3\\ 1& 0 & 0 \end{array} \right]. \] Now Q(3)2 is a positive matrix, so ℤ is an ergodic set. Also the stationary vector here is (1 ⁄ 2, 1 ⁄ 4, 1 ⁄ 4).

      Also

      (1 ⁄ 3)½(1 ⁄ 3)¼(30 ⁄ 3)¼ < 1,

      so we expect all trajectories to eventually cycle. In fact there appear to be five cycles, starting with values 0, 5, 17, -1, -4.

      George Leigh (1983) pointed out that cycling can also be predicted by considering the related mapping T', where \[ T'(x)=\left\{\begin{array}{rll} T(x) &\mbox{if $x ≡ 0$ or $1\pmod{3}$}\\ T^2(x)=\frac{10x-8}{3} &\mbox{if $x ≡ 2 \pmod{3}$.} \end{array} \right. \] For T' is of relatively prime type and 1 · 1 · 10 < 33, so we expect everywhere cycling.

    2. (Collatz) The 3-branched mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{2x}{3} &\mbox{if $x ≡ 0 \pmod{3}$}\\ \frac{4x-1}{3} &\mbox{if $x ≡ 1 \pmod{3}$}\\ \frac{4x+1}{3} &\mbox{if $x ≡ 2 \pmod{3}$} \end{array} \right. \] is of relatively prime type and 2 · 4 · 4 > 33. So we expect most trajectories to be divergent.
      The trajectory {Tk(8)} appears to be divergent. There appear to be 9 cycles, with starting values 0, 1, 2, 4, 44, -1, -2, -4, -44.

      T is a 1-1 mapping and its inverse S is the four-branched mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{3x}{2} &\mbox{if $x ≡ 0 \pmod{4}$}\\ \frac{3x+1}{4} &\mbox{if $x ≡ 1 \pmod{4}$}\\ \frac{3x}{2} &\mbox{if $x ≡ 2 \pmod{4}$}\\ \frac{3x-1}{4} &\mbox{if $x ≡ 3 \pmod{4}$.} \end{array} \right. \] Here \[ Q(4)=\left[ \begin{array}{cccc} 1/2 & 0 & 1/2 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 \\ 0 & 1/2 & 0 & 1/2 \\ 1/4 & 1/4 & 1/4 & 1/4 \end{array} \right] \] and this is doubly-stochastic. Hence ℤ is an ergodic set and(¼, ¼, ¼, ¼) is the stationary vector.

      Also

      (6 ⁄ 4)¼ (3 ⁄ 4)¼ (6 ⁄ 4)¼ (3 ⁄ 4)¼ > 1,

      so again we expect most trajectories of S to be divergent.
    3. The 4-branched mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{3x}{2} &\mbox{if $x ≡ 0 \pmod{4}$}\\ \frac{x+1}{2} &\mbox{if $x ≡ 1 \pmod{4}$}\\ \frac{x}{2}+1 &\mbox{if $x ≡ 2 \pmod{4}$}\\ \frac{7x+1}{2} &\mbox{if $x ≡ 3 \pmod{4}$.} \end{array} \right. \] Here \[ Q(4)=\left[ \begin{array}{cccc} 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2\\ 1/2 & 0 & 1/2 & 0\\ 0 & 1/2 & 0 & 1/2 \end{array} \right] \] which under permutation (0, 2, 1, 3) transforms to normal form

      \[ \left[ \begin{array}{cccc} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 1/2\\ 0 & 0 & 1/2 & 1/2 \end{array} \right]. \] The submatrices have stationary vectors (½, ½).
      Hence S1 = B(0, 4) ∪ B(2, 4) and S2 = B(1, 4) ∪ B(3, 4) are ergodic sets.

      The weighted product for S1 is (6 ⁄ 4)½(2 ⁄ 4)½ < 1 and for S2 is (2 ⁄ 4)½(14 ⁄ 4)½ > 1.

      So we expect all trajectories starting with an even integer to eventually cycle, while most trajectories starting with an odd integer should be divergent.

    4. The 4-branched mapping \[ T(x)=\left\{\begin{array}{ccc} \frac{3x}{2}+1 &\mbox{if $x ≡ 0 \pmod{4}$}\\ \frac{x-1}{2} &\mbox{if $x ≡ 1 \pmod{4}$}\\ \frac{x}{2} &\mbox{if $x ≡ 2 \pmod{4}$}\\ \frac{7x-1}{2} &\mbox{if $x ≡ 3 \pmod{4}$.} \end{array} \right. \] Here \[ Q(4)=\left[ \begin{array}{cccc} 0 & 1/2 & 0 & 1/2\\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2\\ 1/2 & 0 & 1/2 & 0. \end{array} \right]. \] The matrix is periodic with period 2 and ℤ is the only ergodic set (mod 4).

      The stationary vector is (¼,¼,¼,¼) and the weighted product is (6 ⁄ 4)¼(2 ⁄ 4)¼(2 ⁄ 4)¼(14 ⁄ 4)¼ > 1.
      Hence we expect almost all trajectories to diverge.

    5. The 3-branched mapping \[ T(x)=\left\{\begin{array}{ccc} 2x &\mbox{if $x ≡ 0 \pmod{3}$}\\ \frac{7x+2}{3} &\mbox{if $x ≡ 1 \pmod{3}$}\\ \frac{x-2}{3} &\mbox{if $x ≡ 2 \pmod{3}$.} \end{array} \right. \] Here \[ Q(3)=\left[ \begin{array}{ccc} 1 & 0 & 0\\ 1/3 & 1/3 & 1/3\\ 1/3 & 1/3 & 1/3 \end{array} \right] \] and B(0, 3) is an ergodic set (mod 3). Also B(1, 3) and B(2, 3) are transient classes.
      In any case, clearly x ≡ 0 (mod 3) ⇒ T(x) ≡ 0 (mod 3). Hence a trajectory starting in the zero class (mod 3) remains there.
      All divergent trajectories starting in the congruence classes x ≡ ±1 (mod 3) appear to eventually enter B(0, 3).
      We believe that if Tk(x) ≡ ±1 (mod 3) for all k ≥ 0, then the trajectory must eventually enter one of the cycles -1, -1 or -2, -4, -2.
      The author offers a $100 (Australian) prize for a proof.
      The problem seems just as intangible as the 3x + 1 problem, moreso as the number of steps taken to enter the zero class is spectacularly short.
      The reader 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. K.R. Matthews, Some Borel measures associated with the generalized Collatz mapping, Colloquium Math. 63 (1992), 191-202.
    5. H. Möller, Über Hasses Verallgemeinerung des Syracuse - Algorithmus (Kakutanis Problem), Acta Arith. 34 (1978) 219-226.
    6. 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.
    Top of page

    Last 24th May 2023