What are the known rules on the seed that guarantee the Collatz sequence will stop

Question

I have written some code that searches for counter-examples to the Collatz conjecture. The following fact enables me to accelerate the search.

In the paper "Garner, Lynn - On The Collatz 3n + 1 Algorithm" Garner claims it is "not hard to verfiy" that the following rules hold.

I have spent about a week trying to prove the general version of this result, but have not succeeded. I will define the terms in Garner's paper, and would be grateful for any help.

The Collatz map $c:\mathbb{N}\to\mathbb{N}$ is defined by

$c\left(n\right):=\frac{1}{2}\begin{cases} 3n+1 & n\text{ odd}\\ n & n\text{ even} \end{cases}$

Given a seed $n\in\mathbb{N}$ the Collatz sequence is defined as $\left\{ c^{p}\left(n\right)\mid p\in\omega\right\}$, where as usual $c^{0}\left(n\right)=n$ and $c^{p+1}\left(n\right)=c\left(c^{p}\left(n\right)\right)$ for all $n\in\mathbb{N}$.

Given any $n\in\mathbb{N}$ the stopping time $\sigma\left(n\right)$ is the smallest $p\in\mathbb{N}$ such that $c^{p}\left(n\right)<n$. If the Collatz conjecture is true every Collatz sequence has a finite stopping time.

I am after the theorem that says something like; Given $n,m\in\mathbb{N}$, $\sigma\left(n\right)=m$ whenever $n\equiv p\mod{2^{q}}$ for $p,q$ with THIS property. My question is what is THIS property?

Answer 1

These numbers come from explicitly writing out the iterates of the Collatz function and seeing, from that, which numbers have which stopping times. If you want to condense the property being discussed, it's as follows: we can compute that $$c^q(x\cdot 2^q+p)=\alpha x + \beta$$ for some integer constants $\alpha$ and $\beta$. If $\alpha < 2^q$, then, for all great enough $n$ equivalent to $p$ mod $2^q$, we will have $c^q(n) < n$ - and we can use this to create the sort of statements in your question.

It's best to illustrate this with an example. To see that the stopping time of $32x + 11$ is $5$ (for the $c$ in the question*), one could calculate: $$c(32x+11) = 48x + 17$$ $$c^2(32x+11) = 72x + 26$$ $$c^3(32x+11) = 36x + 13$$ $$c^4(32x+11) = 54x + 20$$ $$c^5(32x+11) = 27x + 10$$ Where, for $x\geq 0$, it's clear that the first four iterates are greater than the input, and the fifth is less than the input - hence the stopping time is $5$. Note that we cannot compute the sixth iterate, since $27x+10$ could be either even or odd.

You can run a similar sort of calculation to explicitly get the first $q$ iterates of $c$ applied to $2^q\cdot x + p$ for any $p$ as a linear function of $x$ - and doing such a calculation might reveal the stopping time of numbers of that form (as it did in the example I gave).

If you wanted to generate the list they made in the paper, what you can do is calculate this for every possible mod $2$ residue, and note which residues have fixed stopping times. Then, of those residues which did not have fixed stopping times, you can split them into two residue classes mod $4$, and see if any of those have fixed stopping times (now being able to calculate one more iteration in the future). Then, you can split into residues mod $8$ and so on, until you are satisfied. Note that the number of residues remaining mod $2^q$ will grow exponentially (although the proportion of residues lacking a stopping time will decrease towards $0$).

You can be a bit more sophisticated with this, although it's not clear it would be useful for your application. If you fix the parities of the sequence $x, c(x), c^2(x),\ldots, c^{n-1}(x)$, there is a unique equivalence class mod $2^n$ such that $x$ in that class will have a trajectory with the specified parities - for instance, there is some mod $8$ equivalence class such that $x$ is even, $c(x)$ is odd, and $c^2(x)$ is even. You can note that, for $x$ in that class, we must have $c^n(x)=\alpha x + \beta$ for some rational $\alpha$ and $\beta$ - and can explicitly compute $$\alpha = (3/2)^{\text{# of odd steps in trajectory}}\cdot (1/2)^{\text{# of even steps in trajectory}}.$$ This can give the asymptotic results noted in the paper, but is probably not the most efficient way to generate a list of all classes that don't stop after some number of steps.

(*The paper you quote appears to use the version of the Collatz function that takes two steps to go from odd $x$ to $\frac{1}2(3x+1)$, so gets $8$ instead - but it's the same idea with that method, although it works somewhat less elegantly with that slower function)

Answer 2

Based on previous answers I have done more analysis and identified a way of finding rules that eliminate a seed n as a candidate for violating the Collatz conjecture. Considering modular restrictions as discussed here on Wikipedia we get the following.

Fact. If for some $k\ge0$ and $2^{k}>b\ge0$ we have $c^{k}\left(2^{k}a+b\right)<2^{k}a+b$ for all $a>0$, then the first number $n$ for which the Collatz sequence does not reach $1$, if it exists, cannot be $b\mod2^{k}$, that is $n\not\equiv b\mod2^{k}$. Recalling that $m\equiv n\mod2^{k}$ iff $m-b=a2^{k}$ for some $a\in\mathbb{Z}$, note that saying $m$ cannot be $b\mod2^{k}$ means that $m\neq a2^{k}+b$ for any $a\in\mathbb{Z}$.

Regarding a Collatz sequence as a partity sequence as described here on Wikipedia we observe that $c^{p}\left(a2^{k}+b\right)=a3^{c\left(p,k,b\right)}+c^{p}\left(b\right)$ and so is linear in $a$ and can therefore be determined by any two points on its line.

By the Fact we are interested in the $p=k$ case. The obvious points on the line to take are $\left(0,c^{k}\left(b\right)\right)$ and $\left(1,c^{k}\left(2^{k}+b\right)\right)$, and these are easily calculated. The line through these two points is then $y\left(a\right)=\left(c^{k}\left(2^{k}+b\right)-c^{k}\left(b\right)\right)a+c^{k}\left(b\right)$

Substituting back into the Fact above we require $\left(c^{k}\left(2^{k}+b\right)-c^{k}\left(b\right)\right)a+c^{k}\left(b\right)<2^{k}a+b$ for all $a>0$. By simple geometry this will be the case iff

• $c^{k}\left(2^{k}+b\right) \le c^{k}\left(b\right)+2^{k}$

• $c^{k}\left(b\right) \le b$

• $c^{k}\left(2^{k}+b\right) < 2^{k}+b$

We will say $\left(k,b\right)\in\omega^{2}$ is an elimination rule iff it satisfies these equations. We can then say that the Collatz sequence with seed $n$ will reach $1$ if it is $b\mod2^{k}$. In other words $n$ is not a candidate for violating the Collatz conjecture.

Let $\left(k,b\right)$ and $\left(k^{\prime},b^{\prime}\right)$ be elimination rules. It is reasonably easy to show that if $k\ge k^{\prime}$ and $0\equiv\left(b-b^{\prime}\right)\mod2^{k^{\prime}}$ then $\left(k,b\right)$ is subordinate to $\left(k^{\prime},b^{\prime}\right)$ in the sense that being $b\mod2^{k}$ implies being $b^{\prime}\mod2^{k^{\prime}}$. For example being $0\mod2^{3}$ (divisible by 8) implies being $0\mod2^{1}$ (even). Given this we can ignore subordinate rules when trying to eliminate $n$.

The following python script generates all non-redundant elimination rules up to k_max. With k_max=8 it generates rules that eliminate about 93% of seeds.

def collatz_seq(seed,p=0):
    # Return c^p(seed). 
    c=seed
    s=[seed]
    k=0
    while True:
        if seed>0 and c<=1:break
        if p!=0 and k==p:break
        c=int(c/2) if (c%2) == 0 else int((3*c+1)/2)
        s+=[c]
        k+=1
    return s[-1]

def cka2kb_test(k,b):
    """
    Work out the line for c^k(a*2^k+b) and compare to a*2^k+b.
    If LHS < RHS for all a>0 then (k,b) is an elimination rule. 
    """  
    # Get two points on the c^k(a*2^k+b) line.  
    pts=[]
    for a in range(2):
        pts+=[(x:=a*(2**k)+b,collatz_seq(x,k))]
    # Work out the equation of the b line a*2^k+b line. 
    b_line=(pts[1][0]-pts[0][0],pts[0][0])
    # Work out the equation of the c line c^k(a*2^k+b) line. 
    c_line=(pts[1][1]-pts[0][1],pts[0][1])
    # Test if lines c^k(a*2^k+b) < a*2^k+b for a>0. 
    vfy=(c_line[0]<=b_line[0]) # c line slope <= b line slope. 
    vfy=vfy and (c_line[1]<=b_line[1]) # c line intercept <= b line intercept. 
    vfy=vfy and (c_line[0]+c_line[1]<b_line[0]+b_line[1]) # c line < b line at 1. 
    return {'verified':vfy,
            'cka2kb':c_line,
            'a2kb':b_line,
            }

def is_in_rules(rule,rules):
    # Check if exclusion rule is subordinate to an existing rule. 
    for r in rules:
        subord=(rule[0]>=r[0])
        x=(rule[1]-r[1])/(2**r[0])
        subord=subord and (x.is_integer()) 
        if subord: 
            return True
    return False

def find_exclusion_rules(k_max=8):
    # Find (k,b) such that c^k(a*2^k+b) < a*2^k+b for all a. 
    # With k_max=8 (2^k=256) this accounts for 93% of seeds. 
    # With k_max=16 (2^k=65,536) evaluates in reasonable time. 
    rules=set()
    for k in range(1,k_max+1):
        for b in range(2**k):
            # skip if (k,b) equiv to found rule
            if is_in_rules((k,b),rules):continue
            # test all a for this (k,b)
            vfy=cka2kb_test(k,b)
            if vfy['verified']:rules.add((k,b))
    rules=list(rules)
    rules.sort()
    return rules

if __name__ == '__main__':
    excl_lvls=8
    rules=find_exclusion_rules(excl_lvls)
    print(rules)

The elimination rules the script generates with k_max=8 are [(1, 0), (2, 1), (4, 3), (5, 11), (5, 23), (7, 7), (7, 15), (7, 59), (8, 39), (8, 79), (8, 95), (8, 123), (8, 175), (8, 199), (8, 219)].

For example consider the rule $(7,15)$, this means that if $n$ is $15\mod2^7$ then the Collatz sequence starting with $n$ reaches $1$, and so is not a candidate for violating the Collatz conjecture. Compare this to the rule from my original question which asserts the stopping time is $11$ if $n$ is $15\mod 128$.