On Collatz Words, Sequences, and Trees

Wolfdieter Lang Karlsruhe Germany

                wolfdieter.lang@partner.kit.edu

Abstract Motivated by recent work of Trümper, we consider the general Collatz word (updown pattern) and the sequences following this pattern. We derive recurrences for the first and last sequence entries from repeated application of the general solution of a binary linear inhomogeneous Diophantine equation. We solve these recurrences and also discuss the Collatz tree.

1 Introduction

The Collatz map C for natural numbers maps an odd number m to 3m + 1 and an even number to m/2. The Collatz conjecture (see Lagarias [4] for original references) is the claim that every natural number n ends up, after sufficiently many iterations of the map C, in the trivial cycle (4, 2, 1).

Motivated by the work of Trümper [9] we consider a general finite Collatz word on the alphabet {u, d}, where u (for ‘up’) indicates application of the map C on an odd number, and d (for ‘down’) for applying the map C on an even number. The task is to find all sequences which follow this word pattern (to be read from left to right). These sequences are called CS (for Collatz sequence, also for the plural) realizing the CW (for Collatz word, also for the plural) under consideration. This problem was solved by Trümper [9] under the restriction that the first and last sequence entries are odd. Here we do not use this restriction. The solutions are given in terms of recurrence relations for the first and last entries of the CS for a given CW. This involves a repeated application of the general solution in positive integers of the linear inhomogeneous Diophantine equation ax + by = c, with a = 3^{m}, b = 2^{n} and given integer c = c(m, n). Because gcd(3, 2) = 1, one always has a countably infinite number of solutions. This general solution depends on a non-negative integer parameter k. We believe that our solution is more straightforward than the one given by Trümper [9].

2 Collatz words, sequences and the Collatz tree

The Collatz map C : ℕ → ℕ, m ↦ 3m + 1 if m is odd, m ↦ m/2 if m is even, leads to an increase u (for ‘up’) or decrease d (for ‘down’), respectively. Finite Collatz words over the alphabet {u, d} are considered with the restriction that, except for the one letter word u, every u is followed by a d, because 2m + 1 ↦ 2(3m + 1). This is the reason for also introducing (with Trümper [9]) s := ud. Thus s stands for 2m + 1 ↦ 3m + 1. The general finite word is encoded by an (S + 1)−tuple n⃗_{S} = [n_{0}, n_{1}, …, n_{S}] with S ∈ ℕ.

CW (n⃗_{S+1}) = d^{n_{0}}sd^{n_{1}−1}s ⋯ sd^{n_{S}−1}  (1)
= (d^{n_{0}}s)(d^{n_{1}−1}s) ⋯ (d^{n_{S−1}−1}s)d^{n_{S}−1}

with n_{0} ∈ ℕ_{0} := ℕ ∪ {0}, n_{i} ∈ ℕ, for i = 1, 2, …, S. The number of letters of u (that is of s = ud) in the word CW (n⃗_{S}), or CW (S), for short, is S (which is why we have used n⃗_{S} not n⃗_{S+1} for the (S + 1)−tuple), and the number of letters of d is

D(S) := ∑_{j=0}^{S} n_{j}.

In the paper of Trümper [9] n_{0} = 0 (start with an odd number), y = S and x = D(S).

Some special words are not covered by this notation: first the one-letter word u with the Collatz sequence (CS) of length two CS(u; k) = [2k + 1, 2(3k + 2)], and CW ([n_{0}]) = d^{n_{0}} with the family of sequences CS([n_{0}]; k) = [2^{n_{0}}k, 2^{n_{0}−1}k, …, 1k] with k ∈ ℕ_{0}.

A Collatz sequence CS realizing a word CW (n⃗_{S}) is of length L = D + S + 1, and follows the word pattern from the left to the right:

CS(n⃗_{S}) = [c_{1}, c_{2}, …, c_{L}].

For example, CW ([1, 2, 1]) = dsds with S = 2, D(2) = 2, and length L = 7 with SC_{0}(n⃗_{S}) = [2, 1, 4, 2, 1, 4, 2] is the first of these sequences (for non-negative integers), the one with smallest starting number c_{1}. In order to conform with the notation used by Trümper [9], we use c_{1} = M for the starting number and c_{L} = N for the last number.

However, in the paper [9] M and N are restricted to be odd, which is not the case here. Later one can get the words with odd starting number M by choosing n_{0} = 0. In order to also have N odd, one has to pick only the odd numbers from SC_{k}([0, n_{1}, …, n_{S}]), for k ∈ ℕ_{0}.

In the Trümper [9] article the monoid of Collatz words, with the unit element e = empty word is treated. This is not considered in this work. Also the connection to the 3m − 1 problem is not pursued here.

The Collatz tree CT is an infinite (incomplete) ternary tree, starting with the root, the number 8 on top at level l = 0. Three branches, labeled L, V and R can be present. If a node (vertex) has label n ≡ 4 (mod 6) the out-degree is 2 with a left edge (branch) labeled L ending in a node with label \frac{n−1}{3} and a right edge (label R) ending in the node labeled 2n.

In the other cases, n ≡ 0, 1, 2, 3, 5 (mod 6), with out-degree 1, a vertical edge (label V) ends in the node labeled 2n. The root labeled 8 stands for the trivial cycle 8 repeat(4, 2, 1). See Figure 1 for CT_{7} with only the first eight levels.

It may seem that this tree is left-right symmetric (disregarding the node labels), but this is no longer the case starting at level l = 12. At level l = 10 the mod 6 structure of the left and right part of CT, also taking into account the node labels, is broken for the first time, but the node labels 4 (mod 6) are still symmetric. At the next level l = 11 the left-right symmetry concerning the labels 4 (mod 6) is also broken, leading at level l = 12 to a symmetry breaking in the branch structure of the left and right part of CT. Thus at level l = 12 the number of nodes becomes odd for the first time: 15 nodes on the left side versus 14 nodes on the right one. See rows l + 3 of \underline{A127824} for the node labels of the first levels, and \underline{A005186}(l + 3) for the number of nodes. The number of 4 (mod 6) nodes at level l is given in \underline{A176866}(l + 4).

A CS is determined uniquely from its starting number M. Therefore no number can appear twice in CT, except for the numbers 1, 2, 4 of the (hidden) trivial cycle. The Collatz conjecture is that every natural number appears in CT at some level (1, 2, and 4 are hidden in the root 8). A formula for l = l(n) would prove the conjecture.

Reading CT from bottom to top, beginning with some number M at a certain level l, recording the edge labels up to level l = 0, leads to a certain L, V, R-sequence. For example, M = 40 at level l = 5 generates the length 5 sequence [V, R, V, L, V]. This is related to the CS starting with M = 40, namely [40, 20, 10, 5, 16, 8], one of the realizations of the CW dddud = d^{3}s, with S = 1 and n⃗_{1} = [3, 1]. (Later we shall see that this is the realizations with the third smallest starting number, the smaller once are 8 and 24). One has to map V and R to d and L to u. This shows that the map from a L, V, R-sequence to a CW is not one to one. The numbers n ≡ 4 (mod 6) except 4 (see \underline{A016957}) appear exactly in two distinct CS. For example, 64 ≡ 4 (mod 6) shows up in all CS starting at any vertex which descends from the bifurcation at 64, e.g., 21, 128; 42, 256; 84, 85, 512; etc. The CS starting with 512 and ending in 64 corresponds to the same CW ddd as the CS starting with 84 and ending in 64.

3 Solution of a certain linear inhomogeneous Diophantine equation

For the derivation of the recurrence relations for the start and end numbers M and N of Collatz sequences (CS) with prescribed up-down pattern (realizing a given CW) we need the general solution of the following linear and inhomogeneous Diophantine equation.

D(m, n; c) :  3^{m}x − 2^{n}y = c(m, n), m ∈ ℕ_{0}, n ∈ ℕ_{0}, c(m, n) ∈ ℤ . (2)

It is well known (e.g., Niven et al. [6, pp. 212–214]) how to solve the equation ax+by = c for integers a, b (not 0) and c provided g = gcd(a, b) divides c for integers x and y; otherwise

Figure 1: The Collatz Tree CT_{7}

there is no solution. One finds a sequence of solutions parameterized by t ∈ ℤ. Then one has to restrict the t range to obtain all positive solutions. The procedure is to first find a special solution (x_{0}, y_{0}) of the equation with c = g. Then the general solution is (x = \frac{c}{g}x_{0} + \frac{b}{g}t, y = \frac{c}{g}y_{0} − \frac{a}{g}t) with t ∈ Z. The proof is found in [6]. For our problem g = gcd(3^{m}, 2^{n}) = 1 for non-negative m, n, and this g divides any c(m, n).

Lemma 1. Solution of D(m, n; c)

(a) A special positive integer solution of D(m, n; 1) is

y_{0}(m, n) = (\frac{3^{m} + 1}{2})^{n+3^{m−1}} (mod 3^{m}) ,
x_{0}(m, n) = \frac{1 + 2^{n}y_{0}(m, n)}{3^{m}} .  (3)

(b) The general solution with positive x and y is

x(m, n) = c(m, n)x_{0}(m, n) + 2^{n}t_{min}(m, n; sgn(c)) + 2^{n}k ,
y_{0}(m, n) = c(m, n)y_{0}(m, n) + 3^{m}t_{min}(m, n; sgn(c)) + 3^{m}k ,  (4)

with k ∈ ℕ_{0}, and

t_{min}(m, n; sgn(c)) = \begin{cases}⌈| c(m, n) |\frac{x_{0}(m,n)}{2^{n}}⌉ , & if c < 0; \\ ⌈−c(m, n)\frac{y_{0}(m,n)}{3^{m}}⌉ , & if c ≥ 0. \end{cases}  (5)

For the proof we use the following lemma:

Lemma 2. A(n, m) := \binom{n−1}{m−1} \frac{gcd(m,n)}{m} is a positive integer for m = 1, 2, …, n, n ∈ ℕ.

Proof. (due to Peter Bala, see \underline{A107711}, history, February 28 2014)

This is the triangle \underline{A107711} with A(0,0) =1. By a rearrangement of factors one also has A(n, m) = \binom{n}{m} \frac{gcd(n,m)}{n}. Use gcd(n, m) lcm(m, n) = nm (e.g., [2, Theorem 2.2.2, pp. 15–16], where the uniqueness of the lcm is also shown). Now

A(n, m) = \frac{a(n, m)}{lcm(n, m)}

with

a(n, m) = \binom{n}{m}m,

a positive integer because the binomial is a combinatorial number. Now m|a(n, m) and n|a(n, m) because

a(n, m) = n\binom{n − 1}{m − 1}

by a rearrangement. Hence a(n, m) = k_{1}m = k_{2}n, i.e., a(n, m) is a common multiple of n and m (call it cm(n, m)). Now lcm(n, m)|a(n, m) because lcm(n, m) is the (unique) lowest cm(n, m). Therefore \frac{a(n,m)}{lcm(n,m)} ∈ ℕ, since only natural numbers are in the game.

Now to the proof of Lemma 1.

Proof. (a) x_{0}(m, n) = \frac{1+2^{n}y_{0}(m,n)}{3^{m}} is a solution of D(m, n; 1) for any y_{0}(m, n). The given y_{0}(m, n) is a positive integer ∈ {1, 2, …, 3^{m} − 1} m ∈ ℕ and y_{0}(0, n) = 1 for n ∈ ℕ_{0}. One has to prove that x_{0}(m, n) is a positive integer. This can be done by showing that 1 + 3^{n}y_{0}(n, m) ≡ 0 (mod 3^{m}) for m ∈ ℕ. One first observes that \frac{3^{m}+1}{2} ≡ \frac{1}{2} (mod 3^{m}), because obviously 2\frac{3^{m}+1}{2} ≡ 1 (mod 3^{m}) (2 is a unit in the ring ℤ_{3^{m}}). For m = 0 one has x_{0}(0, n) = 1 + 2^{n}, n ∈ ℕ_{0}, which is positive. In the following m ∈ ℕ.

1 + 2^{n} (\frac{3^{m} + 1}{2})^{n+3^{m−1}} ≡ 1 + 2^{n} (\frac{1}{2})^{n+3^{m−1}} ≡ 1 + (\frac{1}{2})^{3^{m−1}} (mod 3^{m}) .  (6)

Now we show that L(m) := (\frac{3^{m}+1}{2})^{3^{m−1}} ≡ 0 (mod 3^{m}) by using \frac{3^{m}+1}{2} = 3k(m) − 1 with k(m) := \frac{3^{m−1}+1}{2}, a positive integer. The binomial theorem leads with a(m) = 3^{m−1} to

(3k(m) − 1)^{a(m)} = ∑_{j=0}^{a(m)−1} \binom{a(m)}{j}(−1)^{j}(3k(m))^{a(m)−j}
= 3^{m}Σ_{1}(m) + Σ_{2}(m), with  (7)
Σ_{1}(m) = ∑_{j=0}^{a(m)−m}(−1)^{j}\binom{a(m)}{j}k(m)^{a(m)−j}3^{a(m)−m−j}, and  (8)

Σ_{2}(m) = ∑_{j=a(m)−m+1}^{a(m)−1}(−1)^{j}\binom{a(m)}{j}(3k(m))^{a(m)−j} .  (9)

Now Σ_{1}(m) is an integer because of a(m) − j ≥ a(m) − m − j ≥ 0 and the integer binomial, hence L(m) ≡ Σ_{2} (mod 3^{m}). Rewriting Σ_{2} with j′ = j − a(m) + m − 1, and also using the symmetry of the binomial, one has

Σ_{2}(m) = ∑_{j=0}^{m−2} \binom{a(m)}{j}(−1)^{j−m}(3k(m))^{m−1−j}

= ∑_{j=1}^{m−1}(−1)^{j+1}\binom{a(m)}{j}(3k(m))^{j} = 3^{m}Σ̂_{2}(m) with  (10)

Σ̂_{2}(m) = ∑_{j=1}^{m−1}(−1)^{1+j}\binom{a(m)}{j}k(m)^{j}3^{j−m}

= ∑_{j=1}^{m−1}(−1)^{1+j}k(m)^{j}\binom{a(m) − 1}{j − 1}\frac{1}{j}3^{j−1} .  (11)

In the last step a rearrangement of the binomial has been applied, remembering that a(m) = 3^{m−1}. It remains to be shown that A_{m,j} := 3^{j−1}\binom{3^{m−1}−1}{j−1} \frac{1}{j} is a (positive) integer for j = 1, 2, …, m−1. Here Lemma 2 comes to help. Consider there A(3^{m−1}, j) for j = 1, 2, …, m−1 (m = 0 has been treated separately above), which is a positive integer. If 3 ∤ j then 3^{j−1}A(3^{m−1}j) = A_{m,j}, hence a positive integer. If j = 3^{k}J, with k ∈ ℕ the largest power of 3 dividing j then gcd(3, J) = 1, and j = 3^{k}J ≤ m − 1 < 3^{m−1} and gcd(3^{m−1}3^{k}J) = 3^{q} with q = min(k, m − 1).

Proof. (b) The general integer solution of Eq. (2) is then (see [6, pp. 212–214]; note that there b > 0, here b < 0, and we have changed t ↦ −t)

x = x̂(m, n; t) = c(m, n)x_{0}(m, n) + 2^{n}t,
y = ŷ(m, n; t) = c(m, n)y_{0}(m, n) + 3^{m}t, t ∈ ℤ.  (12)

In order to find all positive solutions for x and y one has to restrict the range of t, depending on sgn c. If c(m, n) ≥ 0 then, because x_{0} and y_{0} are positive and

\frac{x_{0}(m, n)}{2^{n}} = \frac{y_{0}(m, n)}{3^{m}} + \frac{1}{2^{n}3^{m}} ,

we have t > −\frac{c(m,n)x_{0}(m,n)}{2^{n}} and t > −\frac{c(m,n)y_{0}(m,n)}{3^{m}}, i.e.,

t ≥ ⌈max (−\frac{c(m, n)x_{0}(m, n)}{2^{n}}, −\frac{c(m, n)y_{0}(m, n)}{3^{m}})⌉

= ⌈−c(m, n) min (\frac{x_{0}(m, n)}{2^{n}}, \frac{y_{0}(m, n)}{3^{m}})⌉

= ⌈−c(m, n)\frac{y_{0}(m, n)}{3^{m}}⌉

= t_{min}(m, n; +).

If c(m, n) < 0 then

t ≥ ⌈| c(m, n) | max (\frac{x_{0}(m, n)}{2^{n}}, \frac{y_{0}(m, n)}{3^{m}})⌉

= ⌈| c(m, n) |\frac{x_{0}(m, n)}{2^{n}}⌉

= t_{min}(m, n; −).

Thus with t = t_{min}(m, n; sgn(c)) + k, with k ∈ ℕ_{0} one has the desired result. Note that (x_{0}(m, n), y_{0}(m, n)) is the smallest positive solution of the equation D(m, n; 1), Eq. (2), because, for c(m, n) = 1, t_{min}(m, n; +) = ⌈−\frac{y_{0}(m,n)}{3^{m}}⌉, but with y_{0}(m, n) ∈ \{1, 2, …, 3^{m} − 1\} this is 0.

A proposition on the periodicity of the solution y_{0}(m, n) follows.

Proposition 3. Periodicity of y_{0}(m, n) in n

(a) The sequence y_{0}(m, n) is periodic in n with primitive period length L_{0} = φ(3^{m}), for m ∈ ℕ_{0} with Euler’s totient function φ(n) =\underline{A000010}(n), where φ(1) := 1.

(b) The sequence x_{0}(m, n = L_{0}(m)) = q(m)x_{0}(m, n)−r(m), m ∈ ℕ_{0}, with q(m) := 2^{φ(3^{m})} and r(m) := \frac{2^{φ(3^{m})}−1}{3^{m}}. See \underline{A152007}.

(c) The set Y_{0}(m) := {y_{0}(m, n)|n = 0, 1, …, φ(3^{m})−1}, is, for m ∈ ℕ_{0}, a representation of the set RRS(3^{m}), the smallest positive restricted residue system modulo 3^{m}. See Apostol [1, p. 113] for the definition. The multiplicative group modulo 3^{m}, called ℤ_{3^{m}}^{×} = (ℤ/3^{m}ℤ)^{×} is congruent to the cyclic group C_{φ(3^{m})}.

Proof. (a) By Euler’s theorem (e.g., [2, Theorem 2.4.4.3, p. 32 ]) a^{φ(n)} ≡ 1 (mod n), provided gcd(a, n) = 1. Now gcd (\frac{3^{m}+1}{2}, 3^{m}) = gcd (\frac{3^{m}+1}{2}, 3) = 1 because \frac{3^{m}+1}{2} ≡ \frac{1}{2} (mod 3^{m}) (see above), and hence \frac{3^{m}+1}{2} ≢ 0 (mod 3^{m}). This shows that L_{0}(m) is a period length, but we have to show that it is in fact the length of the primitive period, i.e., we have to prove that the order of \frac{3^{m}+1}{2} modulo 3^{m} is L_{0}(m). (See e.g., [2, Definition 2.4.4.1, p. 31], for the order definition.) In other words we want to show that \frac{3^{m}+1}{2} is a primitive root (of 1) modulo 3^{m}. Assume that k(m) is this order (the existence is certain due to Euler’s theorem). Hence (\frac{1}{2})^{k(m)} ≡ 1 (mod 3^{m}) and k(m)|L_{0}(m). It is known that the modulus 3^{m} possesses primitive roots, and the theorem on the primitive roots says that there are precisely φ(φ(3^{m})) incongruent ones (e.g., Niven et al. [6, pp. 205, 207], or Nagell [5, Theorem 62.3, p. 104 and Theorem 65, p. 107]). In our case this number is φ(2 · 3^{m−1}) = 2 · 3^{m−2} if m ≥ 1. The important point, proven in Nagel [5, Theorem 65.3, p. 107], is that if we have a primitive root r modulo an odd prime, here 3, then, if r^{3−1} − 1 is not divisible by 3^{2}, it follows that r is in fact a primitive root for any modulus 3^{q}, with q ∈ ℕ_{0}. One of the primitive roots modulo 3 is 2, because 2^{2} = 4 ≡ 1 (mod 3) and 2^{1} ≢ 1 (mod 3). Also 2^{3−1} − 1 = 3 is not divisible by 3^{2}, hence 2 is a primitive root of any modulus 3^{q} for q ∈ ℕ_{0}. From this we proof that \frac{3^{m}+1}{2} ≡ \frac{1}{2} (mod 3^{m}) is a primitive root modulo 3^{m}. Consider (\frac{3^{m}+1}{2})^{k} ≡ \frac{1}{2^{k}} (mod 3^{m}) for k = 1, 2, …, φ(3^{m}). In order to have (\frac{1}{2})^{k} ≡ 1 (mod 3^{m}) one needs 2^{k} ≡ 1 (mod 3^{m}). But due to Nagel [5, Theorem 65.3, p. 107 ], for p = 3, a primitive root modulo 3^{m} is 2, and the smallest positive k is therefore φ(3^{m}), and hence \frac{3^{m}+1}{2} is a primitive root (of 1) of modulus 3^{m}.

(b) x_{0}(m, n + φ(3^{m})) = \frac{1+2^{n}2^{φ(3^{m})}y_{0}(m,n)}{3^{m}} from the periodicity of y_{0}. Rewritten, this is

\frac{2^{φ(3^{m})} ((2^{−φ(3^{m})} − 1) + (1 + 2^{n} y_{0}(m, n))}{3^{m}} = −\frac{1}{3^{m}} (2^{φ(3^{m})} − 1) + 2^{φ(3^{m})}x_{0}(m, n)
= q(m)x_{0}(m, n) − r(m)

with the values given in the proposition.

(c) This follows from the reduced residue system modulo 3^{m} for m ∈ ℕ_{0},

\{(\frac{1}{2})^{0} , (\frac{1}{2})^{1} , …, (\frac{1}{2})^{φ(3^{m})−1}\} ,

because \frac{1}{2} is a primitive root modulo 3^{m} (from part b)). With a(m) := \frac{3^{m}+1}{2} one has 1 = gcd(a(m), 3) = gcd(a(m), 3^{m}) = gcd(a(m)^{b(m)}3^{m}) with b(m) := 3^{m−1}, and

\{a(m)^{b(m)} (\frac{1}{2})^{0} , a(m)^{b(m)} (\frac{1}{2})^{1} , …, a(m)^{b(m)} (\frac{1}{2})^{φ(3^{m})−1}\}

is a reduced residue system modulo 3^{m} (see Apostol [1, Theorem 5.16, p. 113]). Thus

Y_{0}(m) ≡ {a(m)^{b(m)}1, a(m)^{b(m)+1}, …, a(m)^{b(m)+φ(3^{m})−1}}

is a reduced residue system modulo 3^{m}. Therefore this gives a permutation of the reduced residue system modulo 3^{m} with the smallest positive integers sorted increasingly.

Example 4. For m = 3, φ(3^{3}) = 2 · 3^{2} = 18 = L_{0}(3), and

{y_{0}(3, n)}_{n=0}^{17} = {26, 13, 20, 10, 5, 16, 8, 4, 2, 1, 14, 7, 17, 22, 11, 19, 23, 25}

is a permutation of the standard reduced residue system modulo 27, obtained by re-sorting the found system in increasing order. See \underline{A239125}. For m = 1, 2, and 4 see \underline{A007583}, \underline{A234038} and \underline{A239130} for the solutions (x_{0}(m, n), y_{0}(m, n)).

4 Recurrences and their solution

After these preparations it is straightforward to derive the recurrence for the start and end numbers M and N for any given CW (n⃗_{S}), for S ∈ ℕ.

(A) We first consider the case of words with n_{S} = 1, i.e., n⃗_{S} = [n_{0}, n_{1}, …, n_{S−1}, 1]. This is the word CW (n⃗_{S}) = ∏ → _{j=0}^{S−1}d^{n_{j}}s (with an ordered product, beginning with j = 0 at the left-hand side). In order to simplify the notation we use M(S), N(S), y_{0}(S), x_{0}(S), and c(S) for M(n⃗_{S}), N(n⃗_{S}) , y_{0}(S, n_{S}), x_{0}(S, n_{S}) and c(S, n_{S}), respectively. For S = 1, the input for the recurrence, one has

M(1; k) = 2^{n_{0}}(2 k + 1) and N(1; k) = 3k + 2, for k ∈ ℕ ,  (13)

because there are n_{0} factors of 2 from d^{n_{0}}, and then an odd number 2k + 1 leads after application of s to 3k + 2. Thus M(1) = 2^{n_{0}} and N(1) = 2.

Proposition 5. Recurrences for M(S) and N(S) with n_{S} = 1.

(a) The coupled recurrences for M(S, t) and N(S, t), the first and last entry of the Collatz sequences CS(n⃗_{S}; t) for the word CW (n⃗_{S}) with n⃗_{S} = [n_{0}, n_{1}, …, n_{S−1}, 1] (n_{S} = 1) are

M(S, t) = M(S) + 2^{D̂(S)}t,
N(S, t) = N(S) + 3^{S}t, with t ∈ ℤ ,  (14)

where D̂(S) := ∑_{j=0}^{S−1} n_{j} (we prefer to use a new symbol for the n_{S} = 1 case), and the recurrences for M(S) and Ñ(S) = N(S) − 2 are

M(S) = M(S − 1) + 2^{D̂(S−1)}c(S − 1)x_{0}(S − 1) ,
Ñ(S) = 3y_{0}(S − 1)c(S − 1),  (15)

with

c(S − 1) = 2(2^{n_{S−1}−2} − 1) − Ñ(S − 1) =: A(S − 1) − Ñ(S − 1) .  (16)

The recurrence for c(S) is

c(S) = −3y_{0}(S − 1)c(S − 1) + A(S), S ≥ 2,  (17)

and the input is M(1) = 2^{n_{0}}, Ñ(1) = 0 and c(1) = A(1).

(b) The general positive integer solution is

M(S; k) = M(S) + 2^{D̂(S)}t_{min}(S − 1) + 2^{D̂(S)}k,
N(S; k) = 2 + Ñ(S) + 3^{S}t_{min}(S − 1) + 3^{S}k, k ∈ ℕ_{0},  (18)

where

t_{min}(S) = t_{min}(S, n_{S}, sgn(c(S))) = \begin{cases}⌈| c(S) |\frac{x_{0}(S)}{2^{n_{S}}}⌉ , & if c(S) < 0; \\ ⌈−c(S)\frac{y_{0}(S)}{3^{S}}⌉ , & if c(S) ≥ 0. \end{cases}  (19)

Corollary 6.

M(S; k) ≡ M(S) + 2^{D̂(S)}t_{min}(S − 1) (mod 2^{D̂(S)}),
N(S; k) ≡ Ñ(S) + 3^{S}t_{min}(S − 1) (mod 3^{S}).  (20)

In Terras’ article [8] the first congruence corresponds to Theorem 1.2, where the encoding vector E_{k}(n) refers to the modified Collatz tree using only d and s operations.

Proof. (a) By induction over S. For S = 1 the input M(1) = 2^{n_{0}}, N(1) = 2 or Ñ(1) = 0 provides the start of the induction. Assume that part (a) of the proposition is true for S values 1, 2, …, S − 1. To find M(S) one has to make sure that d^{n_{S−1}}s can be applied to N(S − 1; k), the end number of step S − 1 sequence CS(n⃗_{S−1}; t) which is N_{int}(S − 1, t) = N(S − 1) + 3^{S−1}t, with integer t, by the induction hypothesis. This number has to be of the form 2^{n_{S−1}−1}(2m + 1) (one has to have an odd number after n_{S−1} d−steps such that s can be applied). Thus 3^{S−1}t − 2^{n_{S−1}}m = 2^{n_{S−1}−1} − N(S − 1) = A(S − 1) − Ñ(S − 1) =: c(S − 1), where Ñ(S − 1) = N(S − 1) − 2 and A(S − 1) = 2(2^{n_{S−1}−2} − 1). Due to Lemma 1 the general solution, with t → x(S − 1, n_{S−1}; t) ˆ=x(S − 1; t), m → y(S − 1, n_{S−1}; t) ˆ=y(S − 1; t), to shorten the notation, is

t → x(S; t) = c(S − 1)x_{0}(S − 1) + 2^{n_{S−1}}t,
m → y(S; t) = c(S − 1)y_{0}(S − 1) + 3^{S−1}t, t ∈ ℤ .  (21)

Therefore the first entry of the sequence CS(n⃗_{S}; t) is M(S; t) = M(s − 1, x(S − 1, t)) which is

M_{int}(S; t) = M(S − 1) + 2^{D̂(S−1)}c(S − 1)x_{0}(S − 1) + 2^{D̂(S)}t,  (22)

hence M(S) = M(S − 1) + 2^{D̂(S−1)}c(S − 1)x_{0}(S − 1), the claimed recurrence for M(S).

The last member of CS(n⃗_{S−1}; t) is 3m + 2 (after applying s on 2m + 1 from above). Thus N_{int}(S; t) = 3y(S; t) + 2, or N_{int}(S; t) − 2 = 3c(S − 1)y_{0}(S − 1) + 3^{S}t. Therefore, Ñ(S) = N(S) − 2 = 3c(S − 1)y_{0}(S − 1) which is the claim for the Ñ recurrence. Note that the remainder structure of eqs. 18, expressed also in the Corollary 6, has also been verified by this inductive proof. The recurrence for c(S) = A(S) − Ñ(S) follows from the one for Ñ(S).

(b) Positive integer solutions from M_{int}(S; t) and N_{int}(S; t) of part (a) are found from the second part of Lemma 1 applied to the equation 3^{S−1}x − 2^{n_{S−1}}y = c(S − 1), determining t_{min}(S − 1) as claimed. This leads finally to the formulae for M(S; k) and N(S; k) with k ∈ ℕ_{0}.

Example 7. (sd)^{S−1}s Collatz sequences

Here n_{0} = 0 = n_{S} and n_{j} = 2 for j = 1, 2, …, S − 1. The first entries M(S; k) and the last entries N(S; k) of the Collatz sequence CS([0, 2, …, 2]; k) (with S − 1 times a 2), whose length is 3S, are M(S; k) = 1 + 2^{2S−1}k and N(S; k) = 2 + 3^{S}k. For S = 3 a complete Collatz sequence CS([0, 2, 2]; 3) of length 9 is [97, 292, 146, 73, 220, 110, 55, 166, 83] which is a special realization of the word sdsds with starting number M(3; 3) = 97 ending in N(3; 3) = 83. Note that for this u − d pattern the start and end numbers have remainders M(S; 0) = M(1; 0) = 1 and N(S; 0) = N(1; 0) = 2. See the tables \underline{A240222} and \underline{A240223}.

The recurrences for M(S) ˆ=M(n⃗_{S−1}), Ñ(S) ˆ=Ñ(n⃗_{S−1}) or N(S) ˆ=N(n⃗_{S−1}) and c(S) ˆ= c(n⃗_{S−1}) are solved by iteration with the given inputs M(1) = 2^{n_{0}}, Ñ(1) = 0 and c(1) = A(1) = 2(2^{n_{0}−2} − 1).

Proposition 8. Solution of the recurrences for n_{s} = 1 The solution of the recurrences of Proposition 5 with the given inputs are, for S ∈ ℕ:

c(S) = A(S) + ∑_{j=1}^{S−1}(−3)^{j}A(S − j) ∏_{l=1}^{j} y_{0}(S − l),

ñ(S) = A(S) − c(S) = − ∑_{j=1}^{S−1}(−1)^{j}A(S − j) ∏_{l=1}^{j} y_{0}(S − l),
N(s) = Ñ(S) + 2,
M(S) = 2^{n_{0}} + ∑_{j=1}^{S−1} R(S − j),  (23)

with D̂(S) := 1+∑_{j=0}^{S−1} n_{j}, A(S) := 2(2^{n_{S}−2}−1), R(S) := 2^{D̂(S)}x_{0}(S)c(S), and y_{0}(S) ˆ=y_{0}(S, n_{S}), x_{0}(S) ˆ=x_{0}(S, n_{S}), given in Lemma 1.

Proof. This is obvious.

(B) The general case n_{S} = 1 can now be found by appending the operation d^{n_{S}−1} to the above result. This leads to the following theorem.

Theorem 9. The general case n⃗_{S}.

For the Collatz word CW (n⃗_{S}) = d^{n_{0}} ∏ → _{j=1}^{S}(sd^{n_{j}−1}) = d^{n_{0}}s ∏ → _{j=1}^{S}(d^{n_{j}−1}s)d^{n_{S}−1} (the ordered product begins with j = 1 on the left-hand side) with n_{0} ∈ ℕ_{0} , n ∈ ℕ, the first and last entries of the corresponding Collatz sequences {CS(n⃗_{S}; k)}, of length L(S) = n_{0} +2 ∑_{j=1}^{S} n_{j}, for k ∈ ℕ_{0}, are

M(n⃗_{S}; k) = M(S) − 2^{D̂(S)}N(S)x_{0}(S, n_{S} − 1) + 2^{D(S)}t_{min}(S, n_{S} − 1, sgn(c_{new}(S))
+2^{D(S)}k,
N(n⃗_{S}; k) = c_{new}(S)y_{0}(S, n_{S} − 1) + 3^{S}t_{min}(S, n_{S} − 1, sgn(c_{new}(S)) + 3^{S}k,  (24)

with c_{new}(S) := −N(S), D̂(S) = 1 + ∑_{j=0}^{S−1} n_{j}, D(S) = ∑_{j=0}^{S} n_{j}.

Proof. In order to be able to apply to the Collatz sequences CS([n_{0}, n_{1}, …, n_{S} − 1, 1]) (with the results from part (A) above) the final d^{n_{S}−1} operation one needs for the last entries N_{int}(S; t) = N(S)+3^{S}t = 2^{n_{S}−1}m with some (even or odd) integer m. The new last entries of CS([n_{0}, n_{1}, …, n_{S}]; t) are then m. The general solution of 3^{S} −2^{n_{S}−1}m = −N(S) =: c_{new}(S) is, according to Lemma 1, given by

t → x(S; t) = c_{new}(S)x_{0}(S, n_{S} − 1) + 2^{n_{S}−1}t,
m → y(S; t) = c_{new}(S)y_{0}(S, n_{S} − 1) + 3^{S}t, t ∈ ℤ.  (25)

This leads to positive integer solutions after the shift t → t_{min} + k, with t_{min} = t_{min}(S, n_{S} − 1, sgn(c_{new}(S))) to the claimed result N(S; k) for the new last number of CS(n⃗; k), with k ∈ ℕ_{0}. The new start value M(S; k) is obtained by replacing t → x(S; t) in the old M_{int}(S; t) (with n_{S} = 1). M(S; k) = M_{int}(S, x(S; t)) with t → t_{min} + k, also leading to the claimed formula.

The remainder structure modulo 2^{D(S)} for M(n⃗_{S}, k) and modulo 3^{S} for N(n⃗_{S}, k) is manifest.

The explicit sum versions of the results for case n_{S} = 1, given in Proposition 9, can be inserted here.

Example 10. ud^{m} = sd^{m−1} For m = 1, 2, 3 and k = 0, 1, …, 10 one finds for N([0, m], k):

[2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32],
[1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31],
[2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32],

and for M([0, m], k):

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21],
[1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41],
[5, 13, 21, 29, 37, 45, 53, 61, 69, 77, 85].

Only the odd members of N([0, m], k), that is, the odd-indexed entries, and the corresponding M([0, m], k) appear in the article of Trümper [9] as Example 2.1. See \underline{A238475} for M([0, 2n], k) and \underline{A238476} for M([0, 2n − 1], k). The odd N([0, 2n], k) values are the same for all n, namely 5 + 6k, and N([0, 2n − 1], k) = 1 + 6k for all n ∈ ℕ.

Example 11. (ud)^{n} = s^{S}, S ∈ ℕ

n⃗_{S} = [0, 1, …, 1] with S times a 1. For S = 1, 2, 3 and k = 0, 1, …, 10 one finds for N(n⃗_{S}, k):

[5, 8, 11, 14, 17, 20, 23, 26, 29, 32],
[17, 26, 35, 44, 53, 62, 71, 80, 89, 98],
[53, 80, 107, 134, 161, 188, 215, 242, 269, 296],

and for M(n⃗_{S}, k):

[3, 5, 7, 9, 11, 13, 15, 17, 19, 21],
[7, 11, 15, 19, 23, 27, 31, 35, 39, 43],
[15, 23, 31, 39, 47, 55, 63, 71, 79, 87].

For odd N entries, and corresponding M entries this is in the article of Trümper [9, Example 2.1].

See \underline{A239126} for these M values, and \underline{A239127} for these N values, which are here S dependent.

In conclusion the author does not think that the knowledge of all Collatz sequences with a given up-down pattern (a given Collatz word) helps to prove the Collatz conjecture. Nevertheless the problem considered in this paper is a nice application of the solution of a simple Diophantine equation.

5 Acknowledgment

Thanks go to Peter Bala who answered the author’s question for a proof that all triangle \underline{A107711} entries are non-negative integers. See the history there, dated February 28 2014.

6 Note added

The referee commented that “... the line of reasoning of the author shows resemblance with the derivation of cycles for the general Collatz problem (T (n) = \frac{pn+q}{2} if n is odd) based on Lyndon words [3] and the extra equality x = y” (in the present work x = M and y = N).

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.

[2] B. Fine and G. Rosenberger, Number Theory, Birkhäuser, 2007.

[3] T. Laarhoven and B. de Weger, The Collatz conjecture and De Bruijn graphs, Indag. Math. (N.S.) 24 (2013) 971–983. Preprint available at

   http://arxiv.org/abs/1209.3495.

[4] J. Lagarias, The 3x + 1 problem and its generalization, Amer. Math. Monthly 92 (1985), 3–23.

[5] T. Nagell, Introduction to Number Theory, Chelsea Publishing Company, 1964.

[6] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., 1991.

[7] The On-Line Encyclopedia of Integer Sequences (2010), published electronically at

   http://oeis.org.

[8] R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241–252.

[9] M. Trümper, The Collatz problem in the light of an infinite free semigroup, Chinese J. Mathematics, 2014 (2014), Article ID 756917,

   http://www.hindawi.com/journals/cjm/aip/756917/.

2010 Mathematics Subject Classification: Primary 11D04; Secondary 32H50. Keywords: Collatz problem, Collatz sequences, Collatz tree, recurrence, iteration, linear Diophantine equation.

(Concerned with sequences \underline{A000010}, \underline{A005186}, \underline{A007583}, \underline{A016957}, \underline{A107711}, \underline{A127824}, \underline{A152007}, \underline{A176866}, \underline{A234038}, \underline{A238475}, \underline{A238476}, \underline{A239125}, \underline{A239126}, \underline{A239127}, \underline{A239130}, \underline{A240222}, and \underline{A240223}.)

Received April 10 2014; revised versions received October 2 2014; November 5 2014; November 11 2014. Published in Journal of Integer Sequences, December 12 2014.

Return to Journal of Integer Sequences home page.