Computer scientists attempt to corner the Collatz conjecture

Re:Computer scientists attempt to corner the Collatz conjecture by brundolf on Thursday August 27, 2020 @04:05PM (#24298022)

For fun I went ahead and wrote a little javascript to calculate the sequence. I realized that a lot of work would end up repeated as soon as you encountered an earlier number again (it's directed-graph traversal, really), so it records the ones that it's solved and bails out when it finds them again (denoted by the ->). You can paste the following into your browser console to get a feel for what it looks like.

    let memo = {}

    function conjecture(n) {
        let str = "";

        while (n !== 1) {
            str += n + " ";

            if (memo[n] != null) {
                str += "->";
                return str;
            } else {
                if (n % 2 === 0) n = memo[n] = n / 2;
                else n = memo[n] = n * 3 + 1;
            }
        }

        str += n + " ";

        return str;
    }
    function rangeTo(end) {
        return new Array(end).fill(null).map((_, i) => i + 1)
    }

    for (const n of rangeTo(1000)) {
        console.log(conjecture(n))
    }

A neat thing is that this terminates (at 1) for seemingly every number you try (I disabled console-logs and the process terminated for every number up to a range of 10,000,000, which is as high as I tested). It's just the formal proof that missing. There also seems to be a vague pattern to the results, but that may just be cloud-pictures.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by schoen on Friday August 28, 2020 @12:48AM (#24301453)

> the process terminated for every number up to a range of 10,000,000, which is as high as I tested

Other people have taken this experiment a bit further already:

https://en.wikipedia.org/wiki/Collatz_conjecture#Experimenta...

> As of 2020, the conjecture has been checked by computer for all starting values up to 2⁶⁸.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by vecter on Friday August 28, 2020 @04:06AM (#24302478)

> It's just the formal proof that missing.

That's the only thing that actually matters. You've demonstrated something analogous to the following: "Claim: there are no numbers larger than 100,000,000,000,000,000." You've then gone and checked all the numbers from 1 to 10 million, concluded that it's true, and then just say that we're missing a formal proof. I don't mean to be rude, but from an actual mathematical point of view, you've basically demonstrated nothing.

10 million is mindboggling tiny when it comes to all the numbers. Consider this counterexample to Polya's conjecture: https://www.youtube.com/watch?v=eQCUPQdi6DY

Or so many other examples: https://math.stackexchange.com/questions/514/conjectures-tha...

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by throwaway357920 on Friday August 28, 2020 @10:16AM (#24305098)

>Claim: there are no numbers larger than 100,000,000,000,000,000.

https://en.wikipedia.org/wiki/Ultrafinitism

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by brundolf on Friday August 28, 2020 @10:40AM (#24305406)

> I don't mean to be rude

Well that's how it comes off. Obviously I didn't think I'd made some breakthrough in five minutes with some JavaScript, and obviously I know that the formal proof is the important thing. I was just poking at the phenomenon and expressing my curiosity. There's no need to be so eager to jump in and shut that down.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by thomasahle on Friday August 28, 2020 @03:30AM (#24302289)

> the process terminated for every number up to a range of 10,000,000, which is as high as I tested. It's just the formal proof that missing.

As well as the rest of the numbers between ten million and infinity.

And I suppose, an understanding of why.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by smabie on Friday August 28, 2020 @12:44AM (#24301441)

A recursive memorized solution would be more elegant. Or even a mutually recursive solution.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by brundolf on Friday August 28, 2020 @11:01AM (#24305695)

It would also be significantly slower and potentially limited by stack depth. Even with the memoization some of these sequences get pretty long.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by smabie on Friday August 28, 2020 @05:18PM (#24310080)

I mean, a tail recursive solution wouldn't be.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by rowanG077 on Thursday August 27, 2020 @05:42PM (#24299020)

Just to let you know the memoization technique you used is called dynamic programming.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by nickysielicki on Friday August 28, 2020 @02:08AM (#24301831)

"Dynamic programming" is such a dumb name for what it is and I hope that we can all eventually stop calling it that.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by waterhouse on Friday August 28, 2020 @02:47AM (#24302025)

Emphatically agreed. For those not aware, the person who chose the name (for what were originally called "multistage decision processes", which is far more descriptive) says he chose "dynamic" in significant part because it sounded impressive to a hard-nosed boss:

"... It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities." https://en.wikipedia.org/wiki/Dynamic_programming#History

Also, by the way, to the extent that "dynamic programming" has a definition (the words have little to do with what it means, so it's hard to fix the term to a specific definition), it generally refers to a superset of memoization. So memoization is the more specific term, and should be preferred.

I think we may be able to help kill usage of the term by observing that its initialization, DP, which some people are fond of using, has a much more graphic alternate meaning. Then modern puritanism may make people reluctant to say it anymore.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by WORLD_ENDS_SOON on Friday August 28, 2020 @02:42AM (#24301998)

The history behind the term is pretty interesting to me: https://en.wikipedia.org/wiki/Dynamic_programming#History The original research on the subject was published in engineering / optimization as opposed to computer science, and the term "programming" was used differently there ("linear programming" and "quadratic programming" for example). Now we think of it not as an optimization problem but as an algorithm design technique, but the name still stuck around.

[ Parent | on HN ]

Re:Computer scientists attempt to corner the Collatz conjecture by brundolf on Thursday August 27, 2020 @07:52PM (#24300007)

I'm aware, I was just commenting on it as an interesting trait of the problem. There might be an n+1 aspect, where if you can prove that each sequence will eventually reach some previous number that reduces to 1 then that higher one will too

[ Parent | on HN ]