The Collatz Conjecture... but in Binary
Вставка
- Опубліковано 30 лип 2023
- Let me explain the “3x+1” mystery (the Collatz conjecture) and show some cool shortcuts that happen if we interpret it in binary, as well as some extensions like including negative numbers!
Make sure you're also tuned in to my @Domotro channel for my livestreams and other bonus content!
This episode was filmed by Carlo Trappenberg (plus a few scenes filmed by Jonathan Ruchlis). It was directed and edited by me (Domotro) and I also made the music in the soundtracks. And here's a link to the public domain fractal image I included near the end:
en.wikipedia.org/wiki/Collatz...
A small correction: near the end, when showing the negative number patterns, I had 1-2-4 written above those as an example of the positive loop, but 1-2-4 is in backwards order with the way I drew the arrows (arrows+error=errows?). That was meant to refer to the normal 4-2-1 loop (which could also be written as 1-4-2 or as 2-1-4) that was in the earlier portions of the episode.... There's also a few little typos: I misspelled "result" as "resut" one one whiteboard, and I accidentally typed "and my" twice on one of the credits whiteboards. Whoops.
Special thanks to Evan Clark and to all of my Patreon supporters:
Max, George Carozzi, Peter Offut, Tybie Fitzhugh, Henry Spencer, Mitch Harding, YbabFlow, Joseph Rissler, Plenty W, Quinn Moyer, Julius 420, Philip Rogers, Ilmori Fajt, Brandon, August Taub, Ira Sanborn, Matthew Chudleigh, Cornelis Van Der Bent, Craig Butz, Mark S, Thorbjorn M H, Mathias Ermatinger, Edward Clarke, and Christopher Masto, Joshua S, Joost Doesberg, Adam, Chris Reisenbichler, Stan Seibert, Izeck, Beugul, OmegaRogue, Florian, William Hawkes, Michael Friemann, Claudio Fanelli, The Green Way, Julian Zassenhaus, Bailey Douglass, Jan Bosenberg, Brooks Boutwell, David Irvine, qe, George Sharabidze, Jack Dwyer, and Fredrik!...
(Also thanks to my cats Sage, Dandelion, and Sassafras! Can you spot all 4 of Dandelion's catmeo appearances in this episode?)
Check out the Combo Class Patreon at / comboclass
If you want to mail me anything (such as any clocks/dice/etc. that you'd like to see in the background of Grade -2), here's my private mailbox address (not my home address). If you're going to send anything, please watch this short video first: • You Can Now Mail Me Th...
Domotro
1442 A Walnut Street, Box # 401
Berkeley, CA 94709
Come chat with other combo lords on the Discord server here: / discord
and there is a subreddit here: / comboclass
If you want to try to help with Combo Class in some way, or collaborate in some form, reach out at combouniversity(at)gmail(dot)com
DISCLAIMER: Do not copy any uses of fire, sharp items, or other dangerous tools or activities you may see in this series. These videos are for educational (and entertainment) purposes.
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).
Try starting with zero. Infinite loop of splitting zero in half which 0/2 = 0.
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 :)
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?
@@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 :)
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 !
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...
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” !
Some facts are base independent but yeah some other facts are just arbitrarily because of base ten haha. Base six would be better :)
Surely that's a baseless conjecture
@@ComboClass Senary supremacy! Based.
Maybe not totally arbitrary since we have ten fingers.
@@Mik1604ancient Egyptians used base 12, the Welsh and Inuit, base 20, and one area uses base 27! There are countless examples
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! :)
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 😂
Same, it’s so entertaining
this is made for kindergarten if you didn't know
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.
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 :)
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.
Sin(pi * x) is not 0 at every integer, sin(2pi * x) is.
@@ethanbottomley-mason8447 sin(0) = 0, sin(pi) = 0, sin(2pi) = 0.
sin is 0 at every integer multiple of pi.
@@redpug5042 You are correct.
I need to try this…
I've seen Veritasium make a video on this, but I didn't understand it. You made me understand it. Thanks!
I've spent way too much time thinking about this problem and will undoubtedly spend even more
it's wasted countless years of good math research. entire careers even. stay. away.
@@ChannelMath Oh, I know - its just too late for me. I've gazed too deeply into this particular abyss to be saved.
The negative extension is basically a mirror of “3x-1”.
which is another unsolved question!
@@drenz1523 nope, 3x-1 is proven false
honnestly, i love how your decorative stuff keeps falling or breaking
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.
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??
@@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).
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?
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
@@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.
@@BridgeBum True, but you still need some way to keep track of those odd numbers if you want to use that fact.
@@KaiHenningsen Agreed, however in practice you have to keep track of every number anyway.
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
Amazing video, as always. This playing with numbers always fascinates me and I love that there is a math channel dedicated to this.
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
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.
Fantastic video, your content is an absolute joy to watch.
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.
collatz conjecture is such a tease. Me and another math student spent a few weeks trying all kinds of different things, including using base 2 and 3, but the sequences just barely couldn't be shown to spiral up or down. I also tried using graph theory and erdos' probabilistic method to win that sweet $500 bucks, to no avail.
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…
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...
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.
27 = 3^3, so squaring that is 3^6, and squaring that is 3^12 ... so 3^((2^n)*3).
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.
Same here...but then again, I have anxiety issues.
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.
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)
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.
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 !
Man i love the Collatz Conjecture. So glad you talked about 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.
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.
Good shit as always dawg!
These videos are so captivating!
Love these vids, thanks!
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 👍
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?
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
@@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.
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
@@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.
@@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.
Love this video! Super fun to see binary used here
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.
It feels very decideable, but hard to figure out how
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
@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.
@@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.
"..Whoa! Carlo, the globe is on fire."
Indeed.. indeed.
loving the new season
"Oh dear. The crazy person in the lab is going into his small tiny yard to talk gibberish again.
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!
Thanks! There will be an episode about hypercomplex numbers at some point. Not sure about a hopf fibration episode but it’s certainly possible :)
Awesome man looking forward to it 😁
My world's on fire. How about yours? Oh. well... Hey now, you're an all-star.
Tahnk you!
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
I was thinking about this and this is the first video in my feed. Eerie
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
Wow I really like your videos. Look up to you.
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
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
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?
I was completely unprepared to be amazed at this unique content! Thank you!
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!
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)
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
This is the Explosions & Fire with math and I'm here for it
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?
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?
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.
Obviously we need to prove that the algorithm / 2 , 3x + 1, will always end up on one of the solutions x, of ( x,y ) 😅 👹
Four hours ago this was posted? Lets get it on.
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)
I dropped my phone and then the whiteboard fell. I'm sorry.
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)
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.
I'd like to see how this looks in base three and in base six.
For whatever reason, you remind me of Explosions&Fire, but like... Math version 😅 Great video anyhow, well done :)
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.
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.
Oh no, has Domotro been sucked into the neverending story of 3x + 1? It is an interesting conjecture.
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 :)
Problem so simple yet so hard.
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.
cool to know there are shortcuts in base 3 and others
How is this the first time someone’s told me that Collatz’s first name was Lothar? Like that’s a wizard’s name.
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 😂)
I saw the globe on fire and immediately thought "Oh no, a model of global warming" 😆
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.
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.
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.
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?
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
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.
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.
@@ComboClass That would be great. Thanks Domotro!
Look up Skewes's number, it is a good example of things failing only at very large numbers.
@@ethanbottomley-mason8447 Thanks for the reference.
Just change 1 + 1 to equal 3, the unity of 2 creates something new a third, do this and 3x + 1 becomes infinite
Negatives are basically positive except its 3x-1 instead of 3x+1
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
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.
I love you maths Jack Harlow / Mr Tumnus
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?
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.
What about factors as well? Will that aid in demonstration of this?
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?
I don't want to set the world on fire~
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
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
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
you might have doubts, now prove it :)
It reaches the same loop as one because you add 1. Enjoy the yendolars.
What was the fractal you showed? I thought I saw some Mandelbrot bulbs in there...
It’s linked in the description, and there’s some more info about the image in the link
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.
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.
What if someone prove that it is improvable
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.
Heeey aren't you "The Guy" from spy kids?
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.
so many broken clocks.
people that are into math are so, so, weird. yes, I mean you. yes, this is a compliment.
Can we prove collatz conjecture by induction method?
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)
the globe's on fire 🌍🔫
I wonder what would happen if you switched to base 3. 3x+1 would always end in 1
Base three does have its own cool shortcuts (and also downsides). The 3x+1 phase is easier, but the x/2 phase isn’t as neat as binary
Shouldn't the negative version be 3X −1?