# Does this extension of the Collatz sequence converge for n=550?

The Collatz function, or $3n + 1$ function is well known. A heuristic argument that most inputs should converge with repeated application of the function is as follows. With probability 1/2 an input $n$ will be either even or odd. If it is even, it will be multiplied by a factor of 1/2. If it is odd, it will be multiplied by a factor of roughly 3, and then divided by 2. So on average we would expect the growth rate per two iterations to be $\frac{1}{2}*\frac{3}{2} = \frac{3}{4} < 1$.

Now consider the following extension to numbers $p$ and $q$.

$f(n) = \begin{cases} n/p & \quad \text{if } n \text{ is divisible by }p\\ qn \text{ rounded up to the nearest multiple of }p & \quad \text{if } n \text{ is not divisible by }p\\ \end{cases}$

We can also express this function as (for ease of computation)

$f(n) = \begin{cases} n/p & \quad \text{if } n \text{ mod }p=0\\ qn + p - (qn\text{ mod }p) & \quad \text{otherwise}\\ \end{cases}$

Then, heuristically we can argue that an input $n$ has a $\frac{1}{p}$ probability to be a multiple of $p$ and hence will be multiplied by $\frac{1}{p}$, and a $\frac{p-1}{p}$ probability to be multiplied by a factor of $\frac{q}{p}$. So the average growth factor we expect after $p$ iterations is $\frac{1}{p}(\frac{q}{p})^{p-1}$.

Now consider the case $p=3$, $q=5$. The heuristic growth factor is $\frac{1}{3}(\frac{5}{3})^2 = \frac{25}{27} < 1$, so we predict convergence. Indeed, for every starting $n \leq 549$ the sequence formed by repeated application of $f$ converges to one of two cycles.

$4 \rightarrow 21 \rightarrow 7 \rightarrow 36 \rightarrow 12 \rightarrow 4$

$8 \rightarrow 42 \rightarrow 14 \rightarrow 72 \rightarrow 24 \rightarrow 8$

However, the sequence starting with $n = 550$ eventually overflows the integer arithmetic in Matlab. (~$10^{200}$). Note that the sequence hovers in the $10^{15}$ range for a while before skyrocketing straight to $10^{200}$, so I don't quite trust the computation.

Can someone either $(a)$ show that $550$ actually does converge using better numerics or $(b)$ prove that $550$ diverges?

• My computation (in Mathematica) shows that 550 converges to the first sequence above after somewhere between 2800 and 3000 terms. I can send you the entire sequence if you want. – rogerl Oct 7 '15 at 19:11
• Confirmed, $2$ is reached at the $2831^{\text{st}}$ step, then it enters $12 \to 4$. The maximum number appearing in the sequence is $366801780869709687$. – Daniel Fischer Oct 7 '15 at 19:14
• Alright, it looks like Matlab is just misleading when integers exceed $2^{63}$. It still allows integer math to be performed but the results may be inaccurate. – Brady Gilg Oct 7 '15 at 20:14
• No more loops for $n \lt 200\, 000$ – Gottfried Helms Oct 8 '15 at 7:22
• In the "negative" domain (can be simulated if you use "rounded down" instead of "rounded up") we seem to have only one cycle $1 \to 3 \to 1$ – Gottfried Helms Oct 8 '15 at 7:39

Here is a bit of python that can run this task.

def f(n, p, q, max_trials=10000):
if n <= 0:
return 0
trial = 0
ret = []
while (n != 4) and (n != 8) and (trial<max_trials):
ret.append(n)
if n%p == 0:
n = n/p
else:
n = q*n + p - (q*n % p)
return ret

if __name__ == "__main__":
print f(550, 3, 5)


As mentioned in the comments, the sequence terminates into a loop on the 2831st step. There are $8$ numbers in the sequence larger than $10^{17}$, $77$ larger than $10^{16}$ and $167$ larger than $10^{15}$. So "most" terms in the sequence are smaller than $10^{15}$.