Random lengths of Collatz chains

[Chris Miller]

TL;DR

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?

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?

 

[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?

 

[Chris Miller]

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!

 

[Chris Miller]

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$?

 

[Chris Miller]

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

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.

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?

 

[Chris Miller]

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.

 

[Chris Miller]

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.

 

[Chris Miller]

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]

Not sure where you are going with this, but I assume you have seen a chart similar to the one at https://commons.wikimedia.org/wiki/File:Collatz-stopping-time.svg ? What does this say to you about your assumption in post #1 "Assuming its hail stone series is pseudo-random"?

 

[Chris Miller]

Not sure what "total stopping time" means exactly. By "assuming" I meant only treating. I wouldn't think it would pass any random tests like GCD, Gorilla, b-day, etc., or be evenly distributed since all normal Collatz series end on 16, 8, 4, 1. The higher level series I'm playing with can be millions of times longer and cover much wider ranges of values, and seem to act like probability distributions, much more than normal (level 0) Collatz. In series that reach 50 and 100-bit values before descending, I'd still expect to see more frequent lower integers. But the LSBs are almost perfectly random.