Random lengths of Collatz chains

  • #1
313
29

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?
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
6,960
1,203
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:
  • #3
313
29
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.
 
  • #4
Stephen Tashi
Science Advisor
6,960
1,203
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!
 
  • #5
313
29
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.
 
  • #6
Stephen Tashi
Science Advisor
6,960
1,203
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##?
 
  • #7
313
29
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
 
  • #8
Stephen Tashi
Science Advisor
6,960
1,203
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?
 
  • #9
313
29
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.
 
  • #10
Stephen Tashi
Science Advisor
6,960
1,203
  • #11
313
29
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?
 
  • #12
Stephen Tashi
Science Advisor
6,960
1,203
## 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.
 
  • #13
313
29
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.
 
  • #14
pbuk
Science Advisor
Gold Member
1,282
287
  • #15
313
29
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.
 

Related Threads for: Random lengths of Collatz chains

  • Last Post
Replies
3
Views
2K
Replies
1
Views
2K
Replies
11
Views
733
Replies
8
Views
25K
Replies
0
Views
2K
Replies
146
Views
5K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
6K
Top