6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rogerl Oct 7 '15 at 19:11
  • $\begingroup$ 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$. $\endgroup$ – Daniel Fischer Oct 7 '15 at 19:14
  • $\begingroup$ 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. $\endgroup$ – Brady Gilg Oct 7 '15 at 20:14
  • $\begingroup$ No more loops for $n \lt 200\, 000$ $\endgroup$ – Gottfried Helms Oct 8 '15 at 7:22
  • $\begingroup$ 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$ $\endgroup$ – Gottfried Helms Oct 8 '15 at 7:39
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.