Fun w/math: Collatz Conjecture

Greeting posters and readers alike!

I have posted several math threads and we get about 3 pages in and get stuck on "how" the thing works. Mostly it is my fault for not being a thorough expert on several branches of modern math.

But this is different. You can teach this to second grade students!

Lothar Collatz found a simple algorithm: given any integer, n, check to see if it is even or odd (is there a remainder when divided by "2", if there is a remainder of 1, it is odd), if it is even, divide the number in half, if it is odd, multiply by 3 and add 1 to it. You get new numbers back and check them. Collatz said, that given any number that if sent through enough times it will eventually reach 1.

Here is what the function looks like:

Note: I have taken a short cut because the odd number part spits out an even number, so why not halve it first? Plus I am using modular math (the "mod" which means "just look at the remainder after dividing").

It is almost a simple party trick! Try it yourself. I have done this several times and convinced myself that that yeah, you will eventually reach one. But ask any real mathematician and they stay away with a 10-foot pole!!

Experienced mathematicians warn up-and-comers to stay away from the Collatz conjecture. It’s a siren song, they say: Fall under its trance and you may never do meaningful work again.

The Collatz conjecture is quite possibly the simplest unsolved problem in mathematics — which is exactly what makes it so treacherously alluring.

“This is a really dangerous problem. People become obsessed with it and it really is impossible,” said Jeffrey Lagarias, a mathematician at the University of Michigan and an expert on the Collatz conjecture.

Collatz Conjecture has remained unsolved since when it was stated in 1937.

In the 1970s, mathematicians showed that almost all Collatz sequences — the list of numbers you get as you repeat the process — eventually reach a number that’s smaller than where you started — weak evidence, but evidence nonetheless, that almost all Collatz sequences incline toward 1.

Obsessed is the least of it! They started counting sequence lengths and using probabilities and all kinds of crazy functions to shave the problem down. And there it sat until one of the modern era's greatest talents, Terrance Tao, from UCLA, published a paper in one of the largest jumps on the problem since the 1970s' (to see a real math paper and get really scared!):

arXXiv.org: Almost all orbits of the Collatz map attain almost bounded values; arxiv.org:1909.03562.

Earlier this year one of the top mathematicians in the world dared to confront the problem — and came away with one of the most significant results on the Collatz conjecture in decades.

On September 8, Terence Tao posted a proof showing that — at the very least — the Collatz conjecture is “almost” true for “almost” all numbers. While Tao’s result is not a full proof of the conjecture, it is a major advance on a problem that doesn’t give up its secrets easily.

“I wasn’t expecting to solve this problem completely,” said Tao, a mathematician at the University of California, Los Angeles. “But what I did was more than I expected.”

Quantamagazine.org, Dec. 11, 2019 - Mathematician Proves Huge Result on ‘Dangerous’ Problem.

Read the article as they do a better job of explaining it. But what Tao did was to assign a "weighted value" to the starting integer, n, and created sets of these integers. Then he shows how these sets are pared down by the Collatz function. But he did not solve the conjecture.

Why?

Notice the term, "Almost all"

He did not solve it for all n but "almost all" n.

I read this on Monday and thought it was decent read. I tried to read the alphabet soup that Tao's paper is and get the general idea but I am not down with set theory like he is and don't understand all the function notation so I can "see" what is happening to the individual integers (or even what the family of integers looks like, for that matter).

Then I check the arxiv today and see this:

arXive.org - Verification of Collatz Conjecture: An algorithmic approach based on binary representation of integers. arxiv.org:1912.05942.pdf.

Here, some computer scientists from India, took the integers, turned them into binary numbers (quick review. 00 in binary is "0" in integer form; 01 is "1'" in integer form; 10 is "2" in integer form; 11 is "3"...). They then flipped them around so the large portion of the integer in binary form is on the "little end" (technically, we call it "little end-ian" as opposed to what I just showed which is "big end-ian" which I guess now makes me a racist! lol)…

Anyway, there is a 7 page proof of the Collatz Conjecture (btw, Tao's is 42 pages of dense set/functions).

See, math is not hard to understand. It is just really hard to write about in a language everyone can speak!! Especially when it is so easy to state that a 2nd grader can "get it" why can't it have a "simple answer"??


xkcd.com - Collatz Conjecture.

TEOT's Conjecture: Nothing meaningful can be said about the Strong Collatz Conjecture!



So have you ever heard of this one? Ever get caught under its spell? Is this still scary math to you? Or are you saying, "H3ll yeah! Got me a new way to bet people at the bar for free beer now!!"

Love me some math! Ty. I never heard this one before.

"He did not solve it for all n but "almost all" n."

One could argue he wasted his time and got no closer to a solution, when there are infinite numbers not equal to n, no?

a reply to: TEOTWAWKIAIFF

a reply to: TEOTWAWKIAIFF

Experienced mathematicians warn up-and-comers to stay away from the Collatz conjecture. It’s a siren song, they say: Fall under its trance and you may never do meaningful work again.

Yeah, like I need a math problem to stop me from doing meaningful work. I can stop doing meaningful work over a bottle of tequila, a cute puppy, or a rerun of Gilligan's Island.

a reply to: hombero

Yeah, the answer I have come up with is "all n" and yes, Collatz will always cycle to 1.

The answer is kind of tricky in that the way the conjecture is shown get you thinking about in one way. The way to think about it is from the "10,000 foot" view. Then it become apparent what is happening.

And yes, a lot of mathematicians have spilt a lot of ink on this one! And like I said, Tao's paper has way too much stuff happening for me to wrap my brain around it. He sets up another function for his family of weighted integers integers and show that Collatz cycles to 1 for those. But there are outliers to those sets that he cannot correlate. It is a might effort and better than anyone else to date. So not really a wasted effort but a great example of how a mathematician thinks about problems.

I like it because it is easy to understand but hard to prove if you are not wearing rose colored glasses!

This will be an aside to my paper that may make me either a laughing stock of the math world or Matt Damon from Good Will Hunting!!

I think interacting with so many great minds right here on ATS and getting the other side of things has been a great training ground since the mathematicians can get a bit b1tchy when their life's work gets upset by an "outsider".

All I need is a working computer (or tablet... just something bigger than my phone) and I will be off to the races. Swimming with the big fishes. Suffering the slings and arrows of outrageous fortune.

Thanks for reading!

a reply to: VictorVonDoom



I think it is meant as "mathematician doing meaningful math" which is another argument in of itself!!

a reply to: TEOTWAWKIAIFF

An odd number multiplied by three will always be an odd number. Add one for an even number and divide by two. You'll end up with another even number half the time over time and divide by two again. Basically, the function doesn't allow a solution of anything other than one and ensures a natural number as the result of each step.

Anyone who has spent 5 minutes on it and can't see that deserves to waste their time.

In my opinion.

ETA: the only other result is infinity, which is impossible to prove.

Reminds me of Kaprekar constant.

Pretty cool, I love stuff like this

a reply to: sine.nomine

That is “for all n” is so hard to prove when you charge straight ahead.

You are on the right track!

It is the “infinity” that makes this question so appealing to an answer.

Like I said, lots of ink spilt on it.

I think that the xkcd comic sums it up nicely. And thanks for being perceptive to see the “conjuring trick” that is there! I think most people are missing the point on what you said and are being “proud” of their math skills instead of wondering what is being asked here.

I think that the really big question, the Riemann Hypothesis, also has this problem. Not a 100% sure... just a hunch.

Sometimes being “lost and n the weeds” makes you question the “why” or in this case, the “what” and if you are lucky, the light goes off and then... what??

I’ll say this, I figured it out back around 2002 and waited for years (signed a NDA and IP agreement with my employer that they “owned even my innovations from my brain”) for somebody else to do the same. But all these years later we “almost all” as an answer!

Universe is trying to get me to move by these articles but I wish She would give me a push in the wallet instead!

Universe has a sense of humor!

a reply to: TEOTWAWKIAIFF

I suppose I'm confused about to what you're referring when you say in 2002 to you figured "it" out. Are you talking about a specific equation or function or something else?

Did you mean to say after all these years we [have] "almost all" as an answer? That paragraph confused me.

In the end, referring back to the original formula, I guess I don't see what application we'd have to knowing another answer anyway. Seems to be one.

originally posted by: TEOTWAWKIAIFF
a reply to: sine.nomine
It is the “infinity” that makes this question so appealing to an answer.

You'd never find it because it can't exist. Not with only natural numbers. It's just a game of plinko til it reaches the bottom.

a reply to: TEOTWAWKIAIFF

And that dear children is why I don't do math....
Because ¿huh?
Let's take 2=n ; 2/2=1 ; or n= 2 mod 2 = 0
5=n ... 16/2... 8/2...4/2...2/2=1 ; n= 16 mod 2 = 0

I seriously don't understand this. Because every odd integer when added 1 becomes even...
I'm #ing confused? What is this good for? Why?
I don't see a problem I don't understand the approach and in my world the conclusion is false both mod are 0...
# math

Oh wait 5 mod 2 = 1
Okay so that's true...
I still don't get what on Earth the ×3 would be necessary for since plus 1 alone is doing the trick?
I don't get math...

a reply to: Peeple

Let's say n = 19.

(19 * 3 + 1) / 2 = 29. Not an even number. The divide by two is part of the odds category, and if the result is even, you divide by two again and again until it's odd again. Essentially, you're taking long-run casino odds, and the house always wins. The odd numbers only have a chance of increasing by a little over 1.5 (less than double), whereas the evens decrease by 2 (half). So over time, no matter what the n equals, it'll reach it's lowest value, which will always be one.

It doesn't matter which number you choose, or how high because it's infinite. You'd only be lengthening the process to reach 1.

Basically the formula favors decreasing numbers, and the formula only allows for decreasing numbers to end at 1.

To say the Collatz Conjecture is "unsolved" is kind of dumb. It is solved. It's 1.

It is a fun little formula though.

originally posted by: sine.nomine
To say the Collatz Conjecture is "unsolved" is kind of dumb. It is solved. It's 1.

I think the "unsolved" translates to "lacking rigorous proof", rather than "I don't know the answer". The unsolved conjectures seem to be of the form "here's what I think the answer is, how can we rigorously prove this is the correct answer?".

That's also the case for these other conjectures for which a one million dollar prize is offered if you can provide proof:

Hodge conjecture
Birch and Swinnerton-Dyer Conjecture

Someone already solved another unsolved conjecture and would have won the million dollar prize, but he refused to accept it saying it was unfair because he built on the work of another mathematician who deserved at least equal credit. I don't know why he didn't just accept the prize and give the other mathematician who deserved credit half of it, that would make more sense, wouldn't it?

Russian mathematician rejects $1 million prize

Is there any prize offered for solving the Collatz Conjecture? If so, I'm not aware of it.

a reply to: Arbitrageur

The prize for Collatz is about 1,000 US$. That is a continuation of an earlier prize of $500. It might be higher.

The Russian guy is a legend!!! He rules! And to walk away is the punk rock attitude that I aspire to.

My proof is steeped in another explanation that to explain would be duplicate work. I hate “working stupid” and repeating myself. So my proof is a paragraph, about a 1/3 of a page, but is an aside... a minor detour.

Maybe I should publish my proof and use the money to buy some computer that works and then take over the world!!

-Pinky and the Brain

a reply to: Peeple

My deepest Peeps,

The “conjecture” is more of a “conjuring trick” that makes people look at the leggy blonde assistant instead of the “magician” palming the card!

The weird thing is that this works. And people cannot understand why. It is kind of silly, like I said that it is a party trick, rather than a math puzzle.

Major hint to life... the answer is in the question!

a reply to: Arbitrageur

Yeah, that's fair. You're right.

originally posted by: TEOTWAWKIAIFF
a reply to: Peeple

My deepest Peeps,

The “conjecture” is more of a “conjuring trick” that makes people look at the leggy blonde assistant instead of the “magician” palming the card!

The weird thing is that this works. And people cannot understand why. It is kind of silly, like I said that it is a party trick, rather than a math puzzle.

Major hint to life... the answer is in the question!

That's funny because I was going to mention how I'm pretty sure it's used in some card tricks.


ETA for fun:

a reply to: sine.nomine

Yeah!



“Say Brain, what are we going to do tonight?”

I'd like to see this run backward in a tree similar to the cartoon in the OP, but reversed.

That is, start with 1. Double it; you get 2. Double it to get 4, and so on.

Eventually you get to a number (such as 16) that becomes a branch in the tree. That branch happens because (16-1)÷3 = an integer (5 in this case). So at 16 the tree branches off to "5" and "32".

The set of numbers (like 16) that, when 1 is subtracted from them, would be a multiple of 3 ([n-1]÷3 = an integer) alternates between even and odd (4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, etc.). So not every number in that set would represent a "node" on the tree that needs to branch. Only the even numbers in this set would be a branching node.

A node on one branch would eventually be a repeat number of a node on another branch. When this happens, the branches can merge at that node.

If anyone feels like writing a program to show this graphically, I'd be interested to see it, and would be interested to see if this reverse approach gives any insight into the Collatz conjecture, such as any patterns, including patterns where the nodes that are repeat numbers on other branches are merged.

a reply to: Soylent Green Is People


Illustration by Edmund Harriss, coloured in by Tiffany Arment

Many math problems become easier when one allows a small number of exceptional cases to behave badly and one is willing to settle for controlling almost all cases, I showed that one could move this intermediate milestone to be as close as one wishes to the final goal 1… for almost all n.

Terrence Tao

From: NewScientist.com - Baffling maths riddle that looks like a pile of worms almost solved.

The "pile of worms" or "hydra" is the Collatz function mapped out.


Collatz fractal, public domain image by Pokipsy76
Forbes.com - An Easily Stated Problem With No Solution In Sight.

Here, someone took the Collatz function, extended it to the complex plane, then mapped what the results were... and got a fractal!! How cool is that??!

I know it is not your idea of an inverse tree but both are pretty cool. And shows that repetitive (if not self-reflexive) operations upon something as simple as integers can yield something that looks like art!