5.2 Base 3/2 Number System
5.2.1 The Number System in Rational Base \(3/2\)
The following definitions and results formalise portions of the paper by Eliahou and Verger-Gaugry [ 2 ] , which studies the representation of natural numbers in the rational base \(3/2\) and its connections to the Collatz problem. Every natural number \(n\) admits a unique representation
and the digits \(a_i\) can be extracted by repeated division of \(2n\) by \(3\).
The least-significant digit of \(n\) in rational base \(3/2\) is
This is the digit \(a_0\) of Proposition 2.2 of [ 2 ] .
The parent of \(n\) in the base-\(3/2\) digit tree is
Removing the least-significant digit from \(\langle n \rangle \) gives \(\langle \operatorname {parent}(n) \rangle \).
For all \(n \in \mathbb {N}\),
This is the division algorithm applied to \(2n\) divided by \(3\).
For all \(n \in \mathbb {N}\), \(\operatorname {lsd}(n) {\lt} 3\).
By the definition of the remainder modulo \(3\).
For all \(n \ge 1\), \(\operatorname {parent}(n) {\lt} n\).
We have \(\operatorname {parent}(n) = \lfloor 2n/3 \rfloor \le 2n/3 {\lt} n\) whenever \(n \ge 1\).
For all \(n \in \mathbb {N}\),
This is part of Proposition 2.2 of [ 2 ] .
From \(2n = 3 \cdot \operatorname {parent}(n) + \operatorname {lsd}(n)\), reducing modulo \(2\) gives \(0 \equiv \operatorname {parent}(n) + \operatorname {lsd}(n) \pmod{2}\).
The base-\(3/2\) representation of \(n\), written \(\langle n \rangle \), is the list of digits (least-significant first) defined recursively:
Termination is guaranteed by Lemma 175.
Every digit in \(\operatorname {digits}_{3/2}(n)\) is less than \(3\).
By strong induction on \(n\). If \(n = 0\) the digit list is empty. Otherwise the first digit is \(\operatorname {lsd}(n) {\lt} 3\) (Lemma 174), and the remaining digits belong to \(\operatorname {digits}_{3/2}(\operatorname {parent}(n))\), which satisfy the bound by the induction hypothesis (since \(\operatorname {parent}(n) {\lt} n\)).
\(|\operatorname {digits}_{3/2}(n)| = 0\) if and only if \(n = 0\).
If \(n = 0\) the list is empty. Conversely, if \(n \ge 1\) the list has the form \(\operatorname {lsd}(n) :: (\cdots )\), whose length is at least \(1\).
The evaluation of a list of base-\(3/2\) digits (least-significant first) is
For admissible digit lists (those produced by \(\operatorname {digits}_{3/2}\)), the division is always exact.
For all \(n \in \mathbb {N}\),
By strong induction on \(n\). For \(n = 0\) both sides are \(0\). For \(n \ge 1\):
where the division is exact since \(\operatorname {lsd}(n) + 3 \cdot \operatorname {parent}(n) = 2n\).
The function \(U : \mathbb {N} \to \mathbb {N}\) (Notation 3.7 of [ 2 ] ) is defined by
Equivalently, \(U(n) = (3n + 2 - (n \bmod 2))/2\).
When \(n\) is odd, \(U(n) = T(n)\).
Both evaluate to \((3n + 1)/2\).
For all \(n \in \mathbb {N}\),
This is Remark 3.8 of [ 2 ] .
Split into cases according to the parity of \(n\) and verify by direct computation:
If \(n = 2k\), then \(U(n) = 3k+1\) and \(T(n) = k\), so \(U(n) \bmod 2 = (k+1) \bmod 2 = (k + 2k + 1) \bmod 2 = (T(n) + n + 1) \bmod 2\).
If \(n = 2k+1\), then \(U(n) = 3k+2\) and \(T(n) = 3k+2\), and again both sides match modulo \(2\).
For all \(n \in \mathbb {N}\),
This is Proposition 3.9 of [ 2 ] .
Split by parity of \(n\) and verify the integer arithmetic:
If \(n\) is even: \(U(n) = (3n+2)/2\), so \(\operatorname {parent}(U(n)) = \lfloor 2 \cdot (3n+2)/2 \, /\, 3 \rfloor = \lfloor (3n+2)/3 \rfloor = n\).
If \(n\) is odd: \(U(n) = (3n+1)/2\), so \(\operatorname {parent}(U(n)) = \lfloor (3n+1)/3 \rfloor = n\).
When \(n\) is odd, \(\operatorname {lsd}(U(n)) = 1\).
\(U(n) = (3n+1)/2\), so \(\operatorname {lsd}(U(n)) = (2 \cdot (3n+1)/2) \bmod 3 = (3n+1) \bmod 3 = 1\).
When \(n\) is even, \(\operatorname {lsd}(U(n)) = 2\).
\(U(n) = (3n+2)/2\), so \(\operatorname {lsd}(U(n)) = (3n+2) \bmod 3 = 2\).
For all \(n \in \mathbb {N}\), \(U(n) \ge 1\).
In both cases \((3n+2)/2 \ge 1\) and \((3n+1)/2 \ge 1\).
For all \(n \in \mathbb {N}\), the base-\(3/2\) digits of \(U(n)\) are obtained by prepending \(1\) (if \(n\) is odd) or \(2\) (if \(n\) is even) to \(\langle n \rangle \):
This is Proposition 3.9 of [ 2 ] (combined form).
Since \(U(n) \ge 1\) (Lemma 188), we can unfold the recursive definition to get \(\langle U(n) \rangle = \operatorname {lsd}(U(n)) :: \langle \operatorname {parent}(U(n)) \rangle \). By Lemma 185, \(\operatorname {parent}(U(n)) = n\). The digit is \(1\) when \(n\) is odd (Lemma 186) and \(2\) when \(n\) is even (Lemma 187).
For odd \(n\) (Corollary 3.2 of [ 2 ] ),
That is, the base-\(3/2\) representation of \(T(n) = (3n+1)/2\) is obtained by prepending digit \(1\) to \(\langle n \rangle \).
Since \(n\) is odd, \(T(n) = (3n+1)/2 \ge 1\). We verify that \(\operatorname {lsd}(T(n)) = 1\) and \(\operatorname {parent}(T(n)) = n\) by direct arithmetic.
For even \(n \ge 1\) (Proposition 3.1, digit \(0\)),
We verify \(\operatorname {lsd}(3n/2) = 0\) and \(\operatorname {parent}(3n/2) = n\) by the arithmetic of even \(n\): since \(n\) is even, \(3n/2\) is an integer and \(2 \cdot (3n/2) = 3n\), whose remainder modulo \(3\) is \(0\) and whose quotient by \(3\) is \(n\).
For even \(n\) (Proposition 3.1, digit \(2\)),
Since \(n\) is even, \((3n+2)/2\) is a positive integer. We verify \(\operatorname {lsd}((3n+2)/2) = 2\) and \(\operatorname {parent}((3n+2)/2) = n\) by computing \(2 \cdot (3n+2)/2 = 3n + 2\), which gives remainder \(2\) and quotient \(n\) upon division by \(3\).
If \(\operatorname {lsd}(n) = 1\), then \(\operatorname {parent}(n)\) is odd.
Since \(\operatorname {lsd}(n) \equiv \operatorname {parent}(n) \pmod{2}\) (Lemma 176) and \(\operatorname {lsd}(n) = 1\), we have \(\operatorname {parent}(n) \bmod 2 = 1\).
If \(\operatorname {lsd}(n) = 0\), then \(\operatorname {parent}(n)\) is even.
Same reasoning: \(\operatorname {lsd}(n) = 0\) and the parity congruence give \(\operatorname {parent}(n) \bmod 2 = 0\).
If \(\operatorname {lsd}(n) = 2\), then \(\operatorname {parent}(n)\) is even.
Since \(2 \bmod 2 = 0\), the parity congruence gives \(\operatorname {parent}(n) \bmod 2 = 0\).
The \(k\)-fold iteration of \(U\) is defined by \(U^0(n) = n\) and \(U^{k+1}(n) = U(U^k(n))\).
The saturated number \(\operatorname {sat}(k) = U^k(0)\) is the largest natural number whose base-\(3/2\) representation has length \(k\) (Proposition 3.10 of [ 2 ] ).
The first few values are \(\operatorname {sat}(0)=0\), \(\operatorname {sat}(1)=1\), \(\operatorname {sat}(2)=2\), \(\operatorname {sat}(3)=4\), \(\operatorname {sat}(4)=7\), \(\operatorname {sat}(5)=11\), \(\operatorname {sat}(6)=17\), \(\operatorname {sat}(7)=26\).
For \(k \ge 1\), every digit in \(\langle \operatorname {sat}(k) \rangle \) is either \(1\) or \(2\) (no digit \(0\) appears). This is Proposition 3.5 of [ 2 ] .
By induction on \(k\). For \(k = 0\) the claim is vacuously true (the list is empty). For \(k + 1\), we have \(\operatorname {sat}(k+1) = U(\operatorname {sat}(k))\), so by Lemma 189, \(\langle \operatorname {sat}(k+1) \rangle \) is \(\langle \operatorname {sat}(k) \rangle \) with either \(1\) or \(2\) prepended. The prepended digit is in \(\{ 1,2\} \) by construction, and the remaining digits are in \(\{ 1,2\} \) by the induction hypothesis (or are empty when \(k = 0\)).
For all \(k \in \mathbb {N}\) (Proposition 3.6 of [ 2 ] ),
This is a direct application of Lemma 189 to \(n = \operatorname {sat}(k)\).
The cyclic permutation \(\sigma = (2\; 1\; 0)\) on the digit set \(\{ 0,1,2\} \):
Formally, \(\sigma (d) = (d + 2) \bmod 3\).
Given a digit list (least-significant first), \(\operatorname {splitAtFirstZero}\) returns the pair \((\mathit{prefix}, \mathit{suffix})\) where \(\mathit{prefix}\) consists of all nonzero digits before the first \(0\), and \(\mathit{suffix}\) consists of the digits after the first \(0\). If no \(0\) is present, the suffix is empty.
For all \(n \ge 1\),
Direct arithmetic: \(\operatorname {lsd}(n+1) = (2(n+1)) \bmod 3 = (2n + 2) \bmod 3 = ((2n) \bmod 3 + 2) \bmod 3 = \sigma (\operatorname {lsd}(n))\).
If \(n \ge 1\) and \(\operatorname {lsd}(n) = 0\), then \(\operatorname {parent}(n+1) = \operatorname {parent}(n)\) (no carry).
When \(\operatorname {lsd}(n) = 0\), we have \(2n \equiv 0 \pmod{3}\), so \(\lfloor 2(n+1)/3 \rfloor = \lfloor (2n+2)/3 \rfloor = \lfloor 2n/3 \rfloor \) since the remainder goes from \(0\) to \(2\) without crossing \(3\).
If \(n \ge 1\) and \(\operatorname {lsd}(n) \ne 0\), then \(\operatorname {parent}(n+1) = \operatorname {parent}(n) + 1\) (carry propagates).
When \(\operatorname {lsd}(n) \in \{ 1, 2\} \), we have \(2n \bmod 3 \ge 1\), so adding \(2\) causes the quotient \(\lfloor 2n/3 \rfloor \) to increase by \(1\).
(Proposition 2.3, Odometer.) Let \(\langle n \rangle = u\, 0\, v\) where \(v \in \{ 1,2\} ^*\) (i.e. \(v\) is the block of nonzero digits before the first \(0\), reading from the least-significant end, and \(u\) is the part after the \(0\)). Then
where \(v^\sigma \) denotes the list obtained by applying \(\sigma \) to each digit of \(v\). In other words, incrementing by one applies \(\sigma \) to all leading nonzero digits (carrying), replaces the first \(0\) with \(2\), and leaves the remaining digits unchanged.
By strong induction on \(n\).
Base case (\(n = 0\)): \(\langle 0 \rangle = []\) splits trivially, and \(\langle 1 \rangle = [2]\) (since \(\operatorname {lsd}(1) = 2\) and \(\operatorname {parent}(1) = 0\)). The formula gives \([] \cdot 2 \cdot [] = [2]\).
Inductive step (\(n \ge 1\)): Write \(\langle n \rangle = \operatorname {lsd}(n) :: \langle \operatorname {parent}(n) \rangle \).
Case \(\operatorname {lsd}(n) = 0\) (no carry): The split gives prefix \(= []\) and suffix \(= \langle \operatorname {parent}(n) \rangle \). By Lemma 202, \(\operatorname {lsd}(n+1) = \sigma (0) = 2\). By Lemma 203, \(\operatorname {parent}(n+1) = \operatorname {parent}(n)\). So \(\langle n+1 \rangle = 2 :: \langle \operatorname {parent}(n) \rangle \), which matches the formula.
Case \(\operatorname {lsd}(n) \ne 0\) (carry): The split prefix is \(\operatorname {lsd}(n) :: (\text{prefix from rest})\). By Lemma 202, the first digit becomes \(\sigma (\operatorname {lsd}(n))\). By Lemma 204, \(\operatorname {parent}(n+1) = \operatorname {parent}(n) + 1\). The induction hypothesis (applied to \(\operatorname {parent}(n) {\lt} n\)) handles the remaining digits.
The scaled evaluation of a digit list \([a_0, \ldots , a_k]\) is
Recursively: \(\operatorname {scaledEval}([]) = 0\) and \(\operatorname {scaledEval}(a :: \mathit{rest}) = 2^{|\mathit{rest}|} \cdot a + 3 \cdot \operatorname {scaledEval}(\mathit{rest})\).
For all \(n \in \mathbb {N}\),
By strong induction on \(n\). For \(n = 0\), both sides are \(0\). For \(n \ge 1\), let \(L = |\operatorname {digits}_{3/2}(\operatorname {parent}(n))|\). Then \(|\operatorname {digits}_{3/2}(n)| = L + 1\) and:
(Proposition 4.5 of [ 2 ] .) Let \(n \ge 1\) with \(\langle n \rangle = a_k \cdots a_0\) having \(k+1\) digits. Then \(n\) is even if and only if
Equivalently, using the scaled evaluation:
where \(L = |\langle n \rangle |\).
By Lemma 207, \(\operatorname {scaledEval}(\langle n \rangle ) = 2^L \cdot n\), so modulo \(2^{L+1} = 2^L \cdot 2\):
The left-hand side is \(0\) if and only if \(n \bmod 2 = 0\) (since \(2^L \ge 1\), so \(2^L \cdot (n \bmod 2) = 0\) implies \(n \bmod 2 = 0\)).
The number of odd values among the first \(k\) terms of the \(U\)-orbit starting from \(n_0\) is
The \(U\)-orbit density conjecture for a fixed starting point \(n_0\) asserts that
The universal \(U\)-orbit density conjecture asserts that \(U\text{-orbit density}(n_0)\) holds for every \(n_0 \in \mathbb {N}\).
Conjecture 4.2 (Definition ??) is equivalent to the \(U\)-orbit density conjecture for \(n_0 = 0\).
Since \(\operatorname {sat}(j) = U^j(0)\), the count of odd values \(\operatorname {numOnesSat}(k)\) is exactly \(\operatorname {numOddU}(k, 0)\). The two statements are definitionally equal.