# Random lengths of Collatz chains

## Summary:

Given that a positive b-bit test integer is reduced by 1/p per iteration, how many iterations will, on average, be needed to reduce it to 1?

## Main Question or Discussion Point

Assuming its hail stone series is pseudo-random, the Collatz algorithm divides by 2 twice for each multiplication by 3. This means that for every three iterations the test value is on average reduced by 1/4, or 1/12 per iteration. I've tweaked the algorithm to produce much longer series for which (again, assuming they're pseudo-random) the probable reduction per iteration approaches zero (but still seems to work). I'd like to know how to calculate the average iterations (loops) expected to reduce 128-bit test values to 1, where the per loop reduction is 1/12, 1/448, 1/245760... (in order to compare to actual results).

More generally, given that a positive b-bit test integer is reduced by 1/p per iteration, how many iterations will, on average, be needed to reduce it to 1?

Related Set Theory, Logic, Probability, Statistics News on Phys.org
Stephen Tashi
Summary:: Given that a positive b-bit test integer is reduced by 1/p per iteration, how many iterations will, on average, be needed to reduce it to 1?
Perhaps you mean to ask "Given that, on average, a positive b-bit test integer $p$ is reduced by a factor of $1/p_n$ by the $n-th$ step of a process where $p_n$ is the value at the beginning the $n$-step...."?

Or is the factor $1/p$ a constant? Or did you intend "reduced by" to mean an arithmetic subtraction instead of "reduced by a factor of"?

Whatever random process you have in mind, my guess is that this question cannot be answered only by knowing the average change produced by the random process. What is the probability distribution for the change?

Last edited:
I apologize for my lack of specificity. Forget probability. Each test integer (t) is, at each iteration reduced by t * (p-1)/p where p is constant. E.g., if t is 128 bits and p=2, it would take 127 iterations to reduce t to 1. I'd probably be able to extrapolate to other p if I were better at math.

Stephen Tashi
E.g., if t is 128 bits
Do you mean "if $t = 2^{129} - 1$"? Or perhaps you mean $2^{128} \le t \le 2^{129} - 1$ ?

Each test integer (t) is, at each iteration reduced by t * (p-1)/p where p is constant.
Suppose $t = 13$ and $p = 3$. Does the iteration produce the new value $t = 8$? Or does it produce the new value $t = 9$ ?

I'd probably be able to extrapolate to other p if I were better at math.
This might not be a simple question - depending on how we settle the details!

Thanks Stephen. Assume that intermediary test values need not be integral. So 13 * (2/3) = 8.66666... Starting to look like a logarithm thing to me. The number of iterations of x=x*((p-1)/p) it'll take to reduce x by one bit should be fairly constant (per bit) as p approaches infinity.

Stephen Tashi
Thanks Stephen. Assume that intermediary test values need not be integral. So 13 * (2/3) = 8.66666... Starting to look like a logarithm thing to me.
Then is the question to solve $t (\frac{p-1}{p})^N = 1$ for $N$?

If it solves to the same N as this algo, where t and p are given, then yes.

Code:
N=0
while t>=1
t=t*((p-1)/p)
N++
endwhile

Stephen Tashi
If it solves to the same N as this algo, where t and p are given, then yes.

Code:
N=0
while t>=1
t=t*((p-1)/p)
N++
endwhile
That algorithm does an interation when t is initially 1. Is that what you want it to do?

Doesn't really matter since intermediary values needn't be integral. But, yes, I suppose while t>1 would've been better. Thanks for pointing that out. Been trying to see whether the algorithm is the same as your equation (besides that t might never exactly = 1 and so it would have no solution). But is it basically the same? I can probably test using small t and p.

Stephen Tashi
But is it basically the same?
Yes, I think so.

Testing the algorithm with (p-1)/p=11/12 , t=67 then N=49 and t ends up at 0.94. And the expression 67*((11/12)^49) also equals 0.94. So it seems they are the same. Thanks. So how does one find the smallest value of N, given t and p, where t*(p^N)<=1?

Stephen Tashi
$t (\frac{p-1}{p})^N = 1$
$(\frac{p-1}{p})^N = 1/t$
$N \log( \frac{p-1}{p}) = - \log t$
$N = \frac{ (- \log t)}{\log ((p-1)/p))}$

gives a possibly non-integer value of $N$. The solution you want is given by rounding it up. Of course, that's ignoring things like round-off error that actually occur in programs.

Thanks for the solution and the process. Will give it a try. Where p is large, will have to find a way to make work with huge integers is all. Appreciate your help here, Stephen.

pbuk