Collatz extensions

Question

Because, in the basic Collatz algorithm, odds are always transformed into evens (via x=3x+1), and evens are transformed into evens with a probability of .5 (via x=x/2), there will be, on average, 2 divisions (x/4) for every multiplication (x*3). So probability predicts inevitable reduction.

Is the problem then proving there can be no collisions (i.e., internal loops) in test values before 1 is reached?

To try to understand, I've added a second test (only) after dividing an even in which, if the result is odd, I subtract 1 and divide again: i.e., x=(x-1)/2. Now probability predicts 6 divides for each multiplication, and the highest probabilistically descending multiplier is 2^6-1 (63). Here, instead of an average reduction of 3/4 (as per Collatz), it's only 63/64, and one would expect series to be a lot longer. Here's the pseudo-code:

while test>1
    if is_even(test)
        test = test/2
        if is_odd(test)
            // could test for 1 here
            test=(test-1)/2
        endif
    else
        test=test*63+1
    endif
endwhile

I've been running the above algo with huge integers for a few hours now and tested past 14 bits. So far the largest number of iterations has been 1,176,551 for the integer 10581 which reached a 2255-bit intermediary value.

Additional nested odd tests require larger multipliers and result in narrower probability spreads. E.g.:

0 tests (Collatz) : mult = 3,  reduces by 3/4
1 test (as here): mult=63, reduces by 63/64
2 tests: mult=16383 (2^14-1), reduces by 16383/16384
3 tests: mult=(2^30-1) ...

I hypothesize that any above variation will eventually reduce any test value to 1 (though some could take longer than the universe will be around).

I assume this (these) extensions are equally un-provable conjectures, but might they shed light on Collatz by providing a broader context?

https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference oh and 50% of odds will be $4k+3$ shooting two divisions by 2 in the foot. — , Feb 04 '20 at 18:40
Ah, now I see what you're saying. Of course that's true. So? The ratio of divisions to multiplications still approaches to 6:1. — Chris Miller, Feb 04 '20 at 20:33

score 1 · Answer 1 · answered Feb 04 '20 at 19:19

1

$$4k+3\to 12k+10\to 6k+5\to 18k+16\to 9k+8$$

The last number here is same parity as $k$ assuming it's odd we get:$$\to 54j+52$$ which will only divide by 2 twice if $j$ is even (aka if $k=4l+1$) otherwise it goes:$$\to 27j+26\to 81j+79$$ which only divides by 2 twice if $j=4m+1$ otherwise it goes $$\to 162m+161\to 486m+484\to 243m+242$$ which ... you get the drift. we can in theory continue to do this endlessly with conditions. That would mean in theory we can concoct numbers that go arbitrarily long without 2 divisions by 2 at once. We can also use this to show, the only way such a number is the lowest part of a cycle, is if 16k+12 or higher power of two multiplier links up to a number $4p+1$ going backwards.

answered Feb 04 '20 at 19:19

1

13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096*z + 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095 with $z=3$ works to more than 512 iterations until it hits 2 divisions by 2 ( double checked this time). – Feb 04 '20 at 19:50
1

Arbitrarily isn't infinitely, is it? I can make the Collatz go arbitrarily long by setting arbitrarily long strings of bits, e.g., 0x7ffffffffffffffffffffffffffffffffffff ... but not infinitely. – Chris Miller Feb 04 '20 at 20:07
no but until you can prove it hits a number below the original in decending ( it needs a large decent to do that) you can't prove it won't hit another arbitrarily climbing sequence to push it higher. – Feb 04 '20 at 20:13
In fact, it takes 3242 iterations to come back to below itself, meaning unless it hits a lower sequence that climbs back above it, it's not in a cycle, or a climb forever sequence. – Feb 04 '20 at 20:20
I realize I can't prove this conjecture anymore than I can the Collatz. This results in way longer series and way higher ascensions than vanilla Collatz, and, so far, no collisions. Without collisions, probability should (and so far has) always brought the series back to one, just as probability can be used to prove huge primes. So, isn't proving the impossibility of collisions the problem? – Chris Miller Feb 04 '20 at 20:27
2

it's deterministic, it's not probabilistic mathematics. Also Collatz has been tested to at least 60, possibly 70 bits for the start number. Other generalizations of Collatz like $3n-1$, fail early. Collatz hasn't. The hard part is coming up with a proof, (which is not equal to a bunch of calculated examples). Your attempt depends on Collatz in that every second odd number in the normal Collatz, gets replaced with 1 maybe 2 divisions unless it's 1 mod a higher power of 2 than 4. – Feb 04 '20 at 20:38
Never meant to present my testing as proof, any more than testing the Collatz to 1000000 bits would constitute proof of it. That sort of testing can only disprove. And thanks, that does exactly describe this variation, and generally variations with subsequent odd divisions and larger multipliers, none of which I've been able to disprove. – Chris Miller Feb 04 '20 at 20:51
every time you do a number ×2+1 the number of steps until you have two divisions increases by one – Martien de Jong Jul 16 '22 at 00:45

Collatz extensions

1 Answers1