The Collatz Conjecture... but in Binary

[@ComboClass]

In this episode, I explain the unsolved question of the Collatz conjecture, and then show some binary shortcuts and negative extensions to the problem. Thanks for watching! Make sure you’re also tuned in to my @Domotro channel where I put out various bonus content in between these main episodes (and check the description here for other cool links).

[@maiki5962]

Try starting with zero. Infinite loop of splitting zero in half which 0/2 = 0.

[@TymexComputing]

I hate this classes.. but i cant miss it and have to attend it. The pressure of sth falling apart and broking is JUST A HELL FOR AN EGINEERING BRAIN! DONT DO IT IN THE NEXT EPISSEDODE please :)

[@FrankHarwald]

What if current math does have all the tools neccessary to solve the Collatz conjecture but people just hadn't have the right ideas yet?

[@TymexComputing]

@@FrankHarwald Well - i advise you to check out Kurt Gödel's work - his tools including prime numbers :) - it makes a lot of possibilities to think about what else could be possibly correct but unable to prove :)

[@impactrgpdformationrgpd8785]

Very good approach indeed....now let's talk about a Rabbit and a Tortoise trying to prove once and for all that given any length of a racetrack...and any handicap for the rabbit at start of the race...the rabbit ALWAYS ends...catching up with the tortoise ! We can talk about it if you want....thos two rabbit and tortoise have a lot to tell us about how this conjecture behaves ! And its very fun !

[@tristanridley1601]

Looking at this in binary is sort of the obvious way to simplify, but most youtube videos seem to ignore it. This feels like it should be such a classic math puzzle. "Oh, convert the base and it's easier. Well, we can consider what the exception would have to look like." If I came across this problem randomly I'd think confidently that I could solve it in a day. And then you look at the number of geniuses who dumped decades into this...

[@PaulMiller-mn3me]

You ruined me with different bases… whenever I hear an interesting fact about numbers now, my first response is “that’s only because we arbitrarily count in base 10” !

[@ComboClass]

Some facts are base independent but yeah some other facts are just arbitrarily because of base ten haha. Base six would be better :)

[@DanielTaber-p7f]

Surely that's a baseless conjecture

[@Fictionarious]

@@ComboClass Senary supremacy! Based.

[@Mik1604]

Maybe not totally arbitrary since we have ten fingers.

[@neologicalgamer3437]

​@@Mik1604ancient Egyptians used base 12, the Welsh and Inuit, base 20, and one area uses base 27! There are countless examples

[@trixelpixel5196]

Every time I watch your channel, I’m astonished by how underrated it is. You explain so many things in such a fun way that keeps me interested! Thank you! :)

[@QP9237]

If I told elementary school me that watching a person talk about math/numbers was entertaining/fun, I’m sure I’d call myself a moron… but here I am anyways 😂

[@Asterism_Desmos]

Same, it’s so entertaining

[@sonicwaveinfinitymiddwelle8555]

this is made for kindergarten if you didn't know

[@josephrissler9847]

The typical way to extend this to the complex plane is to use trig functions. cos²(xπ/2) is 1 for even x, 0 for odd, and sin²(xπ/2) is the other way around. So the collatz function is collats(x) = cos²(xπ/2)*(x/2) + sin²(xπ/2)*(3x+1). This gives you a function which matches the collatz operation on the integers, but can be applied to all complex numbers. The neat thing about this, is you don't *have* to use trig functions for this. You can use any functions with the same integer values. One of my favorite tricks when playing with collatz fractals (using "Xaos", which you can get for free) is to add in sin(xπ)*something. sin(xπ) is 0 at all the integers, so you add literally any function to the mix and get a collatz function that matches at the integers.

[@ethanbottomley-mason8447]

Sin(pi * x) is not 0 at every integer, sin(2pi * x) is.

[@redpug5042]

@@ethanbottomley-mason8447 sin(0) = 0, sin(pi) = 0, sin(2pi) = 0. sin is 0 at every integer multiple of pi.

[@ethanbottomley-mason8447]

@@redpug5042 You are correct.

[@diophantine1598]

I need to try this…

[@nicolascalandruccio]

Nice way to extend it into C

[@myownlittlworld9427]

I showed this to a friend, and they said, “that makes sense, but what’s with the clocks?” If you haven’t explained the thing with the clocks to anyone yet, please never do and keep it a secret. Mysteries make the world a more beautiful place.

[@jemmerl]

He's trying to tell us that he has been trapped in an infinite time loop and forced to keep making entertaining educational videos for all eternity. Obviously the conveyed point is that we need to destroy the timeline (breaking the clocks) to free him :)

[@JON-es4wk]

@@jemmerlthe only way to escape is for us to solve 3x+1

[@dickrichard626]

He just likes clocks apperently and there is a video where he uses them to make some points and talks about using different numbers on clocks. Clocks have 12 hours and 12 is an important number to math people, because it is a "highly composite" number and counting in base 12 is arguably better than base 10. The only problem is you basicaly have to relearn math all over again just to be able to think in base 12.

[@MrCheeze]

You mentioned that Collatz is one of a family of similar functions. Surprisingly, those Collatz-like functions show up a lot in research on the Busy Beaver problem - the problem of finding the computer program of a certain number of characters, that computes as many steps as possible before halting (without falling into an infinite loop). It looks like in some sense, the Collatz family may well exhibit the most complexity of ANY mathematical problem that has such a simple description.

[@karlwaugh30]

that's interesting because (& correct me if I'm wrong) but the busy beaver function is often defined in terms of Turing Machines & this binary representation seems to be a lot more fundamental (& less arbitrary than the 3x+1 seems) in terms of binary representation (rather than arithmetic values)... Could you explain more of the "most complexity" and what that really means??

[@MrCheeze]

@@karlwaugh30 Nothing other than the normal busy beaver definition, abbreviated. Collatz-like functions seem to run longer than any other turing machine of equally short definition. We don't know whether Collatz-like programs will always be the champions once we get to longer programs, of course. But if they are, that would imply that just knowing the answer to which Collatz-like programs halt and which don't, would encode a solution to the halting problem (impossible).

[@deemaske9143]

honnestly, i love how your decorative stuff keeps falling or breaking

[@PhilHibbs]

The negative extension is basically a mirror of “3x-1”.

[@drenz1523]

which is another unsolved question!

[@brosisjk3993]

@@drenz1523 nope, 3x-1 is proven false

[@s4ad0wpi]

One thing that's worth noting is that if you've tested every number up to N, then you don't need to check any even numbers up to 2N, because they'll be cut in half to a number below N, which you've already checked! You also don't need to check all the Odd numbers between N and 2N, because several of them were probably already a part of patterns you already proved followed the theorem. So that cuts several numbers off your list. It's almost certainly not enough to be used as proof on its own, but probably a good place to start?

[@jejjiz6162]

You would still need to check all odd numbers between N and 2N, otherwise we can inductively say that "since it works for all numbers up to 1, it works for all numbers up to some arbitrary power of 2". That would mean that every number would work. You're correct in saying that even numbers can be skipped, though

[@BridgeBum]

@@jejjiz6162 I think he's trying to say (a) you do not need to check any previously checked number and (b) some odd numbers between N and 2N have been previously checked.

[@KaiHenningsen]

@@BridgeBum True, but you still need some way to keep track of those odd numbers if you want to use that fact.

[@BridgeBum]

@@KaiHenningsen Agreed, however in practice you have to keep track of every number anyway.

[@piercexlr878]

All numbers 1 greater than a multiple of 4 decrease. Same with all numbers 3 greater than a multiple of 8. There's an infinite family of these relationships, but they have few patterns. Since they decrease they either fall to a number thats 4n+3 or they don't and fall infinitely so you can get away with checking 1/4 numbers

[@Fictionarious]

I've spent way too much time thinking about this problem and will undoubtedly spend even more

[@ChannelMath]

it's wasted countless years of good math research. entire careers even. stay. away.

[@Fictionarious]

@@ChannelMath Oh, I know - its just too late for me. I've gazed too deeply into this particular abyss to be saved.

[@your_future_self]

Yeah! I played around with the collatz conjecture in tree form in base 6 for a while and I noticed that all of the places where the branches split ended in four. Which I beleive means that any number that could be arrived at in a chain witha 3x+1 operation is exactly 4 more than a multiple of 6

[@ethanbottomley-mason8447]

Well you only get 3x + 1 if x is odd. Odd numbers are numbers which are 1 more than a multiple of 2, i.e. x = 2n + 1 for some number n, then 3x + 1 = 3(2n + 1) + 1 = 6n + 4. So yes, any time you multiply an odd number by 3 and add 1, you do get 4 more than a multiple of 6.

[@SirRebrl]

Paused shortly into the video, already having thoughts about what was going to make binary interesting for the conjecture. Decided to pick a random binary number and run through the steps. "Chop off all the zeros" was obvious. I didn't think of your 3x+1 strategy, but I was iterating on a whiteboard and focused on preserving space for more iterations. I did come up with a simple system of counting the 1's belonging to each position, then translating evens to 0 and odds to 1. My partner got home as I was doing that and immediately called me a nerd, so I nerded up and explained what I was doing, including the trick for dividing by 2, comparing it to dividing by 10 in decimal. Was entertained to listen to you run down everything I had just said to her when I resumed the video. =D (My random number ended up being 1625 btw, and I got through 20 iterations, reaching 175)

[@leftylizard9085]

I think base 4 would be a useful one to look into. For example, every number that is a sum of consecutively descending powers of four, all the way down to 1, when multiplied by three with one added, becomes a power of four, allowing it to shrink down to one almost instantaneously. It makes sense when written out in base four: 111111111 × 3 = 333333333. 333333333+1 = 1000000000 which, because this is base four, would collpase down to the four two one cycle. This is what happens in binary when a number consists of just 1010101010101 and so on and so forth.

[@TheWonderfulMageofOz]

i'm bc just foud the same...

[@MarloTheBlueberry]

I've seen Veritasium make a video on this, but I didn't understand it. You made me understand it. Thanks!

[@biozbran8208]

Amazing video, as always. This playing with numbers always fascinates me and I love that there is a math channel dedicated to this.

[@ratlinggull2223]

I've been making a small game about the Conjecture and I actually use binary as a strategy to play it. Nice to see this video popping up now.

[@Gunbudder]

i love this method of framing, and its how i think about it. what you are really looking for is a chain of numbers that never hits a power of two. a power of two is the only way to get back to one. so really its a question about the nature of powers of two and what triple plus one is really doing. is also interesting that you can construct numbers that have a large amount of repeated divisions in a row, but do not directly lead to one. for example if you square 27 a large number of times, then you can find some interesting paths by working backwards.

[@KaiHenningsen]

27 = 3^3, so squaring that is 3^6, and squaring that is 3^12 ... so 3^((2^n)*3).

[@legendgames128]

Seeing how much simpler the 3x+1 stage is in binary, I feel like the solution likes in cutting the complexity of a number down to 1. (For example, 1101010010101000000000 in binary has a complexity of 13 in decimal, because there are 13 bits before the trailing 0s) And this reminds me of p-adic numbers, specifically, the case for p=2. 13=1101(I will list the complexity in decimal, in parenthesis) 1101(4)->101000(3)->101(3)->10000(1)->1(1) So, maybe this could be useful information?

[@TheGuyvatzian]

I wrote a paper on the Collatz conjecture in my senior year of college. I actually came up with the accelerated version of the formula seen in this video by myself after I read published papers on the problem and a lot of them used a modified version of the formula where instead of 3x+1 if odd they'd do (3x+1)/2 if odd, and I was like "psh. cowards. just get rid of the whole thing!" And after looking at the problem that way I realized that the big question in the conjecture is really whether a power of 2 will eventually be reached. This led me down a rabbit hole where I realized that the difficulty in the problem comes in the unpredictable way that the 3x+1 step messed with the prime factorization of x. But while that took me a while to realize, it's really not that much progress. To find a pattern in the Collatz conjecture is to find a pattern in prime factorizations

[@legendgames128]

@@TheGuyvatzian The +1 really messes with things. Multiplying by 3 just adds another 3 to the factorization, but as soon as you add 1, everything goes haywire. What would happen if we tested for big prime numbers? I wonder if that could reveal anything.

[@davidhand9721]

This is the path I've been thinking about, too. However, I don't see the increment as being the difficult part, but the multiplying by 3. Adding 1 to a binary number is very simple: eliminate all the trailing 1 bits, add a 1 bit at the first zero. Multiplying by three, i.e. adding x and x

[@AnthonyFlack]

​@@TheGuyvatzian watching this video, I was also thinking that you may as well make the odd number process be (3x+1)/2, because 3x+1 will always turn an odd number even, so the next step will always be to divide by 2. This makes it feel intuitive that the series will always trend downwards over an arbitrarily long time, since there are the same number of even numbers as odd, and even numbers reduce the total by more than odd numbers add to it, proportionately. So in order to keep going up forever, the sequence would have to land on more odd numbers than even, all the way up. And half those even numbers are doubly even, and half of those are triply even... and of course if you ever land on a power of 2 it's game over. Is there a streak somewhere that favours odd numbers all the way up? Again it seems intuitive that this couldn't work, but intuition isn't proof. My suspicion is that in order to work, a sequence would have to favour odd numbers to the degree that it trends towards landing on only odd numbers as it gets larger. If a sequence ever falls back on itself you have a loop, so if the sequence ever lands on the same number twice, you've won a hundred million yen. But again, it seems "intuitive" to me that you could never reverse a 3x+1 by applying x/2 or more 3x+1, except when x=1.

[@AnthonyFlack]

@@davidhand9721 - I was thinking along similar lines too; if you could show that the operation always trends towards reducing digits, or adding more zeroes than ones... but of course it can't be that simple. This is just how you get hooked into it.

[@skeksis268]

I’ve been working on that binary representation of the collatz conjecture on and off for a few years. It’s quite fascinating and has some nice properties, I should write it up…

[@zrodger2296]

Please write it up, and congratulations if you do. I've found some interesting problems over the last few years and have exhaustively solved them on my computer (cool stuff, but nothing really important) but never really finished them, nor have I written up the results. Well, a new year is coming up...

[@m802001]

The guy knows his stuff for sure. I get that the surrounding chaos stands in sharp contrast to the very ordered nature of mathematics, but all that chaos makes me anxious.

[@BillGreenAZ]

Same here...but then again, I have anxiety issues.

[@dbeast03]

Personally, I think the chaos is rather representative of math and science. For as much as we understand, there will always be much, much more that we may never even come close to solving, as even in simple order and concepts such as the Collatz Conjecture, chaos and incalculability is what makes it an oddball problem.

[@epistax4]

Thanks for making this. A few years ago i found the same thing about treating the problem in binary. It's funny that multiplying by 3 is so easy in binary. You know you've converged as soon as you get a 10101.. pattern. Dropping the trailing 0's super satisfying too. It just doesn't get us any closer. If you want to make things harder on yourself instead, try 3x+1 in prime factors. Dropping to the odd is just as easy as with binary. The 3x is also trivial. But effect of a +1 on a prime factored number is extremely arbitrary. Obviously (or not) every single factor is changed by the +1, in a unpredictable fashion. I've tried to find some sort of physical phenomenon that is model by 3x+1 but nothing.

[@electronlibre7921]

Collatz is also an amazing problem to take a look at as a grammar problem and not a numerical problem. That leads to interesting behaviour of paterns. Where you can really pin point a Rabbit...trying to catch a Tortoise !

[@peterlaloli6279]

Fantastic video, your content is an absolute joy to watch.

[@Tyshun-r6c]

your rule can be represented by the following equation: \frac{x + 1}{2} & \text{if } x \text{ is even} \\ x + 1 & \text{if } x \text{ is odd} \end{cases} This equation captures the essence of your rule: adding 1 to the input and, if the result is positive and even, dividing by 2; otherwise, leaving it unchanged

[@popularmisconception1]

with negative numbers, you're basically playing a 3x-1 version of the game with minus sign as a decorator. but it's a nice example that it might make sense to try out modifications to understand that more cycles can in fact emerge (and how and why). maybe a 5x+1 version where all numbers divisible by 2 or 3 would be ridden of these factors, or 5x+3, or 7x+1 removing 5s, 3s and 2s from prime factorization... btw, prime factorization is also a good way how to think of a number, but adding 1 is tricky with this representation. or is it?

[@ー-ーー]

Here are some axioms I could come up with General: 1. Odd number x Odd number is always results in an Odd number. 2. Adding 1 to an Odd number always makes it an Even number. 3. All Even numbers repeatedly divided by two will eventually turn into a Odd Number. Specific to 3x + 1: 1. In a 3x + 1 sequence the amount Odd numbers will always be less then the amount of Even numbers. 2. There is never two Odd Numbers in a row during a 3x + 1 sequence. 3. As the Even Numbers size increases the amount of divisions by 2 in the sequence increase.

[@lvn5609]

Number 3 is wrong I think. Let's say we have a number that can be factorized as 2q, where q is an arbitrary prime number besides 2. Then, because there are infinite numbers of primes and each next prime number gets bigger and bigger, we can get an arbitrary large even number which can be divided by 2 only once before it becomes odd.

[@LAM1895]

It's been about 2 weeks since I saw the Veritasium video about this and I came to the same conclusions about the binary representation recently. It really simplifies the process and shows where the real problem lies: how do we prove that by doing 3x+1 and removing trailing 0s over and over we will always eventually end up with 1? After investigating the problem in many ways I have the feeling that it is the same process as x+1 but the 3 adds a great deal of complexity. It's easy to prove that repeating x+1 and removing zeros will always end up with a 1 -> 2 loop because you're basically just counting natural numbers and any number can be described as a combination of powers of 2 which is the binary representation. So the question would be: can any number be represented with that added 3?

[@Ak4n0]

Y hay otra cosa muy curiosa: Mirando el penúltimo bit de un número impar diferente a 1, podemos asegurar que: · Si es 1, el próximo número impar dentro de la secuencia de Collatz, será MAYOR que el actual. · Si es 0, el próximo número impar dentro de la secuencia de Collatz, será MENOR que el actual. Por ejemplo: 13 -> 1101 El penúltimo bit es 0. De hecho, el siguiente impar en la secuencia es 5. 17 -> 11011 El penúltimo bit es 1. De hecho, el siguiente impar en la secuencia es 41. Y parece que esto se cumple siempre.

[@ObsessiveClarity]

I tried this problem a lot in high school. I did realize something sort of cool. Btw after multiplying by 3 and adding one you always land on an odd number so u can immediately divide by two. Let o(x) = (3x + 1)/2 Let e(x) = x/2 To represent a cycle of length 2 it must be either e(e(x)) = x or e(o(x)) = x or o(e(x)) = x or o(o(x)) = x Obviously all of these equations *do* have solutions. It’s just they are conjectured to be either 1,2,4,0, part of the negative cycles, or *fractions* (what they usually are). So the question is do any equations have positive integer solutions other than 1,2,4. And you can similarly represent cycles of any length using equations like that. And you can also collapse/simplify consecutive nested e functions easily. And you can learn the nature of simplifying an arbitrary composition of such functions. By writing a program to solve such equations symbolically, you could pretty easily show for example that there are no Collatz cycles of length less than 10, by symbolically solving every possible such nested equation 10 layers deep and seeing that all of the solutions are fractions or 0,1,2,4, or negative. And you can look at their inverses. You can try representing them using matrices, and see it as a vector equation with matrices. Another thing to realize is that even if o(e(o(e(x)))) = x, with x an integer, you must verify that each step of o,e,o,e is working correctly - that e is never applied to an odd number (nor a fraction) and o is never applied to an even number (nor a fraction). Another thing is that you can sort of try to approximate the number of e’s and o’s that ought to be in a valid cycle of a given length whose values are in a given range. Because each e contributes a factor of 1/2 and each o *roughly* contributes a factor of 3/2. So (1/2)^E * (3/2)^O ~ 1 where E is the number of e’s and O is the number of O’s, and the cycle applies all of these to a number only to have it return back to itself. So all that multiplying is basically the same as multiplying by 1. That kinda breaks down because nested O’s do contribute more than a constant +1… you can do the math to see what it really looks like a bit better. Anyways this all obviously didn’t lead to a solution lol but still was interesting for me

[@aaronhorak710]

1 mod 4 is always followed by a smaller odd, 3 mod 4 by a larger odd. Easy to see in binary, the former ends in 01 the later in 11. Been working on properties of assumed cycles and trying proof by contradiction. Enjoyable presentation!

[@johndickinson82]

Something I found to think about: there are triangles of twins( numbers one apart in the Collatz)a represents the top number of the triangle and below it is a+1 and the restriction is a+2 is prime.Twins are vertical in these triangles and reach a connection in the same number of moves as the rest of the twin ex: 20,21 both reach 16 after 3 iterations. I’m not sure why 144, 145, and 146 have this behavior, reaching 94 after several moves. The triangles “start” with a(2^n -1)+(a-2), where the start are the values on the left. PS. a=-1 is an exception but is a triangle . What happens in the middle and on are that when you apply the Collatz sequence to it the twins and connections form. I think I am the first to find these “Collatz Triangles” and that they are helpful to the proof. There are patterns with a+1= 0 and 2 mod4 but I’ll leave those for someone to figure out. -Isaac

[@stickfiftyfive]

"..Whoa! Carlo, the globe is on fire." Indeed.. indeed.

[@claytonhiggins7526]

So glad you did a video on this problem, it's one of my favorite unsolved problems! Though personally I think the collatz conjecture is probably undecidable.

[@piercexlr878]

It feels very decideable, but hard to figure out how

[@muskyoxes]

If it's undecidable, then the conjecture is potentially false. If it's potentially false, then anyone could accidentally pick a counterexample and prove it false. I can't decide if this proves it's decidable

[@claytonhiggins7526]

@muskyoxes This actually isn't the case. Since it's possible some sequence could blow up to infinity, you might not be able to prove it's a counterexample because of its infinite nature.

[@drdca8263]

@@muskyoxes Consider the weaker conjecture: “the collatz map has no other cycles other than the (4-2-1) cycle”. If this weaker conjecture is false, then it has a finite refutation. So, if the weak version of it is undecidable, then the weak version is true. So, if the weak version is undecidable, it cannot be proven to be undecidable. That’s not really an issue though.

[@Gunbudder]

don't you dare Collatz me! i've already spent way more time than anyone ever should studying this dang thing. its a black hole of mental energy!

[@PW_Thorn]

The first time I heard about 3x+1, I immediatly thought that a proof of it can be achieved by seeing parterns and relationships and properties for integers in base 2 and 3. And that's here the first YT video going quite that way 👍

[@Snidbert]

Why do pop math channels always call it the “3x+1” conjecture? Shouldn’t it be the 3n+1 conjecture, since it deals with natural numbers rather than reals?

[@filker0]

Any whole power of 2 reduces to the 1 pattern. If you prove for all non-even whole numbers N that applying the function recursively will at some point yield a whole power of 2, the conjecture is proven. It's been some years since I tackled proofs of this sort of thing, and I doubt that I could have proven this property of the function when I was up on such things, but that's really what it boils down to. A shortcut is that if you are checking successive values, as soon as ((3N' + 1) / 2)

[@delicioushomemadestrawberr8730]

As some people have already commented, you need to check whether it reaches a power of two. At the same time I think that you also need only to check for primes, because the other numbers will at some point reach a prime (at least that's what happens when calculating on my mind). With primes you know that either it's 2 or the next number will be even, so you can do (3p+1)/2, which will be a natural number. If somehow you could prove that it will come to a smaller or equal prime in size, you would have proven this conjecture. (this would be for any prime p except 2, so you would show that for all numbers it decreases in size until it reaches the 1-2-4 pattern)

[@MuffinsAPlenty]

It's not clear to me that you should always reach a prime. Even numbers can be a result of multiplying a power of 2 with a bunch of odd prime numbers. So dividing by the 2's will leave a product of primes in this situation. And the real trick which makes Collatz difficult is how adding 1 affects prime factorizations. If we have an odd non-prime, then will multiplying it by 3 then adding 1 cause it to be a prime times 2? Maybe! But it's not clear to me! If you take a product and add 1 to it, then that shuffles up the prime factorization. Maybe it will be a 2p for some prime p, but maybe it will be 2pqr for primes p, q, and r that weren't in the original number. For example, if you start with 23*1381 = 31,763. (Note: both 23 and 1381 are primes). Now, this is odd, so multiply by 3 and add 1 and you get 95,290, which has a prime factorization of 2*5*13*733. We started with a product of two primes, then we ended with 2 times a product of three odd primes. So multiplying by 3 and adding 1 can _increase_ the number of odd primes present (it can also decrease the number of odd primes present, but sometimes it can increase it, which is what makes this line of reasoning hard). I mean every number ever tried has reached a prime (specifically 2), but it's not clear that this should be true abstractly.

[@manudude02]

I was thinking about the problem in base 4. All numbers that can be written as a series of 1s (1, 11, 111 etc), will instantly lead to a power of 2 (game over). This will be the same for 2s (2, 22, 222) for obvious reasons. Since we are always looking for higher numbers, we would like to hit a sequence where we cannot hit 111111.... from below. This will be the case for any string of 1s which are not of length 1(mod 3). You would need to prove that you can keep away from a solid string of ones somehow. As a bonus, 100..... is game over, 200.... can never be reached from below (since 133...... is never divisible by 3), 300..... will not be a power of 2, and 00... is zero)

[@alikaperdue]

There is a way to go directly to (3x+1)/2 from x, by looking “between” the binary digits of x. Write out x in binary, and then record whether the digit changes or not. There is a flipping rule I can’t describe here. The digits that change vs those that do not plus the pattern flipping rule will result in (3x+1)/2. So in a way (3x+1)/2 is a measure of change and stability of the number x. It’s almost like the derivative of x. * I always use (3x+1)/2 instead of just 3x+1, because the former is symmetric when plotted on a graph. The only reason to use 3x+1 is to make it simpler for beginners to see. So don’t do that and always divide by two. Otherwise analysis is less obvious IMO

[@alikaperdue]

once you see the result is a bit analysis of the input. You can get rid of all number concepts and just work on the bit pattern. A little bit like the way the “game of life” can be played without looking at numbers. The input is a bit pattern that is analyses according to non math rules to produce the new output. It just so happens that the output will be 3x+1 if you think of the input as being x.

[@polyhistorphilomath]

Obviously the definition is in terms of a recurrence relation. This suggests solution via generating function. The key advantage of a generating function approach is that we will definitely know a good deal more about any sequence collectively (such as perhaps that it terminates in a single repeating coefficient 1 or in 4-2-1) than we would about an infinite set of sequences. Otherwise we would have to deal with a sequence for every natural number--and that seems like too much work. For an even number g_0 (assuming we never have to multiply by 3 and add 1), the generating function is G(x)= 2g_0/(2-x). For an odd number h_0 (supposing we never have to divide by 2), the generating function is H = (x + h_0(1-x))/((1-x)(1-3x)). We could solve via generating functions. In fact we could simply add them. The trouble is that we don't have a good way of dealing with the indicator function (1-cos(pi*z))/2 [equivalently, cos(pi*z/2)^2] which we would unabashedly steal from the complex iterative formulation of the problem if possible. Suppose we have a sequence {a_n} with ordinary power series generating function A(x), denoting it {a_n} A(x). For a polynomial function of n, p(n), the sequence {p(n)a_n} is generated by P(xD)A(x) -- meaning we apply the polynomial evaluated at the theta operator (typically denoted z d/dz) to A. However we have a coefficient that is not only a transcendental function but is also of the form f(a_n) rather than f(n). Interestingly we can extend the polynomial coefficient to a transcendental coefficient, but it still must be a function of n--otherwise we really have trouble summing over all c_n x^n. For fun, let's see how it would work. T^t (with t being in R) is the shift operator. It is defined as e^(tD). T^t doesn't quite work as it lacks a factor of x in the exponent--but it can be shown that e^(txD)f(x) = f(x e^t). This would allow us to rewrite our indicator function (again, assuming it were not a function of a_n, but of n) because cos(ux) and sin(ux) have a very concise definition in terms of the (scaled) sum and difference respectively of e^(ux) and e^-(ux). There is yet another issue--we have a purely imaginary value of t for every term, so we cannot simply assume application of e^(txD) (converges/is well defined/has desirable spectral properties) where T^(i alpha) fails. But by examining the shift operator directly maybe we can understand what it might look like for our sums of f(x e^(i alpha)) to be well defined. For a shift along the real axis, addition or subtraction from the argument is sufficient. Ex.: b(x-k) for b(x)=x^2. This shifts as expected. However to shift in the orthogonal direction for a non-trivial function b(x) we would have to first take the inverse then apply the shift vertically and invert back to a function of x. e^(tD) b^-1(y) gives an orthogonal shift, meaning we could take {e^(tD)b^-1(y)}^-1(x) to be the definition of T^it for real t. We are working with multifunctions in this example (b=x^2 has a multi-valued inverse) and the generating functions are only formal power series in reality, so we should be prepared to invert via the Lagrange inversion theorem. Taken together, it all suggests that if necessary we could ensure e^(tau xD) is well defined for arbitrary x and tau (where tau=sigma + it) by (1) composition of y -> y e^t, with the inverse and (2) subsequent composition of x -> x e^sigma with the functional inverse of (1) (or by some analogous procedure). Yet as mentioned this only achieves scaling a sequence by a transcendental function of n, not scaling by a transcendental function of the term a_n. So instead we can change approach entirely. Looking at the Weierstrass factorization of a function r(z) taking all integers of the form m2^k (evens) as zeros, we know this should be 1 at other integers by construction. The numbers m2^k are those which we ultimately want to map to 1 if we want to "immediately remove all trailing zeros from the binary representation". Let's take f(x)=3x+1 so that all odd numbers are mapped to the correct value otherwise. Then to prevent a square hyperbola from developing we ought to introduce an elementary factor E_n(-3x). Then f(x)/E_n(-3x) + (1-f(x)r(x)/E_n(-3x)) ought to converge to 1 under iteration.

[@hkayakh]

Man i love the Collatz Conjecture. So glad you talked about it!

[@leavealoner]

Is this easier to solve by looking at it the other way around? start with the loop, and apply the reverse of both equations to every single number in the number line if it is applicable. like, all numbers can be doubled to see which even number they were derived from, and all numbers can be minus-oned to see if the result is divisible by three. isn't it easier to see wether or not that fills the number line or not?

[@LAM1895]

I tried that for fun. I wrote a Python script that creates a binary tree of all possible paths starting from 1. Here is the heart of the code: # Calculate left child value if (value - 1) % 3 == 0 and 3 < current_depth < depth: left_child_value = (value - 1)//3 if left_child_value % 2 != 0: tree.add_edge(value, left_child_value) queue.append((left_child_value, current_depth + 1)) # Calculate right child value right_child_value = value * 2 if current_depth < depth and right_child_value < 10000: tree.add_edge(value, right_child_value) queue.append((right_child_value, current_depth + 1)) I added a limitation to the value of 10 000 because since we're dealing with powers of 2 the numbers and the spread of the tree quickly become huge so it takes a long time to calculate and render. I came to 10 000 by taking the biggest number in the sequence of 27 and rounding up because that particular sequence is an interesting outlier. If you think about it, 27 is on the same depth as 2^111 which is 34 digits long. If you want to do the same I recommend you render the image in SVG format to eliminate the resolution problem.

[@Tletna]

Oh no, has Domotro been sucked into the neverending story of 3x + 1? It is an interesting conjecture.

[@ComboClass]

Haha. I've been planning this episode for a while (I brainstorm episodes way in advance) and it will probably be my only Collatz-related one for a while (apart from maybe some more bonus content about it on my Domotro channel) but we might return to the topic someday :)

[@insouciantFox]

This is the Explosions & Fire with math and I'm here for it

[@karlwaugh30]

This is fascinating, not least because it seems to move a problem of arithmetic operations behaving kinda chaotically and represents it as a question that seems to sit in symbolic dynamics (not that I have skills in that).... A problem of bits and their overlaps etc. Also there's something nice in the "chop off all the zeros" etc especially as it says 1->1

[@Mihoshika]

"Oh dear. The crazy person in the lab is going into his small tiny yard to talk gibberish again.

[@otonanoC]

Four hours ago this was posted? Lets get it on.

[@mementomori7160]

I love that a few years back when I was in highschool that's exactly what I tired to do, considering it in all of those 3 bases(2, 3 and 6), tho I had no intuition for either, maybe I'll give it a try again soon, I won't discover anything, but it'll be at least fun

[@djsyntic]

I think base six might be an interesting one as not only would multiplying by 3 be "easy", but it would keep some sort of even/odd property by looking at only one digit.

[@trueriver1950]

In ternary (base 3) the 3x+1 step becomes 10x+1, so just add a digit 1 to the end. Testing for odd/even is only slightly harder than in base 2 or 10: because it's an odd base you need to count the number of odd digits: odd numbers have an odd number of odd digits. In base 3 the only odd digit is 1. So you count the ones, ignoring any 0s and 2s. Even easier, count in single digit binary: 1, 0, 1, 0, 1, 0 ... or with the words odd, even, odd, even, odd, even ... My intuition is that that is sufficiently easy to make ternary a better base than base 6.

[@QP9237]

Can you do a video on hypercomplex numbers or the hopf fibration? Always enjoy your videos, so would like to see you tackle these topics!

[@ComboClass]

Thanks! There will be an episode about hypercomplex numbers at some point. Not sure about a hopf fibration episode but it’s certainly possible :)

[@QP9237]

Awesome man looking forward to it 😁

[@44Mat]

Couple months back I asked about the relationship between this equation/function and its plotted graph/points vs the inverse of the equation if it also gives an inverted mirrored graph/points....And what do we call such an equation if the inverse doesn't give opposite answers or plots Replace f(x) by y Solve for y.....I wonder if an A.I hallucination could go with me through this rabbit hole and we loosen up a little and refuse to be rigid when trying to solve this one

[@suan22]

I think we "just" have to prove that if you start this procedure with any positive integer number then it will eventually reach a number in the sequence that is less than the starting number. Then induction would prove that this means every number will eventually reach 1, no?

[@Very.Crazy.Math.Pistols]

I'm not an expert in diophantine equations at the moment, but if a number falls into one of the integer solutions that stand in for x, we're there: solve diophantine 3x + 1 = 2^y.

[@Very.Crazy.Math.Pistols]

Obviously we need to prove that the algorithm / 2 , 3x + 1, will always end up on one of the solutions x, of ( x,y ) 😅 👹

[@vantheman8050]

loving the new season

[@gm2407]

What about factors as well? Will that aid in demonstration of this?

[@BillGreenAZ]

Domotro: "Computers checking a bunch of numbers isn't going to prove something about the infinite amount of natural numbers..." I believe there was one conjecture that fell into this situation of being proven to a large number but was later proven to not necessarily be true. I can't remember the name of the conjecture, but this principle supports your statement.

[@ComboClass]

Yeah there’s a few problems like that, and sometime I might even make a future episode topic about conjectures/patterns that break at large counterexamples. A great written work about a similar thing is “the strong law of small numbers” by Richard Guy.

[@BillGreenAZ]

@@ComboClass That would be great. Thanks Domotro!

[@ethanbottomley-mason8447]

Look up Skewes's number, it is a good example of things failing only at very large numbers.

[@BillGreenAZ]

@@ethanbottomley-mason8447 Thanks for the reference.

[@hancocki]

My world's on fire. How about yours? Oh. well... Hey now, you're an all-star.

[@Ing0s]

These videos are so captivating!

[@lucaspowell8290]

Good shit as always dawg!

[@Kayclau]

If I remember anything from calculus is that going to the extreme always works. So, if the number is 1000000000000...0000001 Then, I'll ad 1000000000000...00000011 And the result will be 11000000000000...0000100 Eliminate the 00 from the end and then ad 11000000000000...000011 That will give me 100100000000000...000100 Continue ->10010000000000...0001 ->110110000000000...0100 ->110110000000000...01 I'm no math expert but, it seems like every number has either a 1; a 2; or a 4 at the end. It truly doesn't matter what number you start with. They all end in a 1 or 10 in binary and if not, the next in the sequence will.

[@lugyd1xdone195]

Interesting that if we do this for P-Adic numbers all of those are suddenly possible. Just a question, if we allowed ourselves to count divergent sums as solvable wouldnt it mean that for infinitely large numbers the number only grows, whereas for finitely large numbers if the conjecture is true the number always converges to this cycle? Maybe theres something with divergences-convergences relevant to this problem?

[@swiddle1]

I'd like to see how this looks in base three and in base six.

[@somedooby]

If there is an infinite loop that is trillions of numbers long or grows infinitely, then surely, starting at a very large number would yield one of those results. I wrote a rust program that checks numbers starting at 2^x +1 through 2^x +1 + 2^y. I checked a relatively small amount of numbers (with y being no more than 24) starting at 2^500, 2^1000, up to 2^9000 but couldn't find one. Needless to say, it isn't easily brute forced

[@normbograham3]

(3x+1) - ( 3x-1) = 2. Yup. 2. Meaning, that they only differ by 2, but, (3x-1), has an early failure.

[@ephemera2]

I am nearly 100% certain that I have at the very least broken new ground on this conjecture

[@danciagar]

Collatz algorithm is nothing more than a bits sorter that links every combination of 1 and 0 with a single bit on the bitmap, and in vulgar base 10, a 2^k integer, just don't remove the zeroes and use a bitwise swap of the added "bitshift left" first left trailing zero.

[@Coldheart322]

I'm wondering if looking at this problem in binary has been done in terms of trying to prove the conjecture, as it feels like the proof becomes a step simpler. Because any even binary number ends in 0, any number written as 10...0 will collapse to 1. So can you prove that for any odd binary number, it will eventually hit a 10...0 pattern? I assume it is still difficult to prove, but could be easier to work with than decimal numbers.

[@lool8421]

i kinda have doubts that it could shoot up to infinity because on average it decreases by x0.75 per operation and to get infinity, you would need some chain that repeats an infinite amount of times however some cycles could exist it's just that multiplication with addition don't go as well as we would like

[@salerio61]

you might have doubts, now prove it :)

[@skunko1871]

Love this video! Super fun to see binary used here

[@berzasperdvisiodei6625]

As far as I can tell, negative numbers will fall into a -4 -> -2 -> -1 loop if you alter the rule to be 3x-1 instead of +1.

[@TymexComputing]

There was an pi-soda about the revelations of ternary system - so it would be easier to multiply by three and add 1 (just append 1 at the end of a number) but if its even then you simply have an even number of "even digits" in the representation but on the other hand the divison by two is frankly speaking unnatural in that base. It helps me to see that the Kojaks Konjecture is correct but i need another century to prove it

[@gigaprofisi]

I was thinking about this and this is the first video in my feed. Eerie

[@SourceEnginePlayer]

the reason it must fall a whole crap ton no matter how much it rises is because of 2 reasons 1: multiplying an odd number by an odd number will always be odd, because if you think about it, odd numbers have an extra piece for another odd number, hence odd+odd is even. When there is an odd number, each of the others get paired up with each other, but there is one more odd, which makes it all in all odd. Adding one will guarantee its even, which will divide by 2. However, since there isn't a guarantee that dividing by 2 will result in an odd, it will always fall more than it rises. Its simple, and because it can never rise more than it falls, there isn't another loop outside of 4-2-1. Its simple??? and 2: what goes up must come down.

[@VeteranVandal]

I've tried doing things in different basis. Unfortunately, It had been done before. Changing base didn't do as much as I was hoping.

[@Tymon0000]

Problem so simple yet so hard.

[@emilyrln]

I can't wait to learn the name of your short-haired black kitty!! (Don't tell me; I want to find it in a video 😂)

[@kasuha]

I tried looking at it at base 6 once but it didn't seem to make things any better than in base 10. What I think might be interesting would be to look at it in one of fractional bases, such as 2/3. But i don't think nobody has tried it yet so I guess it doesn't help either.

[@pulsefel9210]

so doesnt the binary form kinda prove it? it doesnt matter how long the string of 1 and 0 are, tripling plus 1 will always result in a lot of 0s to be snipped and eventually go down. id say you hit the money.

[@theinternetis7250]

Love these vids, thanks!

[@ZeroG]

I wanna play Magic Commander with this brotha

[@mantacid1221]

How is this the first time someone’s told me that Collatz’s first name was Lothar? Like that’s a wizard’s name.

[@wryanihad]

Can we prove collatz conjecture by induction method?

[@barakap2372]

Wow I really like your videos. Look up to you.

[@tjdrennan7147]

Just change 1 + 1 to equal 3, the unity of 2 creates something new a third, do this and 3x + 1 becomes infinite

[@DeWillpower]

cool to know there are shortcuts in base 3 and others

[@hziebicki]

For whatever reason, you remind me of Explosions&Fire, but like... Math version 😅 Great video anyhow, well done :)

[@alejrandom6592]

I dropped my phone and then the whiteboard fell. I'm sorry.

[@grezamisoit]

Tahnk you!

[@pacattack2586]

I don't understand how this isn't proven. I mean doesn't the fact that all the integers from 1-100 do this mean that any integer does this? I mean there's arguement to be made that because two digit even numbers split which way they go that you need to check up to 99, but I'm pretty sure that since all numbers end with an integer from 0 (effectively the 100 case) to 99 you couldn't possibly find a number that wouldn't hit 1 eventually right? Alternatively: Either a number *is* a power of two, or you'll eventually *hit* a power of two ... And the moment you do so it just falls down the pit

[@pacattack2586]

Actually possibly better idea - lets switch number systems and build an INFINATELY LONG NUMBER! Ok - worst case senario is that the last digit is odd. So whatever our infinately long number is it ends in a 1 in binary. Worst case senario again is that when we multiply by 3 and add 1 the *second* to last digit becomes odd, so we want this to end in 01. We will truncate the result until we have an odd digit at the end so when we multiply by 3 and add 1 the new second to last digit becomes odd. this means that we now want our number to be 001 for maximum efficency. so on and so forth and we will eventually build a number that is ...00000001 with infinately many 0s in front. This means that 1 *is* the worst case and it *does* cycle back on itself. QED

[@laurendoe168]

I'm surprised you didn't mention replacing 3x+1 with, say, 5x+1 or 7x+1. 7x+1 would be good for the base 6 video.

[@Joe_Payne]

Negatives are basically positive except its 3x-1 instead of 3x+1

[@triffinne]

I saw the globe on fire and immediately thought "Oh no, a model of global warming" 😆

[@FrankAnzalone]

Shouldn't the negative version be 3X −1?

[@rrock2025]

Why the ellipsis?

[@ChannelMath]

here's a better plan of attack, my young padowans: 1) learn how independence proofs work 2) learn forcing 3) prove the Collatz conjecture cannot be proved from the standard axioms of math (see Hilbert's 10th problem for inspiration)

[@yakuzzi35]

I love you maths Jack Harlow / Mr Tumnus

[@RandomGeometryDashStuff]

13:45 how can fraction or complex number be odd or even?

[@MuffinsAPlenty]

Only integers can be even or odd, but one can create extensions which produce the same results on integers as the typical method. So for example, Chamberland in 1996 used the function f(z) = z/2 * cos^2(πz/2) + (3z+1)/2 * sin^2(πz/2). Note that any complex number can be plugged into this function. Now, if z is a positive even integer, then the πz/2 is an integer multiple of π. sin(πz/2) is therefore equal to 0 and cos(πz/2) is therefore equal to 1, reducing the whole equation to z/2. So if you start with an even positive integer and plug it into this function, you end up just dividing that number by 2. If z is a positive odd integer, then πz/2 is π/2 + an integer multiple of π. sin(πz/2) is therefore equal to 1 and cos(πz/2) is therefore equal to 0, reducing the whole equation to (3z+1)/2. So if you start with an odd integer, then it multiplies it by 3 and adds 1, and then divides that by 2 (which is harmless since you always get an even number after doing that). But this function also creates a nice dynamical system which can be studied that way.

[@JiffyDealer]

Imagine it like subnetting ip addresses.