Exploring Variations of the Collatz Conjecture: A Computational Approach

[Chris Miller]

TL;DR Summary

Might variations of the Collatz conjecture help me understand how/why it works?

The Collatz problem is perhaps the only unsolved math problem I actually understand. It "feels" like a proof would be trivial, though obviously it isn't. Been playing with different variations in hopes of understanding it better. Is it a set problem (proving there's no intersection between two sets until 1 is added to each)? An algorithmic proof maybe? Probability also seems to play a part.

The following pseudo-code also converges on 1 for every huge random integer I tested, but sometimes quite gradually, with long upwards trends, before dropping to repeat, with 1 always being the lowest.

t = huge_positive_random_int()

while t>1
    if t is even
        t=t/2
        if t is odd
            t=(t+1)/2
        endif
    else
        t=(t*59)+1
    endif
endwhile

 

[jedishrfu]

I think its far deeper than noticing a pattern in various number cascades. As an example, any power of 2 will cascade directly to 1.

Perhaps by looking at cascades of numbers off a set delta from a power of two number will show a pattern. Or you will see more patterns inside of patterns.

Its an interesting sequence though.

 

[Chris Miller]

Thanks. Agree, the patterns themselves probably won't shed much light. But how they're generated, I'd hoped, might. Contriving start values might, too, though powers of 2 aren't useful. Coercing odds in the series upwards to even appears to be key. Ascending in bigger steps (e.g. 59x+1 vs 3x+1) as here results in 5 to 10 times the number of iterations required to drop to 1. Exploring the limit here might suggest direction. If it were just a relentless manifestation of probability, I'd think there'd be exceptions out there somewhere.

 

[fresh_42]

You can join the project which searches for counterexamples on a distributed net:
https://boinc.thesonntags.com/collatz/index.php
Their initial point was: 2,361,183,346,958,000,000,001
And Wikipedia has a lot of statistics, too:
https://en.wikipedia.org/wiki/Collatz_conjecture
And on the German version (let e.g. Chrome translate it) we find interesting things as:
The conjecture is confirmed up to $87\cdot 2^{60}$ by 09/2017.
https://de.wikipedia.org/wiki/Collatz-Problem
Tao has proven a strong partial solution in 2019:
https://arxiv.org/abs/1909.03562

You see, the problem is on many radars.

 

[Chris Miller]

Thanks for the links. I was aware, from previous posts here and from searches that the problem was addictive. Given there are infinite integers, confirming it to some finite one still leaves infinite possible contradictions and so doesn't really prove anything, does it? Brute force searching for counterexamples is probably futile, especially if the conjecture is true. Whenever I approach even a simple problem, I like to tackle it on my own as much as possible before seeing where others have gone. This helps me better appreciate and understand their work. (It's also why I never fared well in school where solutions were kind of force fed me, often before I really understood, much less appreciate the problem.)

 

[mfb]

Checking a finite number of numbers is not a proof but it is some indication that it might be true. Sure, there are conjectures that have gigantic numbers as smallest counterexamples, but they are rare.

 

[PAllen]

Summary:: Might variations of the Collatz conjecture help me understand how/why it works?

The Collatz problem is perhaps the only unsolved math problem I actually understand. It "feels" like a proof would be trivial, though obviously it isn't. Been playing with different variations in hopes of understanding it better. Is it a set problem (proving there's no intersection between two sets until 1 is added to each)? An algorithmic proof maybe? Probability also seems to play a part.

The following pseudo-code also converges on 1 for every huge random integer I tested, but sometimes quite gradually, with long upwards trends, before dropping to repeat, with 1 always being the lowest.

t = huge_positive_random_int()

while t>1
    if t is even
        t=t/2
        if t is odd
            t=(t+1)/2
        endif
    else
        t=(t*59)+1
    endif
endwhile

I would think Goldbach is the most trivial conjecture that is no closer to proof than it was hundreds of years ago.

 

[Chris Miller]

Checking a finite number of numbers is not a proof but it is some indication that it might be true. Sure, there are conjectures that have gigantic numbers as smallest counterexamples, but they are rare.

You're probably right. Especially since all integers up to 60 or so bits have been tested. So any collisions/loops would have to happen in larger integers, which since they tend to diverge as they increase would seem less probable. But still possible.

 

[Chris Miller]

I would think Goldbach is the most trivial conjecture that is no closer to proof than it was hundreds of years ago.

Yes, I'm familiar with it. Even though it's easy to understand, it strikes me as a lot harder to prove.

 

[pbuk]

By coincidence I have been using the Collatz conjecture as the proof of concept for a website I am working on. It needs another couple of weeks spare time work really, but as this opportunity presents itself...

The site, which aims to increase interest in computational mathematics by "doing it" right before your eyes is here.

 

[Chris Miller]

Hey pbuk! Nice idea for a site. There seem to be lots of interesting hail stone type series you can generate by tweaking the Collatz algo. E.g., test for an odd after dividing an even, and if it's odd, add 1 and divide again. If, however, the original test was odd then multiply by 59 (instread of 3) and add 1. In this case, multipliers larger than 59 tend to ascend to infinity, whereas lower multipliers reduce to 1 more quickly. (I wonder why 59 is the Goldilocks number here?) If you test for up to two consecutive odds inside the even block, the ideal multiplier seems to be around 16383 (i.e. t=t*16383+1). But whether the series decends (always to 1) or rises toward infinity, there seem to be no collisions (repeated test values).

Here's output from the Collatz (odd checks=0 w/ multiplier=3) for the test hex value $123456789.

start: 33 bits 123456789
max: 35 bits 67AE147B4
end: 1
loops: 265

This output is from the code I posted here (the odd checks = 1 w/ multiplier=59 variation) with the same test value.

start: 33 bits 123456789
max: 263 bits 4CF7E321231F20E1E57C3846A3D0CAA84136072A3912CB8AA6E65630997D290358
end: 1
loops: 11381

The odd checks=2 w/ multiplier=16383 variation is even crazier.

Anyway, I just thought it might be interesting to let users on your site input these two parameters and roll out their own Collatz series?

Here's the pseudo-code less any output display or collision and other testing:

// tweak these
#define ODD_CHECKS 1  // 0 for regular Collatz
#define MULTIPLIER 59  // 3 for regular Collatz (must be an odd number)

test=0x123456789 // or whatever
while test>1
    if test & 1 == 0
        test=test/2
        o=ODD_CHECKS
        while o>0
            o=o-1
            if test & 1 ==0 // even
                exit // loop
            endif
            test=(test+1)/2 // now even
        endwhile   
    else
        test=test*MULTIPLIER+1
    endif
endwhile

 

[pbuk]

Anyway, I just thought it might be interesting to let users on your site input these two parameters and roll out their own Collatz series?

You do realize you can edit the code on that site yourself to do that? But you are right, it does need another code section for 'Configuration' as well as 'Setup' and 'Loop'. I'm reluctant to spoon-feed users by giving them boxes to put input in - the idea of the site is to encourage interest and learning in computational and recreational maths, not provide a 'black box' for playing with sequences, as will become clear when I have got it ready for release (perhaps I should have kept it under wraps a bit longer)!

Thanks for the feedback though