# An inverse-minimum theorem for Collatz words without consecutive twos

## Problem and contribution

Write the accelerated Collatz map on positive odd integers as

$$
U(n)=\frac{3n+1}{2^{v_2(3n+1)}}.
$$

A finite forward word of length $r\geq1$ records its positive division
exponents $a_1,\ldots,a_r$. A common-future descent certificate consists of a positive
odd $b<n$ and integers $r,s\geq0$ such that $U^r(n)=U^s(b)$. Such a
certificate permits induction on the starting value even when the observed
forward trajectory has not yet fallen below $n$.

We prove an exact minimum theorem for a class of forward words: if every
exponent is either one or two and no two consecutive exponents are two,
then $n$ is the unique smallest positive odd ancestor of $U^r(n)$ at depth
$r$. The reversed observed path is also minimal at every shorter depth.
When the word starts with one, every different ancestor at depth $r$ is at
least $2n+1$.

For an odd multiple of three whose word starts with one, we strengthen the
conclusion: a smaller ancestor of $U^r(n)$ needs at least $r+4$ odd steps.
This bound is attained on the entire class $n\equiv1275\pmod{2592}$, where

$$
U^3(n)=U^7\!\left(\frac{64n-33}{81}\right),
\qquad 0<\frac{64n-33}{81}<n.
$$

The proof compares inverse paths through an integer affine relation. Its
only boundary case uses a congruence modulo four, rather than a real-valued
inequality alone. These results justify pruning specified inverse searches;
they do not provide a cover of all positive starts or prove the Collatz
conjecture.

## Related work and distinction

Finite parity words, affine composition, inverse trees, and merging
identities are established tools; Lagarias's bibliography [1] documents
this background. Applegate and Lagarias [2] use inverse-tree searches to
bound the number of ancestors and the density of integers reaching a
specified root. The extremal quantity here is instead the smallest odd
ancestor at a specified number of accelerated steps, conditioned on a
word realized by one known ancestor.

Garner [3] studies paired parity words that make consecutive starting
integers coalesce. Cadogan's related merging results are described in [1].
Andaloro [4], Section 2, proves affine merging identities and consequences
for the least integers with a specified odd total stopping time. In
particular, his Lemmas 3 and 4 and the following remark already treat
families involving $x$ and $2x+1$, independently of eventual convergence.
We do not claim that affine merging or this pair of starts is new. Our
sharpness example combines such merging with a proof excluding *every*
smaller ancestor through three additional depths.

Monks, Monks, Monks, and Monks [5] study sufficient sets, bounded numbers
of odd inverse steps needed to reach an arithmetic progression (Theorem
4.1), and greedy back tracing (Section 5.2). Their progression theorem
does not impose a smaller-size requirement. Their greedy construction
avoids multiples of three to produce an infinite inverse path and bounds
the frequency of its odd inverse steps. Our finite comparison includes
all valid paths, including ones terminating at a multiple of three, and
proves when a locally smallest path is globally smallest at every depth
under consideration.

The specific contribution is the integer invariant in Lemma 1, its
minimum theorem uniform in word length and endpoint, and the sharp
additional-depth lower bound. The comparison with [2] and [3] uses the
detailed annotations in [1]; the full texts of [4] and [5] were consulted.
No published r/collatz papers were available at the time of this comparison.

## Inverse comparison

For $e\geq1$, an allowed inverse step is

$$
I_e(x)=\frac{2^e x-1}{3},
$$

when its value is a positive odd integer. If $x\equiv1\pmod3$, then $e$ is
even; if $x\equiv2\pmod3$, then $e$ is odd. A multiple of three has no
allowed inverse step.

Compare the reversed observed path with any other valid inverse path from
the same endpoint. After the same number of inverse steps, let $x$ be the
observed state, $y$ the alternative state, and $\delta$ the alternative
division sum minus the observed sum. When $\delta\geq0$, write

$$
y=2^\delta x+c.
$$

The quantity $c$ is then an integer. Initially $(\delta,c)=(0,0)$.
A reversed word without consecutive twos is a concatenation of blocks
$1$ and $(2,1)$, possibly followed by one final unpaired $2$.

**Lemma 1.** At the end of each complete block $1$ or $(2,1)$, every
alternative inverse path satisfies

$$
\delta\geq0,\qquad 0\leq c\leq5(2^\delta-1).
\tag{1}
$$

**Proof.** For a block $1$ with alternative exponent $b\geq1$, substitution
gives

$$
\delta'=\delta+b-1,\qquad
c'=\frac{2^{\delta'}+2^b c-1}{3}.
\tag{2}
$$

Thus $\delta'\geq0$ and $c'\geq0$. Using (1),

$$
c'\leq
\frac{11\cdot2^{\delta'}-5\cdot2^b-1}{3}
\leq5(2^{\delta'}-1),
$$

where the last inequality is
$4\cdot2^{\delta'}+5\cdot2^b\geq14$.

For a block $(2,1)$, let the alternative exponents be $b_1,b_2$ and put
$B=b_1+b_2$. Since the observed block is $(8x-5)/9$,

$$
\delta'=\delta+B-3,\qquad
c'=\frac{2^B c+5\cdot2^{\delta'}-2^{b_2}-3}{9}.
\tag{3}
$$

The division difference is nonnegative at both intermediate states.
If $\delta\geq1$, this follows from $b_1\geq1$ and $B\geq2$.
If $\delta=0$, (1) gives $c=0$, so the two current states agree. The
observed first inverse exponent is two, forcing $b_1$ to be even and at
least two. The same conclusion follows. Applying the one-step relation

$$
c_{\mathrm{new}}=
\frac{2^{\delta_{\mathrm{new}}}+2^b c_{\mathrm{old}}-1}{3}
$$

at each intermediate state also gives $c'\geq0$.

For $B\geq3$, (1) and (3) imply

$$
c'\leq5\cdot2^{\delta'}
-\frac{5\cdot2^B+2^{b_2}+3}{9}
\leq5(2^{\delta'}-1),
$$

because the subtracted numerator is at least $45$.
For $B=2$, this estimate instead gives

$$
c'\leq5(2^{\delta'}-1)+\frac{20}{9}.
$$

Here $b_1=b_2=1$, and (3) yields

$$
c'\equiv5(2^{\delta'}-1)\pmod4.
$$

Both sides are integers and $20/9<4$, so the desired upper bound follows.
This proves the induction. $\square$

## Minimum ancestors

**Theorem 2.** Suppose the first $r$ exponents from $n$ belong to
$\{1,2\}$ and contain no consecutive twos. Then $n$ is the unique smallest
positive odd $b$ with $U^r(b)=U^r(n)$. Every such $b$ has division sum at
least that of $n$. If the word starts with one, every different such $b$
satisfies $b\geq2n+1$.

**Proof.** Apply Lemma 1 to the reversed word. If it has a final unpaired
two, the last alternative exponent $b_0$ gives

$$
\delta'=\delta+b_0-2,\qquad
c'=\frac{2^{\delta'}+2^{b_0}c-1}{3}.
$$

For $\delta\geq1$ these are nonnegative. For $\delta=0$, we have $c=0$,
the current states agree, and $b_0$ is even and at least two. Again both
are nonnegative. An upper bound on $c'$ is unnecessary after this final
step.

At full depth, therefore, $b=2^\delta n+c\geq n$. Equality gives the same
starting integer and hence the same forward itinerary by determinism.
If the forward word starts with one, there is no unpaired final two in
the reverse. Then (1) forces $c=0$ when $\delta=0$. Every different
ancestor has $\delta\geq1$ and odd $c\geq1$, proving $b\geq2n+1$.
$\square$

Every suffix has the same no-consecutive-twos property. Applying Theorem 2
to each suffix proves that the reversed observed path is minimal at every
shorter depth.

If the forward word starts with one, a prefix of length $j$ has total
division sum at most $j+\lfloor j/2\rfloor$. Since $3>\sqrt8$, every
prefix has affine slope greater than one. Its additive term is positive,
so all positive forward states are strictly larger than $n$. Consequently
no inverse path of length at most $r$ from $U^r(n)$ reaches below $n$.

## A sharp additional depth of four

**Lemma 3.** At a complete block boundary in Lemma 1, $\delta=1$ implies
$c=1$.

**Proof.** Induct on the blocks. For a block $1$, reaching $\delta'=1$
requires $(\delta,b)=(0,2)$ or $(1,1)$. The first case is impossible:
the states agree and the inverse exponent must be odd. The second
preserves $c=1$.

For a block $(2,1)$, the possibilities are
$(\delta,B)=(0,4),(1,3),(2,2)$. In the first case the only possible first
exponent is two, leaving a second exponent two, which has the wrong parity
after the shared first step. In the second case the inductive $c=1$
gives $c'=11/9$ or $13/9$, both nonintegral. In the last case $c$ is odd
and $1\leq c\leq15$, while

$$
c'=\frac{4c+5}{9}.
$$

Integrality forces $c=1$, and then $c'=1$. $\square$

**Theorem 4.** Let $n$ be a positive odd multiple of three. Suppose its
first $r$ exponents start with one, belong to $\{1,2\}$, and contain no
consecutive twos. Then

$$
U^s(b)\neq U^r(n)
\quad\text{for every positive odd }b<n
\text{ and every }0\leq s\leq r+3.
$$

**Proof.** Depths $s\leq r$ were excluded above. Consider an inverse path
of depth $r+d$ with $1\leq d\leq3$. At depth $r$, Lemmas 1 and 3 give
$y=2^\delta n+c$.

If $\delta=0$, then $y=n$ is divisible by three and the path cannot
continue. If $\delta=1$, then $y=2n+1\equiv1\pmod3$, so its next inverse
exponent is even and at least two. The smallest real three-step result,
using exponents $(2,1,1)$, is

$$
\frac{16y-19}{27}=\frac{32n-3}{27}>n.
$$

One or two additional steps give larger lower bounds.
If $\delta\geq2$, then $y\geq4n+1$. Three exponent-one inverse steps give
the lower bound

$$
\frac{8(y+1)}{27}-1
\geq\frac{32n-11}{27}>n,
$$

since $n\geq3$. Again fewer steps give larger lower bounds. Larger
exponents increase every inverse map, completing the exclusion. $\square$

**Proposition 5.** The additional depth four is attained for every
$n\equiv1275\pmod{2592}$.

**Proof.** Write

$$
n=2592t+1275,\quad
b=2048t+1007,\quad
m=4374t+2153,\qquad t\geq0.
$$

The exponents from $n$ are $(1,2,1)$ and give $U^3(n)=m$.
The start $2n+1$ reaches $m$ with exponents $(1,1,3)$.
The start $b=(64n-33)/81$ reaches $2n+1$ with exponents $(1,1,1,2)$.
These exact valuations follow respectively from
$n\equiv27\pmod{32}$ and $n\equiv60\pmod{81}$, whose intersection is the
displayed class. All states are positive, and $b<n$. Thus $U^7(b)=m$.
Theorem 4 excludes every inverse depth at most six. $\square$

At $t=0$ the two paths are

$$
1275\longrightarrow1913\longrightarrow1435\longrightarrow2153
$$

and

$$
1007\longrightarrow1511\longrightarrow2267\longrightarrow3401
\longrightarrow2551\longrightarrow3827\longrightarrow5741
\longrightarrow2153.
$$

Every arrow is one accelerated odd step.

## Why the word restriction matters

The minimum theorem cannot be extended to all words over $\{1,2\}$,
even if every forward prefix expands. For every

$$
n\equiv29023002619\pmod{2^{35}},
$$

the smaller start $(n+3)/2$ shares a future after 22 odd steps from each
start. The word from $n$ is

$$
(1,2,1,2,1,2,1,2,2,1,2,2,1,2,1,2,1,2,1,2,2,1),
$$

and the inverse word from the common future toward $(n+3)/2$ is

$$
(3,3,4,1,2,2,1,2,1,1,2,1,1,1,1,1,1,1,1,1,1,1).
$$

Their division sums are 34 and 33. Affine composition gives precisely
$(n+3)/2$, and the displayed binary class gives the exact valuations.
Every forward prefix has slope greater than one; the smallest prefix slope
is $531441/524288$. At the least representative, the common future is
$53013941237$. The supplement's independent checker verifies the full
class, not just this representative. We make no claim that 22 is the
minimum length of such an example.

## Checks, scope, and reproducibility

The proofs above are independent of finite search. Supporting checks used
exact integer arithmetic and about five CPU workers:

| Check | Scope | Result |
|---|---|---|
| Minimum theorem | All 6,762 allowed words through length 16, two positive representatives each | No smaller ancestor at matching depth |
| Additional-depth theorem | All 1,595 allowed words starting with one through length 14, a divisible-by-three representative each, three extra depths | No smaller ancestor |
| Sharp class | Seven widely separated members, every inverse depth through seven | First possible smaller ancestor at depth seven |
| Universal certificates | Exact affine congruences, positivity, and descent on two entire classes | Both verified |

The finite inverse oracle has no division-exponent cap. For a current
positive odd state $x$ with $s$ steps left,

$$
x_{\mathrm{final}}\geq
\left(\frac23\right)^s(x+1)-1.
$$

A smaller odd target is at most $n-2$, so the oracle prunes precisely when
$2^s(x+1)>3^s(n-1)$. This also bounds the exponents that need enumeration.
The symbolic checker separately verifies exact forward valuations, odd
integral inverse states, positivity, and strict descent on each arithmetic
class. It imports no search implementation. Run it without Python's
optimization flag, since it uses assertions.

The theorem rules out particular short common-future certificates, not
convergence or longer certificates. The optimal four-step class is only
one arithmetic family. No universal coverage, stopping-time bound, or
global Lyapunov function is asserted. The intended use is to omit inverse
searches proved impossible and concentrate on additional ternary
information or words containing adjacent twos.

The supplement includes the independent checker, the two finite oracles,
exact certificate data, and reproduction instructions under the MIT
license. Python 3.10 or later and its standard library suffice. The
commands and expected outputs are in `README.md`; `SHA256SUMS.txt` records
the file hashes.

## References

[1] Jeffrey C. Lagarias. *The 3x+1 problem: An annotated bibliography
(1963–1999).* 2003.
https://arxiv.org/abs/math/0309224

[2] David Applegate and Jeffrey C. Lagarias. *Density bounds for the
3x+1 problem. I. Tree-search method.* Mathematics of Computation 64
(1995), 411–426.
https://doi.org/10.1090/S0025-5718-1995-1270612-0

[3] Lynn E. Garner. *On heights in the Collatz 3n+1 problem.* Discrete
Mathematics 55 (1985), 57–64. See the detailed annotation, entry 72, in [1].
https://arxiv.org/abs/math/0309224

[4] Paul Andaloro. *On total stopping times under 3x+1 iteration.*
Fibonacci Quarterly 38 (2000), 73–78.
https://www.fq.math.ca/Scanned/38-1/andaloro.pdf

[5] Keenan Monks, Kenneth G. Monks, Kenneth M. Monks, and Maria Monks.
*Strongly sufficient sets and the distribution of arithmetic sequences
in the 3x+1 graph.* arXiv:1204.3904v2 (2012).
https://arxiv.org/abs/1204.3904v2