What is the pattern in the modulus when applying collatz function to linear polynomials?

Question

$C(n) = \frac{n}{2}$ if $n$ is even, or $3n + 1$ if $n$ is odd

This function is normally applied to constant numbers, but it can be used on linear polynomials $ax + b$.

There are 3 possibilities of what $ax + b$ can be, it can be always even, it can be always odd, or it can vary depending on the value of $x$.

To determine whenever a $ax + b$ will be even, odd, or vary this is the process:

• If $a$ is odd. then $ax + b$ vary.

• otherwise, if $b$ is even, then $ax + b$ is even, or if $b$ is odd, then $ax + b$ is odd

This way, we can apply $C(n)$ to linear polynomials, when $n$ vary $C(n)$ would be undefined, as there would be $2$ possible outputs.

Examples:

• $C(8x + 2) = 4x + 1$

• $C(6x + 3) = 18x + 10$

• $C(3x + 2)$ is undefined

Python function for $C(n)$

def collatz(a, b):
    """Apply the collatz function to ax + b"""
    # If 'a' is odd, then it has two possible outputs, so return None instead
    if a % 2 == 1:
        return None
    # If 'a' is even, then it has only one possible output
    if b % 2 == 0:
        # apply (a/2)x + (b/2)
        a //= 2
        b //= 2
    else:
        # apply 3(ax + b) + 1 = (3a)x + (3b + 1)
        a *= 3
        b = 3 * b + 1
    return a, b

You can apply the function multiple times to a linear polynomial and have a sequence (stopping once you have an undefined result)

$$8x + 5$$ $$24x + 16$$ $$12x + 8$$ $$6x + 4$$ $$3x + 2$$

as you can see, it started with $8x + 5$, and after applying the function $3$ times, the values became $6x + 4$, which is smaller than $8x + 2$, it means that for any value (positive integer) of x in $8x + 5$, it will always reach a value smaller than the seed.

This is important because if you prove that every value reach a number smaller than itself (other than seed $1$), it implies that it eventually reaches $1$.

But not all linear polynomials can be proven to reach a smaller value that way, for example:

$$6x + 3$$ $$18x + 10$$ $$9x + 5$$

As you can see, it reaches an undefined polynomial before it reaches a polynomial smaller than $6x + 3$.

This brings the question: For what values of $a$ and $b$ will $ax + b$ reach a smaller value than itself before reaching an undefined polynomial?

Python function

def check_goes_smaller(a, b):
    """Check if ax + b can be proven to reduce to a smaller value on the collatz function"""
    seed_a, seed_b = a, b
    # Start by assuming it doesn't reduce
    reduces = False
    # Once 'a' is odd, there are more than one output after applying the collatz function
    while a % 2 == 0:
        a, b = collatz(a, b)
        # Check if it's smaller than the seed
        if a < seed_a or (a == seed_a and b < seed_b):
            reduces = True
            break
    return reduces

You can discard all polynomials such that $a$ is odd, as the next value of the sequence will be undefined.

Let's check for some specific value of $a$, for what values of $b$ will $ax + b$ reach a smaller value in the collatz function?

2x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
4x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
6x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
8x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
10x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
12x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
14x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
16x + {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, ...}
18x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
20x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
22x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
24x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
26x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
28x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
30x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
32x + {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, ...}
34x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
36x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
38x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
40x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
42x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
44x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
46x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
48x + {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, ...}
50x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
52x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
54x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
56x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
58x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
60x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
62x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
64x + {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, ...}
66x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
68x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
70x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
72x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
74x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
76x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
78x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
80x + {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, ...}
82x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
84x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
86x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
88x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
90x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
92x + {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}
94x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
96x + {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, ...}
98x + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, ...}
...

Using this python script

def get_values(a, length=20):
    values = []
    b = 0
    while len(values) < length:
        if check_goes_smaller(a, b):
            values.append(b)
        b += 1
    return values

for a in range(2, 100, 2):
    b_values = get_values(a)
    b_values = "{" + str(b_values)[1:-1] + ", ..." + "}"
    print(f"{a}x + {b_values}")
print("...")

If you analyze those sets, you'll notice that they can be described as numbers that are congruent to some specific values at some modulus, for example, the possible values of $b$ that reach a smaller number in $8x + b$, {0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, ...}, the values on this set are the numbers that are congruent to $0, 1$ or $2$ (mod $4$)

Here is a table of values with the set as congruence sets

2x + [congruent to [0] (mod 2)]
4x + [congruent to [0, 1, 2] (mod 4)]
6x + [congruent to [0] (mod 2)]
8x + [congruent to [0, 1, 2] (mod 4)]
10x + [congruent to [0] (mod 2)]
12x + [congruent to [0, 1, 2] (mod 4)]
14x + [congruent to [0] (mod 2)]
16x + [congruent to [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14] (mod 16)]
18x + [congruent to [0] (mod 2)]
20x + [congruent to [0, 1, 2] (mod 4)]
22x + [congruent to [0] (mod 2)]
24x + [congruent to [0, 1, 2] (mod 4)]
26x + [congruent to [0] (mod 2)]
28x + [congruent to [0, 1, 2] (mod 4)]
30x + [congruent to [0] (mod 2)]
32x + [congruent to [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30] (mod 32)]
34x + [congruent to [0] (mod 2)]
36x + [congruent to [0, 1, 2] (mod 4)]
38x + [congruent to [0] (mod 2)]
40x + [congruent to [0, 1, 2] (mod 4)]
42x + [congruent to [0] (mod 2)]
44x + [congruent to [0, 1, 2] (mod 4)]
46x + [congruent to [0] (mod 2)]
48x + [congruent to [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14] (mod 16)]
50x + [congruent to [0] (mod 2)]
52x + [congruent to [0, 1, 2] (mod 4)]
54x + [congruent to [0] (mod 2)]
56x + [congruent to [0, 1, 2] (mod 4)]
58x + [congruent to [0] (mod 2)]
60x + [congruent to [0, 1, 2] (mod 4)]
62x + [congruent to [0] (mod 2)]
64x + [congruent to [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30] (mod 32)]
66x + [congruent to [0] (mod 2)]
68x + [congruent to [0, 1, 2] (mod 4)]
70x + [congruent to [0] (mod 2)]
72x + [congruent to [0, 1, 2] (mod 4)]
74x + [congruent to [0] (mod 2)]
76x + [congruent to [0, 1, 2] (mod 4)]
78x + [congruent to [0] (mod 2)]
80x + [congruent to [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14] (mod 16)]
82x + [congruent to [0] (mod 2)]
84x + [congruent to [0, 1, 2] (mod 4)]
86x + [congruent to [0] (mod 2)]
88x + [congruent to [0, 1, 2] (mod 4)]
90x + [congruent to [0] (mod 2)]
92x + [congruent to [0, 1, 2] (mod 4)]
94x + [congruent to [0] (mod 2)]
96x + [congruent to [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30] (mod 32)]
98x + [congruent to [0] (mod 2)]
...

The modulus that each number have generates this sequence:

2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 128, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 256, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 128, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 256, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 128, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 256, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 128, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, 4, 2, 4, 2, 16, 2, 4, 2, 4, 2, 4, 2, 32, 2, 4, 2, ...

The numbers that appear in the sequence, in the order they appear are $2, 4, 16, 32, 128, 256, 1024, 4096, 8192, ...$.

If you take log 2 of them you get

$1, 2, 4, 5, 7, 8, 10, 12, 13$

Searching this on the OEIS i get the sequence A020914: "Number of digits in the base-2 representation of 3^n."

Any ideas?

---

UPDATE

(obs: the discovers were done just by analysis, they still need proof)

By analysis, the possible numbers that can be a modulus are 2^{Number of digits in the base-2 representation of 3^n}, which are $2, 4, 16, 32, 128, 256, 1024, 4096, 8192, 32768, 65536, 262144, 1048576, 2097152, 8388608, 16777216, ...$

I will call this set $S$, so $S_1 = 2$, $S_2 = 4$, etc.

let $M(n)$ be the modulus of the set of possible $b$ values

e.g. M(8) = 4, because the possible values of $b$ that goes to a smaller value on $8x + b$ are numbers that are congruent to [0, 1, 2] (mod 4)]

I've manually done some analysis, on what type of numbers have specific values of $S$ as modulus

M(n) = 2 when n = {2} mod 4
M(n) = 4 when n ≡  {4, 8, 12} mod 16
M(n) = 16 when n ≡ {16} mod 32
M(n) = 32 when n ≡ {32, 64, 96} mod 128
M(n) = 128 when n ≡ {128} mod 256
M(n) = 256 when n ≡ {256, 512, 768} mod 1024

It seems like there are two possibilities

If $k$ is odd:

$M(n) = S_k$ when $n \equiv S_k$ (mod $2 \cdot S_k$)

Ex:

• $M(n) = 16$ $(S_3)$ when $n \equiv 16$ (mod $32$)

• $M(n) = 128$ $(S_5)$ when $n \equiv 128$ (mod $256$)

If $k$ is even:

$M(n) = S_k$ when $n \equiv \{S_k, 2 \cdot S_k, 3 \cdot S_k\}$ (mod $4 \cdot S_k$)

Ex:

• $M(n) = 4$ ($S_2$) when $n \equiv \{4, 8, 12\}$ (mod $16$)
• $M(n) = 32$ ($S_4$) when $n \equiv \{23, 64, 96\}$ (mod $128$)

Answer 1

This is an extended comment.

The setup for this problem can be described in somewhat more classical terms. Let us use a (mildly) "accelerated" Collatz sequence:

$$C(n) = \begin{cases} n/2 & n \text{ even} \\ (3n+1)/2 & n \text{ odd} \end{cases}$$

Note that $C(ax+b)$ is either undefined or ($a$ is even and) it is $\alpha x + C(b)$, where $\alpha=\frac12a,\frac32a$ depending on the parity of $b$. In particular, this means that if $a=2^km$ for odd $m$, then $a$ will become odd after exactly $k$ (accelerated) steps. Moreover, the $x$-coefficient at each step $a_i$ satisfies $a_i/a =3^j/2^i$, if there have been $j$ up-steps so far. In particular, the question of whether $a_i<a$ depends only on $k$ and $b$, not on the odd factor $m$.

Therefore, the provided code is checking whether at any point in the first $k$ steps of the Collatz sequence for $b$, the corresponding $a_i$ ever drops strictly below $a$. (Note that $a_i=a$ is impossible, since each $a_i$ has fewer $2$s in its prime factorization.)

As I mentioned in the (actual) comments, this is nominally different from the stated goal of checking whether $a_ix+b_i<ax+b$ for any integer $x\geq 1$. However, I think it is approximately the same. I'm not interested in formalizing this right now, but consider the additive "bonus" for $b$ compared to $a$: from the first up-step it is $\frac12$, from the second it is $\frac14$, and so on. At any future term with $a_i<a$, these bonuses can only have reduced, and thus $b_i<b+\frac12+\frac14+\cdots<b+1$. Not sure if we can get the last +1 eliminated or if that's actually equivalent to the cycle half of Collatz. (Perhaps "only" using Baker's theorem? See Corollary 4)

In any case, this means our problem is to look through the the first $k$ steps of Collatz sequences $b=b_0,b_1,\dots, b_k$ and check whether $b_i\leq b$ for any $1\leq i\leq k$. If the above +1 issue can be resolved, we can upgrade to a strict inequality. Either way, this should be a warning that our new technology has not moved us so far away from Collatz's inherent difficulties.

---

Regarding the 3 Sept ~19:00 UTC update:

The "two possibilities" are slightly more complex than even/odd. For instance, the even/odd prediction runs into trouble when $n=8192$ is predicted to both give periods of $4096$ (because $S_8=4096$) and $8192$ (because $S_9=8192$). But the spirit could be right: $S_{k+1}/S_k$ is provably always either 2 or 4; use the "odd" prediction in the first case and the "even" prediction in the second?

(Note that there is no simple pattern for which $k$ give 2 and which give 4, since the number of digits of $3^k$ in binary is $1+\lfloor\log_2(3) k\rfloor$, and $\log_2(3)$ is irrational.)

I also mentioned in my comments that $2^k$ is always a period (not necessarily the minimal period!) for the $b$, or in other words that $M(2^km)|2^k$. This is because for any $j>0$, adding $2^j\ell$ does not change the parity, and thus $C(b+2^j) = C(b) + 2^{j-1}\ell$ for either $\ell=1,3$. In any case, this means that adding $2^k$ to $b$ does not change which steps are up and which are down, and therefore does not change the sequence of $x$-coefficients $a_i$. On the $k^\text{th}$ step, first step that it would change, $a_k$ is finally odd, and so the sequence terminates.

This argument suggests a potential source of counterexamples to the prediction that I made above. What it means for $2^{k-1}$ to be a period is almost surely that a lower value was already achieved before the last step: when adding $2^{k-1}$, all steps before the last will be in the same direction, but the $k^\text{th}$ step is guaranteed to be in the opposite direction. So the idea would be to find numbers $N$ and $N+2^{k-1}$ which stay above the starting value for the first $k-1$ steps, but their $(k-1)^\text{th}$ values are close enough that the change in directions changes whether the last step lands larger or smaller.

Answer 2

Consider the Collatz sequence of odd integers $x_i$ where $$x_{i+1} = \frac{3x_i + 1}{2^{n_i}}$$ where $n_i$ is the unique positive integer such that $x_{i+1}$ is odd. Define $$N_i := \sum\limits_{j=1}^i n_j \textrm{ for } i \gt 0 \textrm{ and } N_0 := 0$$ $$\sigma = \sum\limits_{i=0}^{L-1} 3^{i}2^{N_{L - 1 - i}} = \sum\limits_{i=0}^{L-1} 3^{L - 1 - i}2^{N_{i}}$$ then starting with $x_1$, $x_{L+1}$ is given by: $$2^{N_L} x_{L+1} - 3^L x_1 = \sigma$$ This is a linear Diophantine equation with variables $x_1$ and $x_{L+1}$ with coprime coefficients and therefore has an infinite number of integer solutions of the form: $$(x_1,x_{L+1}) = (x'_1 + k 2^{N_L}, x'_{L+1} + k 3^L)$$ where $(x'_1,x'_{L+1})$ is any particular solution which can be found by finding a solution to $$2^{N_L}x''_{L+1} - 3^L x''_1 = 1$$ using the Extended Euclidean Algorithm and then $$(x'_1, x'_{L+1}) = (\sigma x''_1, \sigma x''_{L+1})$$ so that $$(x_1,x_{L+1}) = (\sigma x''_1 + k 2^{N_L}, \sigma x''_{L+1} + k 3^L)$$ $k$ is an integer which is restricted if only positive $x$ are considered and also restricted to being even if only odd $x_{L+1}$ are considered. So every set of $n_i > 0$ and hence $N_i$ of length $L$ corresponds to a set of $(x_1,x_{L+1})$ pairs with spacing given by $(2^{N_L},3^L)$. $N_L$ is the total number of divide by $2$'s. So $\sigma$ corresponds to your $a$ and $k2^{N_L}$ corresponds to your b.

For $x_{L+1}$ to be less than $x_1$ we must have at least $2^{N_L} > 3^L$. The Coefficient Stopping Time Conjecture posits that $x_{L+1}$ is always less than $x_1$ whenever this condition is met but is not proven. http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/node5.html

Update to address comment by Eric Stucky:

So a question in the OP is for $ax+b$, for what integer values of $a,x$ and $b$ will repeated application of the Collatz operator result a value less than the original value. I'm only addressing $a,x$ odd and $b$ even. The answer is all $x_1$ solutions to the above Diophantine equation for all $N_L$ and $L$ with $2^{N_L} \gt 3^L$ with every possible $n_i,$ $i=1$ to $L$, $n_i \gt 0$ and $\sum{n_i} = N_L$ where $x=x''_1$, $a=\sigma$, $b=k2^{N_L}$, and with integer $k$ such that $x_1 > 0$, at least if the Coefficient Stopping Time Conjecture is true. Even if that conjecture isn't true then all solutions are still of this form. I'm using the Syracuse form of the Collatz operator. So $L$ is the number of odd integers in the sequence starting with an odd integer. (Actually, the last integer in the sequence is even if $k$ is odd). $N_L$ is the total number of divide by 2's in the sequence, which for your formulation of the Collatz operator is the total number of integers in the sequence.

For any odd integer to become a lesser value after $L$ iterations (of the Syracuse form of the Collatz operator) then we must have $2^{N_L} > 3^L$. So a starting odd integer which has a finite stopping time must be a solution to some Diophantine equation with $2^{N_L} > 3^L$. These starting values have the form $\sigma x''_1 + k 2^{N_L}$ so we just map that onto $ax+b$. There is a correspondence between a set of $n_i$ and the set of $x_1$ which are the solutions to the Diophantine equation.