- #1
Chris Miller
- 371
- 35
- TL;DR 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?
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?
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?