You just need some mathematician's father to write a letter to his son telling him it's impossible and not to waste his time on it. Problem will be solved in no time.
But what if it's actually "impossible" (in the literal sense). I mean, we're assuming that there exists a proof that shows whether it's true or false, but it's already proven that not all mathematical statements must be provable. It's possible that neither its denial nor its affirmation generate contradiction with how the integers ring is defined. 👀 The question is... how do we "prove" there's not a "proof"...? 🤔
@@GabriTell there are various techniques. Though in this case, the interesting thing is this: Imagine we had a proof that this conjecture is undecidable in ZFC. That means it is impossible to find a counter example, otherwise this counter example were a proof that it is false. That means for every number you can ever try or write down, it would terminate in 1.
It's amazing how quickly this problem goes into the weeds -- these examples do a good job of explaining why exactly it is so hard. We try to come up with a simple heuristic about cycle length, and then the nature of the problem forces us into asking questions about the distribution of powers of primes.
I had some fun trying to make some progress on it by running in reverse, and it quickly showed how this problem depends on an infinitely-growing number of calculations, but while also showing that it is true for certain n mod x = 0. Still though, since prime numbers exist, we can know that there will always be more numbers which will appear within the gaps presented by these values of x where n mod x = 0. My method was to start at 1, and do the opposite operations, building branching trees of numbers. So instead of 3n+1 and n/2, you do 2n and (n + 1) / 3, taking only integer results of the latter. Each branch then consists of consecutive doublings of different starting numbers. E.g., one branch starts with 1 and immediately starts doubling, and it corresponds to all powers of 2. The next branch would be constructed by adding 1 and then dividing by 3, but that doesn't produce an integer result and so it is discarded. The next then would be to move on to the second item in the powers-of-two branch, and adding one, then dividing by three. That comes out to (2 + 1) / 3, and so is a result already within the tree, so it too can be discarded. The next operation would then be (4 + 1) / 3, which is also discarded as it's a non-integer. The next, however, gives us (8 + 1) / 3, which is 3, a new value. With this new value, we can construct 3(2^y), or the first branch of powers of two but with the multiplication of a factor of 3. This process can then be repeated to paint out classes of numbers which are covered by the conjecture, rather than having to work with individual numbers themselves. These classes take the form two to the power of all non-negative integers, times some collection of prime numbers. It establishes that, once a prime number is found to be within the conjecture, all numbers equal to a power of two times that number will also be within the conjecture. This reduces the problem from one of testing every number to testing only prime numbers, while providing the route to reach that prime from some number previously established to be within the conjecture. Now who knows whether that ends up being more calculations to do or not, because it requires a list of known primes, as well as mapping out the route from 1 to each of those primes. But, if we presume the conjecture to be true, we can then rely on naively finding the backwards route in reverse -- i.e. we can do the normal Collatz conjecture process to prime numbers to find their route to/from 1. So this should reduce the amount of calculations needed, once working with a dataset consisting of known prime numbers. This also, however, still falls short of coming anywhere close to proof of the conjecture, as it would require finding the path for all prime numbers, which would require there to be a finite amount of prime numbers. But yeah, this could give a method to establish the validity of the conjecture as to all numbers up to and including all known primes.
It’s cool you saw that we only have to show all primes reach one. I reached a general formula following your logic that gives numbers that go to an odd in qx+1. the only problem with this is when it reaches qn because there are no nodes (a number after an odd) above it and the equation tries to divide there making a fraction. If someone can fix this issue then yay. o*(2^(k+((n^c) *(product from m=1 to c of ((v sub m)-1))))) + (2^k)*(sum from m=1 to c of ((((2^n)-1)/q)*((1-(2^(m*n -n)))/(1-(2^n)))*(product from z=m+1 to c of (2^((v sub z)*n -n)))) becomes o. n=A002326((q-1)/2) if the zeroth term is 1 instead of first. (Someone else can fix this to be the 1st term), (I used (2^n -1)/q is integer to prove A002326(2^(n-1) -1)=n.) the other variables are positive integers with k being a whole number and o and q both odd. k is the final amount of multiples of 2. c is the number of times that we switch from one tower of 2^k to another by -1/3. v sub m is the amount of opportunities to switch to another tower occurring between when it does switch. So in conclusion if all odd numbers are within this equation thing, then Collatz proven. Also for 3j in 3x+1, the equation tries to subtract 1 and divide by 3 to get to another whole number, but it doesn’t work there so the equation needs work to avoid this mistake with constraints on the variables. From the previous comment I learned that we only have to find every prime instead of every odd so in that way this can be improved.
What a nice video! I'm very glad to stumble upon it, never knew where an attempt at solving the Collatz Conjecture can lead you, and it was very interesting to follow the history of it in mathematics
Tried my hand at it once. Never again. Ate up too much time just after high school. I do think I’ll at least post my methodology and conclusions here quickly though, although mostly what I can remember. Given that the problem works on multiples of 3 and 2, I decided to split all numbers into 6 (3*2) groups, giving them letter names. A (1,7,…) is an odd number 1 above a multiple of 3 B (2,8,…) is an even number 1 below a multiple of 3 C (3,9,…) is an odd number that is a multiple of 3. D (4,10,…) is an even number that is 1 above a multiple of 3 E (5,11,…) is an odd number 1 below a multiple of 3 F (6,12,…) is an even number that is a multiple of 3. And with these you can start figuring out where numbers trend to, and which are more important and which aren’t. F will become a lower F or a C A,C,E will get multiplied by 3 to become a C, and then have 1 added to become a D. A D divides into either a B or an E A B divides into either an A or a D. With these rules in mind it’s pretty clear F and C don’t matter at all; they will eventually become a D, and there’s no path to reach either once that happens. These rules also demonstrate that a D will be reached no matter what. There is no path that avoids a D. In fact, you can use D (basically a 3n+1) as the start and ends of chained together functions, with 3 potential paths at each D encountered. 1: the E-function, goes D->E->D with an increase. 2: the B-function, goes D->B->D with a decrease 3: the A-function, goes D->B->A->D with a slight decrease except at D1 where it repeats (the 4-2-1 cycle). As such you just ignore every number that isn’t a D and figure out which function a D goes down, as they will go in the pattern A-E-B-E… for growing values of D. Also make sure to give each D a number, with D1 being 4 and D2 being 10. Finding all suitable candidates for going down a chain of functions isn’t too difficult as you just insert each function into the previous function’s “X” (or is it “n” here?) and solve algebraically. And yes, all 3 functions have a specific formula by how much they change the D when applied. No, I don’t remember them off the top of my head, but they don’t take long to figure out. Anyways, the first interesting thing of note is that since the formula for E-functions is just changing factors of 2 into 3 (ok, I do remember that one), you can’t infinitely string them together with a finite number to start with as you’d eventually run out of factors of 2 to convert into 3s, and be forced to undergo a B or A function. The other interesting thing is each time you stack A, B, or E functions with each other, the denominator will grow by a multiple of 2 or 4. For a path of finite length, this means each additional step is either halving or quartering the number of starting D values that will immediately go through it. This effectively debunks infinitely increasing repeating cycles, as the number of D values that could start such a cycle eventually decrease to 1/infinity with infinite steps (aka exactly 1 number on the number line that’ll result in this specific path) and with an infinite repeating growing cycle you could shift 1 down the cycle and find a second D value that gives the same result. Although thinking about it now there are some interesting applications of this method, as there can only exist 1 starting value for any unique infinitely long chain in the conjecture. Although I don’t think it helps much. Anyways, that’s about as far as I got. There was a pattern with the chaining of B and A functions in regards to the addition changes to the next D value, but that’s about it. Thank you for reading this.
This is equivalent to working on base 6 =) Some research papers suggested and investigated its use as a lot of state transitions for the next few steps can be easily read from the final digit of a number. If you ever pick it up again look up modular arithmetic or modular congruence and you will find some familiarity within it. Have fun!
@@RadeticDaniel Yeah I definitely realized I was working in base 6 relatively quickly (and then basically just only working with numbers that end with 4). Definitely noticed parallels to modular arithmetic too although I don't know it well enough to figure out if what I was doing was that or just related to that. Glad to hear this route has been somewhat explored. Kind of expected that tbh.
@@noname117spore working on base 6 is equivalent to modular arithmetic when you look at the last digit to check for an equivalence class, other than that no. The cool part of working in base 6 is that multiplying by 3 is just pushing the digits to the left once and dividing by 2. So, with base 6 in the open and base 10 in parentheses: 3 -> 13+1 (9+1) -> 14 (10) -> 5 -> 23+1 (15+1) -> 24 (16) ... The thing that 30 (18) and 30/2 = 13 (9) is somewhat simple after a while doing the division steps everytime anyway. Just like doing value x 10 / 2 when you want value x 5 in base 10
You can break down the division of 2 more: 1/2 of evens are divisible by 2, 1/4 are divisible by 4, 1/8 are divisible by 8 and so on. If you were to pick a random even number the average "multiplier" it would get is just (1/2*1/2) + (1/4*1/4) + (1/8*1/8) ... This is the summation of 1/2^(2n) which is.. you guessed it, 1/3. So on average between swapping back to odd you're actually just dividing by 3 again.
"If you were to pick a random even number..." yeah well... unfortunately ... already after the first iteration (and even more so after more iterations) the numbers are NOT completely RANDOM anymore. THAT is the whole problem. Otherwise (i.e. if the numbers after each step would still be random) it would be trivial to prove and not even worth mentioning.
I love how the comments prove exactly how tempting this problem is to anyone with a basic understanding of maths. Yes, we've tried that. And that. And that. My favourite way to UNDERSTAND the problem is in binary (of course) since you can sum the 'even' rule by just truncating trailing zeros, aka only tracking significant digits. This is what the strange digital funnel images are based on. Then, make trees by working in reverse from 1. This let my brain actually fully viaualize the puzzle and realize it was approximately impossible.
I draw out trees from a 2-power "spine" like other people draw out mandalas. Just something fun and decorative. I personally have discovered interesting patterns, which of course other people have found before me, but it's still something worth exploring occasionally, with no expectations.
Yeah in the end it becomes a problem of modular arithmetic, capable of being displayed clearly in binary. But it simply asks too much. By my toying with things, I ended up finding that we could reduce it to testing only prime numbers, by establishing that working upwards from 1 can produce all multiplicative combinations of prime factors. But that still fails to include any primes. And good luck establishing some general proof about primes? Might be doable using modular arithmetic, again, but I can't imagine how to do that except on a case-by-case basis for each prime, which makes for an unsolvable proof not much different from merely checking every number in the non-reversed manner.
45:50 18x - 7y = 35 limited to integers is very easy: Because 35 is a multiple of 7 and you're subtracting a multiple of 7, you just need to find a multiple of 18 that's also a multiple of 7... Which is trivial (18*7 so x = 7) and then y is just 18-5 = 13 from there (the 5 is the other factor of 35). Easy for high school (and middle school!) And then there are an infinite amount of solutions where x = 7k and y = 18k - 5
Thank you @katakana1! From the book Math Kook (p. 152): "Until recently, I thought 'irrational' was a derogatory word. I imagined ancient mathematicians arguing with each other: 'Sir, you are irrational, as are your arguments ... as are your very numbers!' But then I learned the root word of 'irrational' is 'ratio.' It just means 'un-ratio-able.' Upon hearing this, a European acquaintance told me, 'It's impossible to finish school without knowing this.' I replied that in the United States, anything is possible."
@@mathkook You probably did learn it in school, and then never thought about it again because the other definition is so ingrained. I'm almost certain at least one, if not all, of my high school teachers that explained irrationals did so by stressing the "ratio". I'm absolutely certain my mind thought it made perfect sense, and that by the next day I'd completely forgotten about it. Because math class would proceed to treat it as just another arbitrary label (like "imaginary"), while everything outside of math class would only use the other definition of "irrational".
Great talk Math Kook. It's amazing how many different creative approaches have been tried (and have failed). I am surprised that you say no one knows a simple proof that the only circuit cycle is the trivial cycle (1,2). Here's an outline. If we consider only the numbers in a trajectory preceded by a larger number and followed by a larger number (ie. a "local minimum"), we can easily write an equation for the next local minimum. We can show that the only case which returns to the initial value as the next local minimum is 1. Let s be an odd positive integer that is also a local minimum, and let m be the order of 2 in s+1, and k the order of 2 in (3/2)^m * (s + 1) - 1 (this is the largest number reached from s before any smaller number occurs). Then the next local minimum after s is ((3/2)^m * (s + 1) - 1) * (1/2)^k Suppose s = ((3/2)^m * (s + 1) - 1) * (1/2)^k. Some algebra produces s = (3^m - 2^m) / (2^(m+k) - 3^m) * s which means (3^m - 2^m) / (2^(m+k) - 3^m) = 1
Gathering powers of 3 and 2 on opposite sides gives 2 * 3^m = 2^m * (1 + 2^k), or 3^m = 2^(m-1) * (1 + 2^k)
Since the 3^m is odd, the exponent (m-1) must be 0, giving m = 1 and 3 = 1 + 2^k, and therefore k = 1
So, the only circuit cycle has m = k = 1, which gives s = ((3/2) * s + 3/2 - 1) * (1/2) = 1, the trivial cycle.
Nice! Can you show the details of your some-algebra-produces part? All I can get is s = (3^m-2)/(2^(k+1)-3^m), leading to a potential path where we have to prove there's only one (s, m, k) solution to that equation in the positive integers.
I’ve done my time playing with the conjecture and it does quickly show you your limitations. It reminds me of the Halting Problem, but of course the HP only demonstrates that there is no *general* solution; it doesn’t rule out a tailored solution. In a certain sense, it means that some programs are just their own “solution” and that the ability to state a conjecture can never be taken to imply a simplified “solution.” If a program can be proven to halt, the proof is kind of isomorphic or analogous to the program itself. So I tend to think that Collatz is just one of those lovely undecidable programs that forms its own distinct continuum.
yeap, negative numbers are an extension to try to better understand it the original sequence has natural numbers for its domain, all integer values 1 and up there are other negative loops on SLOAN and some wikipedia discussion pages
The conjecture is about positive whole nonzero numbers mate, negatives dont necessarily loop to one but they aren't part of the conjecture so ye you're right but it doesnt prove the collatz conjecture wrong
I don't get the slide on cycle length bound. What is a high cycle? Where 8.89 comes from? Doesn't make sense to me since every cycle of len 13 (and up to 11e6) has 1 as its least member.
@PedroPedruzzi Right on. (1) You can also send fractions through the Collatz rule ... try 211/13 and see what you get (a fraction is odd if its numerator is). (2) Not every fraction is a cycle member, but every cycle shape is inhabited by some set of fractions. (3) Considering all cycles with x odd terms (almost surely non-integer fractions, but who knows?) the high cycle is the one whose least member is greatest ... a truly infelicitous phrase.
@@mathkook not trying to rain on anyone's happiness here, but it is my first time reading about odds and evens with fractions. Considering 3/7 = 6/14 I'd assume parity has to be determined with the most reduced form? Interesting concept =)
Hi! I wanted to stop by to say this video is the best I have seen so far on this topic and thank Math Kook for it. I personally dipped into this and happened to find a proof for the inexistence of "gliders" in 3x+1. Unfortunately publishing it isn't easy when you are not a professional mathematician, but if someone who reads this message is one and is interested I am sure we may find common ground. My paper is in French but I am fluent enough in English to translate it if needed. Have a nice day!
What does Life simulating 3n+1 look like? I wonder if that’ll give us any more clues. In particular, stop looking at it as a function of human counting numbers and start looking at it as dots.
sure thing @MelindaGreen, go to math-kook-book.github.io/base2.png ... the different runs are graphically scaled to the same height, even though some runs take longer than others. (also, this is a base2 version that's clearer to read than the base10 version in the video)
Not a mathematician. Haven't seen it anywhere else, and I'm sure it isn't useful at all, but I found it interesting nonetheless. I started by looking at the last digit only, and decided upon a sequence of that last digit say 6,3,0,5 (any will do). When you look at all the starting numbers that end with that last digit for example 6,16,26,36... 686,696, etc. and stop it when it first breaks the 6,3,0,5 sequence, the lengths of these sequences end up looking like a lined ruler with equally spaced markings.
Are there any conjectures like this that are thought to be impossible due to checking insane amounts of numbers, but it was later proved that the solution is just stupidly large?
Yes, the sum of 3 integer cubed numbers being equal to 3. It had 2 known solutions and it was conjectured no other solutions existed, until someone published another triplet that worked
Well I did not "Avoid it at all Costs". Rather I kept at it and did not stop. I put in all the necessary extra time that I needed until I finally solved it. The answer was NOT to give up! It also helps that I've always been a whiz in Math and I tend to look at numbers in different ways than others do. Instead of letting the numbers defeat you, you just figure them out. Anyways... I just wanted to officially say that I Solved the Collatz Conjecture at 3:34 AM, September 26th, 2024. : ) Have a Most Wonderful Day! : ) MonsterPianoPlayer
Now that's very interesting. I wonder if you could invert it somehow. Instead of a finite sequence ending at 1, you let it be a infinite sequence starting at one. Then proving the conjecture is just proving that the sequence contains every integer.
that is how you generate the tree shown at the beginning if a number is even and one more than a multiple of 3 then you can do (n-1)/3 to find out which odd number would get to it and of course you can always include 2n for each number on the tree, as it will always be even and divide to get to n
I thought I would be clever with my approach to do this calculation in binary, but it led to nowhere. I hoped, 3n+1 would yield a certain pattern. In the end one has to proof that 3n+1 at some point leads to a binary number which contains only a single 1, counting all digits (as powers of two collapse the 1-2-4 loop).
Never hurts to try, but it's very unlikely that a simple transformation will turn a hard problem into an easy one. Especially if it's a famous problem, where all the easy approaches have surely already been tried.
you cant change a problem by changing the base. some patterns may be more apparent to a lazy human eye in one base as opposed to another, but regardless those same patterns exist in all bases. 3n+1 is especially beautiful in binary, but ultimately the pattern boils down to the fact that you still need to solve the conjecture in order to prove the conjecture.
After messing about in binary for fun, I did see the pattern that strings of 1 lead to recurring odd numbers. It's quite fun to pick a random large number and let it run, see what'll happen.
It's actually FAR better to look at in binary, and generally considered that way. Still intractible, just more intelligibly. The steps just become "add the number to itself, bitshifted left by 1, plus one. Then truncate all trailing zeroes. Check for 1." So simple you could build a specialist computer chip to solve it nearly instantly for any given starting number. You're still left checking infinite starting numbers, of course. Lol
@@tristanridley1601 "add the number to itself, bitshifted left by 1, plus one" is no simpler than multiplying by 3 and adding 1; truncating all leading zeros is no simpler than dividing repeatedly by 2. Recasting it into binary doesn't make it conceptually any simpler, and it doesn't make it any easier for a computer, because everything we put into computers is encoded in binary anyway.
In the probabilistic sense, can the problem be described as always convergent, since no matter how big the number is, the odds of it never being a power of 2 is next to none due to the sheer amount of numbers it goes through?
@@ianallen738 Given that no natural number can be uncountable, a sequence can't have zero probability of being a power of 2 since the succession itself is never ending. Thus, the probability of landing in a power of 2 is non zero for every sequence since they're not finite.
@@bazooka712but they are finite, for any starting number, theres a finite set of numbers that it traverses.Yes you can extend the list infinitely with 1>4>2>1, but its not seeing new numbers, so you can, to use your argument, state that the odds of this sequence ever reaching 3 is 0%. you may have crossed 3 earlier, but theres no point continuing once the sequence has reached a number its already been too. its guaranteed to never see another number. Even without knowing the actual truth of the collatz conjecture, we know theres 3 outcomes. it goes to 1, and loops it goes to itself, and loops or it somehow extends upwards infinitely. 2 of those options see finitely many numbers, always. So you cant just say theyre not finite and use probability to make an argument
@@bazooka712 Doesnt matter because yoy need a finite counter example. Your case would only work if you were looking for an infinite number of exceptions. For example, imagine 3 didn't work but every single other number did; your convergence would still hold.
Actually, I think you could probably find a way to encode an initial starting pattern in binary for conways game of life, and if you applied the same logic to the collatz conjecture, you could likely make interesting simulations
(1)if n is even, n := -n/2 (2)if n is odd, n := -3n + 1 (3)if n is not 1, repeat(1)(2) for example，n = -7 -7→22→ -11→34→ -17→52→ -26→13→ -38→19→ -56→ 28→ -14→7→ -20→10→ -5 →16→ -8→4→ -2→1 I can't find counter-example.
Wait a minute! At 12:48 you said that no positive whole-numbered cycles of length 3 exist. What about 4-2-1-4 ? Isn't that a cycle of length 3? What did you really mean, and where's the proof?
@dudethebagman Thanks for the reminder. I'm using the "short cut" rule that takes odds to (3n+1)/2 instead of (3n+1). So -5 goes to -7 instead of -14 (then to -7). Under the short-cut rule, the trivial loop is 2-1-2, of length 2.
this is how to solve problem 100 on UVa Online Judge for computer algorithm competitions stack all value until you find a known solved n unstack filling up the array when the index is not out of bound repeat until you know enough for each query cool problem and how i first heard of 3n+1 to begin with but working this out only gives a fast way to calculate solvable numbers and detect a loop if it exists however it does not tell us if a loop exists or if all numbers are solvable
Bruh, just because someone has a 19$ license, doesn't mean they have any prior experience in coding. Had to prove fandoms would ban those that have a lifetime license to test apps because fandoms be toxic on general populace. Proved promotion systems to be just as toxic as fandom hijackers.
I think it's pretty easy to prove this one terminates, since the numbers decrease much more quickly. Starting any number n, you either go to n/2 in one step or (n+1)/2 in two steps. In both cases, you end up with a smaller number than you started with*, so you'll end up at 1 within 2lg(n) steps, and usually around 1.5lg(n) steps since you're dividing by 2 every one or two steps and I would expect the two possibilities to be roughly equally probable. Sanity check: lg(10000)≈13.3, and 10000 goes to 1 in 20 steps (10000, 5000, 2500, 1250, 625, 626, 313, 314, 157, 158, 79, 80, 40, 20, 10, 5, 6, 3, 4, 2, 1). Almost exactly 1.5lg(10000)! *this is only true for numbers greater than two. But 2 and 1 obviously go to 1. I think the reason 3n+1 makes it so much harder is that the next number can either go up or down by a reasonably similar amount (either a factor of 2 or 3), whereas with the n+1 version it can go down by a factor of two but only go up by a measly constant.
@@radeklew1you are correct, half of the odds become a multiple of 2 and the other half a multiple of 4. So it gives 3n/2 and 3n/4 for those cases, which keeps some of the starting numbers floating in a narrow range until they hit a value that likes to jump particularly high or that falls particularly fast
N= positive odd number. N changes to (3N+1)/2 (3N+1)/2 could be: 1- (3N+1)/2 = positive odd integer 2- (3N+1)/2 = positive even integer 1- assume (3N+1)/2 = positive odd integer. Since N = positive odd integer, it could be a value for (3N+1)/2 So, (3N+1)/2 = N 3N + 1 = 2N 3N - 2N = -1 N = -1, which contradicts with N = positive odd integer. So, the assumption (3N+1)/2 = positive odd integer is false. 2- assume (3N+1)/2 = positive even integer. Since N + 1 = positive even integer, it could be a value for (3N+1)/2 So, (3N+1)/2 = N + 1 3N + 1 = 2N + 2 3N - 2N = 2 - 1 N = 1, which does not contradict with N = positive odd integer. So, the assumption (3N+1)/2 = positive even integer is true, and (3N+1)/2 will change to smaller value (3N+1)/4 < N, getting toward the destination 1. If N = 1, (3N+1)/4 will equal 1, which is a term within the destination loop 1 → 2 → 1. So, N = positive odd integer, just changes to (3N+1)/2 = positive even integer, which changes to (3N+1)/4 < N, getting toward the destination 1. So, Collatz conjecture is true. Eng. Mahmoud Attalla. WhatsApp: +20 1112669096.
Maybe an ever increasing sequence is somehow possible. Starting with some odd number, adding a prime factor 3, and then incrementing the number by 1, should produce a number with only one 2 prime factor. And this should remain true when doing this repeatly. It seems to be about how incrementing a number affects its prime factors. If a number has at least one 2 (prime factor), incrementing it removes all 2's because it becomes odd. But if a number has no 2, incrementing it adds one or multiple 2's. And here the numbers should always remain such that only one 2 will be added.
maybe going from the other direction could be useful. let's prove that if we take the number 1 and apply the reverse collatz, then all natural numbers can be created that way.
thats equivalent. if you can prove it going up, you have proved it going down, and vice-versa. it makes no effective difference on the difficulty of solving the problem.
Just Google Collatz Bakuage it was in the news a couple years ago. But don't waste your time on the conjecture, as if you aren't smart enough to do basic web searches well...
I don’t know much about math. If it’s about closeness of powers; then 2 raised to a power is missing the odd numbers and prime numbers. So, if you want to find some closeness, then you have to raise those numbers to some power. So maybe there’s a better question to be asked. Anyway I found it very entertaining fiddling around with numbers.
john conway proved a generalization of this problem is undecidable in 1972 - en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations his functions, however, do not use any addition, which gives them significantly different dynamics than the standard collatz conjecture
We should probably not ask an AI the answer to this in case it decides the universe needs converting into stuff better suited for answering the 3x+1 conjecture
I have found multiple repeating patterns within the Collatz Conjecture I just haven’t taken a proper class on Proof Writing so I can make a proper paper to submit
@@PlaceholderAlex tried. Local community college and the local university both told me that their maths departments are too busy to devote extra time with non-campus work. It’s alright though. I’ll get there. I’m signed up with a program. But yeah. I’ve found multiple repeating patterns. The funny thing is one set of patterns changes every time time you apply the Collatz Conjecture. EVERY. TIME. While I cannot predict what that pattern will look like, I can tell you exactly how many Odds and Evens will be in that pattern. (Note as that set of patterns approaches infinity, the quantity of Odds and Evens on the Numberline both approach a limit. 33.333…% Odd & 66.67% Even. But the more important pattern. Makes the numberline look like a Ruler. With evenly spaced lines.
@@PlaceholderAlex in fact the Ruler Pattern is thee most important pattern. As it basically proves that at infinity, there’s an odd number with an Infinite number of Evens between the initial odd number and the next odd number.
@@HoushouRattengod Just to be clear, are you talking about a counterexample, or just some odd side patterns that you found while playing with the conjecture? If you have a counterexample, then you shouldn't really bother reporting more than the single list of numbers in _one_ of your counterexamples (at least until someone impressed comes to you asking how you found it).
@@Tzizenorec it’s not a counter example. Just the opposite. I’m fairly certain it is the proof needed to show that all numbers will go to one. The pattern(s) in the first section shows that as you continue to use and apply the Collatz Conjecture. The literal Numberline starts to skew towards two limits. 33.3333…% Odd and 66.67% Even Look. 1,2,3,4, …. The numberline before The Collatz Conjecture. 50% Odd, 50% Even. Now apply the rules. Pattern: Odd-Even, Collatz, 1 Time (No shortcut) 4, 1, 10, 2, … Pattern: Even-Odd-Even-Even The pattern has doubled in size and the % of Odds:Evens is 25% Odd / 75% Even Don’t believe me? Watch: 5, 6, 7, 8, … -> 16, 3, 22, 4 Even-Odd-Even-Even That’s just on applying the Collatz Conjecture once. Do it again and you get a new pattern. 1, 2, 3, 4, 5, 6, 7, 8, … (base) 4, 1, 10, 2, 16, 3, 22, 4, … (Collatz-1 (C1)) 2, 4, 5, 1, 8, 10, 11, 2, … (C2) The pattern doubles in size a second time and changes to: E-E-O-O-E-E-O-E 3 Odds / 5 Evens Every time you apply the Collatz Conjecture, there is a new pattern. I cannot predict what the pattern will look like. But I can tell you that the size of the pattern is equal to 2^n , where n equals the number of times you have applied the Collatz Conjecture +1. That way the Base Integer Numberline is 2^(0+1) = 2^1 The formula for how many Odd numbers is a LOT more tricky. But it is based on a recurrence relation formula. And basically, if you map these out, you start to see that a limit starts to appear. And that limit is 1/3 of the Numberline are Odds, and 2/3 are Even. And while /that/ doesn’t prove the Collatz Conjecture. The process I went through to find that, is the basis of “The Ruler” pattern I have.
It might be better to model the problem with a Poset, and see if it converges. Still a huge waste of time. Unless we can reapply the logic to another expression (ie 5x+1 )
Narrator: _But he did not, in fact, avoid the Collatz Conjecture. And so he spent countless hours on making various videos about the Collatz Conjecture, for months to no end...._
So multiplying two odd numbers results in an odd number. They make you add one to always make the result even. Then you have to divide the even numbers by 2. You will always go down because you are halving the result every time. The only reason you end up with the familiar 8-4-2-1 sequence is because of dividing by 2. This is only a result of the mechanics of math and our number system, not some mystical sequence.
It's not that simple. (3n+1)/2 is still > n. An alternating sequence of odd-even will always grow, not shrink. Easy example is n=5. You get 5->16->8, so it does increase. The question is, is there a chain that doesn't eventually hit a power of 2, and we can't know that without a more rigorous proof.
@@andrewhargreave7246 This isn't that amazing to me. The only interesting thing that happens is that sometimes when you have an even number and divide by two you get an odd number. That's just the mechanics of our number system. The rules force any odd number to become even thereby halving the number. Do it enough times and you will get to the 8-4-2-1 sequence which is ONLY divisible by 2 as per the rules. There is no upper limit to this sequence as it works on any whole number. This sequence only works with divide by two and is therefor just a curiosity and a mechanic of our number system.
@@o0Donuts0oThe conjecture interests so many people entirely because its not nearly as simple as you seem to believe. Noone has been able to prove that it always reaches 1, many people believe so, but proof of that is a lot harder to make. As Andrew mentioned (3n+1)/2 is larger than n, and if it results in an odd number it can continue to grow. It will almost go back down again, but in doing so it may go down to the original odd number, in which case it then repeats the loop
@@o0Donuts0o someone else could argument that if you keep dividing by 2, it will be odd, and jump times 3. Even if you divide it again, half the time you will get another odd number and become approximatedly 3n/2 from n/2 from n. Your argument with words only is not strong enough to apply the induction principle. More importantly, it is not strong enough to resist the flipping of terms of your own argument as i wrote above. For example, your argument doesn't say anything about 3 being the multiplier, but 7n+1 grows to infinity. If the multiplier matters, then your logic is either incomplete or wrong. Over simplifying an approach only solves easy problems, this one is open for more than 75 years and some of the best mathematicians of their days tried it. If it was that simple, it would be solved already.
@@RadeticDaniel no. You want it to be hard and mysterious. This isn’t something like solving primes. The rules are made up to make every odd number forcefully be even. And every even number divisible by two. This “puzzle” does not work if you divide by 4 or any other even number. It’s just product of our number system. It won’t work on any other base. All it shows is that if you halve certain numbers by two you may get the 8-4-2-1 sequence. Don’t make this some sort of golden ratio mysticism.
Let F( n ) = 3n+1 if 2|n, n/2 otherwise. Prove all natural values of n always reach 1. That's the simplest way to describe it and it has been open for nearly 80 years. Have fun! P.S.: ready Tao's paper for plenty of Algebra or Conway's automaton solution attempt for another incredibly puzzling perspective
@@RadeticDaniel Let f(x) be a real valued function. If x is rational than f(x)=1, otherwise f(x)=0.. Many would say that's description of a function is ok. I would say it describes a $hit.
@@imeprezime1285 you still don't say what is wrong with the description in your opinion and either ignored or just didn't acknowledge the reference to well known researchers with papers you could probably easily find... As far as I know even calculus books will describe the absolute value function over real numbers as Let F( x ) = -x if x
@@RadeticDaniel You are missing the point and give a supereasy calculable example to face my example. How would you build an algorithm in order to calculate f(x) for every given x? You must know for every possible x if it is irrational or not. Math will never be able to answer that. There are problems that math simply can't solve. Collatz conjecture, Goldbach conjecture and some others are very likely such problems. Words come easy, and with them you can describe almost everything. But that's not enough to reach constructible proof in some cases (and that's hard to prove as well)
You need 99.999...% odds to stay above the start number because even numbers on average don't just get divided by 2, every multiple of 4 gets divided by 4, every multiple of 8 gets divided by 8 etc... diverges to on average even numbers get divided an infinite number of times
This "conjecture" is one of the most useless and dumbest thing that ever happened in mathematics. It's just ridiculous that people spend time on it. I am almost certain you can generalize it to work with different iterations, some n
![ค้าง (STILL) - GEMINI [ OFFICIAL MV ]](http://i.ytimg.com/vi/Ftxx3hk5vkU/mqdefault.jpg)
You just need some mathematician's father to write a letter to his son telling him it's impossible and not to waste his time on it. Problem will be solved in no time.
I tried that. It hasn't worked yet.
Maybe 5 year old was a bit early.
Or the complete opposite. Don't tell it's not solvable and some college guy will solve It.
Just put it on a blackboard and wait for the janitor.
But what if it's actually "impossible" (in the literal sense).
I mean, we're assuming that there exists a proof that shows whether it's true or false, but it's already proven that not all mathematical statements must be provable.
It's possible that neither its denial nor its affirmation generate contradiction with how the integers ring is defined. 👀
The question is... how do we "prove" there's not a "proof"...? 🤔
@@GabriTell there are various techniques. Though in this case, the interesting thing is this: Imagine we had a proof that this conjecture is undecidable in ZFC. That means it is impossible to find a counter example, otherwise this counter example were a proof that it is false. That means for every number you can ever try or write down, it would terminate in 1.
Here are the most facts about that simple conjecture - thank you! Very thorough work!
It's amazing how quickly this problem goes into the weeds -- these examples do a good job of explaining why exactly it is so hard. We try to come up with a simple heuristic about cycle length, and then the nature of the problem forces us into asking questions about the distribution of powers of primes.
amazing video btw! I would love to see more videos that go into exactly why problems like this are so hard and what approaches have been tried
I had some fun trying to make some progress on it by running in reverse, and it quickly showed how this problem depends on an infinitely-growing number of calculations, but while also showing that it is true for certain n mod x = 0. Still though, since prime numbers exist, we can know that there will always be more numbers which will appear within the gaps presented by these values of x where n mod x = 0.
My method was to start at 1, and do the opposite operations, building branching trees of numbers. So instead of 3n+1 and n/2, you do 2n and (n + 1) / 3, taking only integer results of the latter. Each branch then consists of consecutive doublings of different starting numbers. E.g., one branch starts with 1 and immediately starts doubling, and it corresponds to all powers of 2. The next branch would be constructed by adding 1 and then dividing by 3, but that doesn't produce an integer result and so it is discarded. The next then would be to move on to the second item in the powers-of-two branch, and adding one, then dividing by three. That comes out to (2 + 1) / 3, and so is a result already within the tree, so it too can be discarded. The next operation would then be (4 + 1) / 3, which is also discarded as it's a non-integer. The next, however, gives us (8 + 1) / 3, which is 3, a new value. With this new value, we can construct 3(2^y), or the first branch of powers of two but with the multiplication of a factor of 3.
This process can then be repeated to paint out classes of numbers which are covered by the conjecture, rather than having to work with individual numbers themselves. These classes take the form two to the power of all non-negative integers, times some collection of prime numbers. It establishes that, once a prime number is found to be within the conjecture, all numbers equal to a power of two times that number will also be within the conjecture. This reduces the problem from one of testing every number to testing only prime numbers, while providing the route to reach that prime from some number previously established to be within the conjecture.
Now who knows whether that ends up being more calculations to do or not, because it requires a list of known primes, as well as mapping out the route from 1 to each of those primes. But, if we presume the conjecture to be true, we can then rely on naively finding the backwards route in reverse -- i.e. we can do the normal Collatz conjecture process to prime numbers to find their route to/from 1. So this should reduce the amount of calculations needed, once working with a dataset consisting of known prime numbers.
This also, however, still falls short of coming anywhere close to proof of the conjecture, as it would require finding the path for all prime numbers, which would require there to be a finite amount of prime numbers. But yeah, this could give a method to establish the validity of the conjecture as to all numbers up to and including all known primes.
It’s cool you saw that we only have to show all primes reach one. I reached a general formula following your logic that gives numbers that go to an odd in qx+1. the only problem with this is when it reaches qn because there are no nodes (a number after an odd) above it and the equation tries to divide there making a fraction. If someone can fix this issue then yay.
o*(2^(k+((n^c) *(product from m=1 to c of ((v sub m)-1))))) + (2^k)*(sum from m=1 to c of ((((2^n)-1)/q)*((1-(2^(m*n -n)))/(1-(2^n)))*(product from z=m+1 to c of (2^((v sub z)*n -n)))) becomes o.
n=A002326((q-1)/2) if the zeroth term is 1 instead of first. (Someone else can fix this to be the 1st term), (I used (2^n -1)/q is integer to prove A002326(2^(n-1) -1)=n.) the other variables are positive integers with k being a whole number and o and q both odd. k is the final amount of multiples of 2. c is the number of times that we switch from one tower of 2^k to another by -1/3. v sub m is the amount of opportunities to switch to another tower occurring between when it does switch.
So in conclusion if all odd numbers are within this equation thing, then Collatz proven. Also for 3j in 3x+1, the equation tries to subtract 1 and divide by 3 to get to another whole number, but it doesn’t work there so the equation needs work to avoid this mistake with constraints on the variables. From the previous comment I learned that we only have to find every prime instead of every odd so in that way this can be improved.
What a nice video! I'm very glad to stumble upon it, never knew where an attempt at solving the Collatz Conjecture can lead you, and it was very interesting to follow the history of it in mathematics
Tried my hand at it once. Never again. Ate up too much time just after high school.
I do think I’ll at least post my methodology and conclusions here quickly though, although mostly what I can remember.
Given that the problem works on multiples of 3 and 2, I decided to split all numbers into 6 (3*2) groups, giving them letter names.
A (1,7,…) is an odd number 1 above a multiple of 3
B (2,8,…) is an even number 1 below a multiple of 3
C (3,9,…) is an odd number that is a multiple of 3.
D (4,10,…) is an even number that is 1 above a multiple of 3
E (5,11,…) is an odd number 1 below a multiple of 3
F (6,12,…) is an even number that is a multiple of 3.
And with these you can start figuring out where numbers trend to, and which are more important and which aren’t.
F will become a lower F or a C
A,C,E will get multiplied by 3 to become a C, and then have 1 added to become a D.
A D divides into either a B or an E
A B divides into either an A or a D.
With these rules in mind it’s pretty clear F and C don’t matter at all; they will eventually become a D, and there’s no path to reach either once that happens.
These rules also demonstrate that a D will be reached no matter what. There is no path that avoids a D.
In fact, you can use D (basically a 3n+1) as the start and ends of chained together functions, with 3 potential paths at each D encountered.
1: the E-function, goes D->E->D with an increase.
2: the B-function, goes D->B->D with a decrease
3: the A-function, goes D->B->A->D with a slight decrease except at D1 where it repeats (the 4-2-1 cycle).
As such you just ignore every number that isn’t a D and figure out which function a D goes down, as they will go in the pattern A-E-B-E… for growing values of D.
Also make sure to give each D a number, with D1 being 4 and D2 being 10.
Finding all suitable candidates for going down a chain of functions isn’t too difficult as you just insert each function into the previous function’s “X” (or is it “n” here?) and solve algebraically. And yes, all 3 functions have a specific formula by how much they change the D when applied. No, I don’t remember them off the top of my head, but they don’t take long to figure out.
Anyways, the first interesting thing of note is that since the formula for E-functions is just changing factors of 2 into 3 (ok, I do remember that one), you can’t infinitely string them together with a finite number to start with as you’d eventually run out of factors of 2 to convert into 3s, and be forced to undergo a B or A function.
The other interesting thing is each time you stack A, B, or E functions with each other, the denominator will grow by a multiple of 2 or 4. For a path of finite length, this means each additional step is either halving or quartering the number of starting D values that will immediately go through it. This effectively debunks infinitely increasing repeating cycles, as the number of D values that could start such a cycle eventually decrease to 1/infinity with infinite steps (aka exactly 1 number on the number line that’ll result in this specific path) and with an infinite repeating growing cycle you could shift 1 down the cycle and find a second D value that gives the same result.
Although thinking about it now there are some interesting applications of this method, as there can only exist 1 starting value for any unique infinitely long chain in the conjecture. Although I don’t think it helps much.
Anyways, that’s about as far as I got. There was a pattern with the chaining of B and A functions in regards to the addition changes to the next D value, but that’s about it.
Thank you for reading this.
This is equivalent to working on base 6 =)
Some research papers suggested and investigated its use as a lot of state transitions for the next few steps can be easily read from the final digit of a number.
If you ever pick it up again look up modular arithmetic or modular congruence and you will find some familiarity within it.
Have fun!
@@RadeticDaniel Yeah I definitely realized I was working in base 6 relatively quickly (and then basically just only working with numbers that end with 4).
Definitely noticed parallels to modular arithmetic too although I don't know it well enough to figure out if what I was doing was that or just related to that.
Glad to hear this route has been somewhat explored. Kind of expected that tbh.
@@noname117spore working on base 6 is equivalent to modular arithmetic when you look at the last digit to check for an equivalence class, other than that no.
The cool part of working in base 6 is that multiplying by 3 is just pushing the digits to the left once and dividing by 2.
So, with base 6 in the open and base 10 in parentheses:
3 -> 13+1 (9+1) -> 14 (10)
-> 5 -> 23+1 (15+1) -> 24 (16)
...
The thing that
30 (18) and 30/2 = 13 (9) is somewhat simple after a while doing the division steps everytime anyway.
Just like doing
value x 10 / 2 when you want
value x 5 in base 10
Besides that it doesn't really get very far from what I've seen
Man, and all this time i've been vising my local Collatz Conjecture not knowing about the consequences of doing so!
Always loved this problem. I have a solution but it doesn't fit into this post's margin :)
You can break down the division of 2 more: 1/2 of evens are divisible by 2, 1/4 are divisible by 4, 1/8 are divisible by 8 and so on.
If you were to pick a random even number the average "multiplier" it would get is just (1/2*1/2) + (1/4*1/4) + (1/8*1/8) ...
This is the summation of 1/2^(2n) which is.. you guessed it, 1/3. So on average between swapping back to odd you're actually just dividing by 3 again.
If you're averaging multipliers you probably want to take a geometric mean
"If you were to pick a random even number..." yeah well... unfortunately ... already after the first iteration (and even more so after more iterations) the numbers are NOT completely RANDOM anymore. THAT is the whole problem. Otherwise (i.e. if the numbers after each step would still be random) it would be trivial to prove and not even worth mentioning.
Can’t wait to see what type of curves we need to look at to solve this one. :)
Great video. Nice to have a compilation of what we do and do not know!
I love how the comments prove exactly how tempting this problem is to anyone with a basic understanding of maths.
Yes, we've tried that. And that. And that.
My favourite way to UNDERSTAND the problem is in binary (of course) since you can sum the 'even' rule by just truncating trailing zeros, aka only tracking significant digits. This is what the strange digital funnel images are based on.
Then, make trees by working in reverse from 1. This let my brain actually fully viaualize the puzzle and realize it was approximately impossible.
I draw out trees from a 2-power "spine" like other people draw out mandalas. Just something fun and decorative. I personally have discovered interesting patterns, which of course other people have found before me, but it's still something worth exploring occasionally, with no expectations.
Yeah in the end it becomes a problem of modular arithmetic, capable of being displayed clearly in binary. But it simply asks too much. By my toying with things, I ended up finding that we could reduce it to testing only prime numbers, by establishing that working upwards from 1 can produce all multiplicative combinations of prime factors. But that still fails to include any primes. And good luck establishing some general proof about primes? Might be doable using modular arithmetic, again, but I can't imagine how to do that except on a case-by-case basis for each prime, which makes for an unsolvable proof not much different from merely checking every number in the non-reversed manner.
45:50 18x - 7y = 35 limited to integers is very easy: Because 35 is a multiple of 7 and you're subtracting a multiple of 7, you just need to find a multiple of 18 that's also a multiple of 7... Which is trivial (18*7 so x = 7) and then y is just 18-5 = 13 from there (the 5 is the other factor of 35). Easy for high school (and middle school!)
And then there are an infinite amount of solutions where x = 7k and y = 18k - 5
Thank you @katakana1! From the book Math Kook (p. 152): "Until recently, I thought 'irrational' was a derogatory word. I imagined ancient mathematicians arguing with each other: 'Sir, you are irrational, as are your arguments ... as are your very numbers!' But then I learned the root word of 'irrational' is 'ratio.' It just means 'un-ratio-able.' Upon hearing this, a European acquaintance told me, 'It's impossible to finish school without knowing this.' I replied that in the United States, anything is possible."
@@mathkookI also paused the video and solved this one. Good ending, honestly, after tempting my brain repeatedly with the impossible problem. :)
@@mathkook You probably did learn it in school, and then never thought about it again because the other definition is so ingrained. I'm almost certain at least one, if not all, of my high school teachers that explained irrationals did so by stressing the "ratio". I'm absolutely certain my mind thought it made perfect sense, and that by the next day I'd completely forgotten about it. Because math class would proceed to treat it as just another arbitrary label (like "imaginary"), while everything outside of math class would only use the other definition of "irrational".
Great talk Math Kook. It's amazing how many different creative approaches have been tried (and have failed). I am surprised that you say no one knows a simple proof that the only circuit cycle is the trivial cycle (1,2). Here's an outline.
If we consider only the numbers in a trajectory preceded by a larger number and followed by a larger number (ie. a "local minimum"), we can easily write an equation for the next local minimum. We can show that the only case which returns to the initial value as the next local minimum is 1.
Let s be an odd positive integer that is also a local minimum, and let m be the order of 2 in s+1, and k the order of 2 in (3/2)^m * (s + 1) - 1 (this is the largest number reached from s before any smaller number occurs). Then the next local minimum after s is
((3/2)^m * (s + 1) - 1) * (1/2)^k
Suppose s = ((3/2)^m * (s + 1) - 1) * (1/2)^k.
Some algebra produces s = (3^m - 2^m) / (2^(m+k) - 3^m) * s
which means (3^m - 2^m) / (2^(m+k) - 3^m) = 1
Gathering powers of 3 and 2 on opposite sides gives
2 * 3^m = 2^m * (1 + 2^k), or
3^m = 2^(m-1) * (1 + 2^k)
Since the 3^m is odd, the exponent (m-1) must be 0, giving m = 1 and
3 = 1 + 2^k, and therefore k = 1
So, the only circuit cycle has m = k = 1, which gives
s = ((3/2) * s + 3/2 - 1) * (1/2) = 1, the trivial cycle.
Nice! Can you show the details of your some-algebra-produces part? All I can get is s = (3^m-2)/(2^(k+1)-3^m), leading to a potential path where we have to prove there's only one (s, m, k) solution to that equation in the positive integers.
@@mathkook My sincere apologies😳 I goofed on the algebra, which in fact produces s = (3^m - 2^m) / (2^(m+k) - 3^m) (not this expression times s).
@@bradsmith3750 i know what you mean, i've been there so many times!
5:57 this feels like the halting problem, like a lot like it
Yeap it halts a lot of efforts
@@brendawilliams8062 damn hahahaha
still true though
yes otter, same thinking over here =)
Just found your channel!
New subscriber!🎉❤
I’ve done my time playing with the conjecture and it does quickly show you your limitations. It reminds me of the Halting Problem, but of course the HP only demonstrates that there is no *general* solution; it doesn’t rule out a tailored solution. In a certain sense, it means that some programs are just their own “solution” and that the ability to state a conjecture can never be taken to imply a simplified “solution.” If a program can be proven to halt, the proof is kind of isomorphic or analogous to the program itself. So I tend to think that Collatz is just one of those lovely undecidable programs that forms its own distinct continuum.
well hold up. -1 -> -2 -> -1 there's a loop that doesn't end in 1. also consider 0.
yeap, negative numbers are an extension to try to better understand it
the original sequence has natural numbers for its domain, all integer values 1 and up
there are other negative loops on SLOAN and some wikipedia discussion pages
The conjecture is about positive whole nonzero numbers mate, negatives dont necessarily loop to one but they aren't part of the conjecture so ye you're right but it doesnt prove the collatz conjecture wrong
Thank God TH-cam recommended me this great video, 47 minutes flew by really quickly
Very cool video! Have you considered making more long-form videos like these? I'd definitely watch :)
I don't get the slide on cycle length bound. What is a high cycle? Where 8.89 comes from? Doesn't make sense to me since every cycle of len 13 (and up to 11e6) has 1 as its least member.
@PedroPedruzzi Right on. (1) You can also send fractions through the Collatz rule ... try 211/13 and see what you get (a fraction is odd if its numerator is). (2) Not every fraction is a cycle member, but every cycle shape is inhabited by some set of fractions. (3) Considering all cycles with x odd terms (almost surely non-integer fractions, but who knows?) the high cycle is the one whose least member is greatest ... a truly infelicitous phrase.
@@mathkook not trying to rain on anyone's happiness here, but it is my first time reading about odds and evens with fractions.
Considering 3/7 = 6/14 I'd assume parity has to be determined with the most reduced form?
Interesting concept =)
Hi! I wanted to stop by to say this video is the best I have seen so far on this topic and thank Math Kook for it.
I personally dipped into this and happened to find a proof for the inexistence of "gliders" in 3x+1. Unfortunately publishing it isn't easy when you are not a professional mathematician, but if someone who reads this message is one and is interested I am sure we may find common ground. My paper is in French but I am fluent enough in English to translate it if needed.
Have a nice day!
T'as un discord? i'd like to know more about it
Very interesting watch, thank you!
super glad to stumble onto your channel! really cool talk!
Very entertaining talk. Thanks!
What does Life simulating 3n+1 look like? I wonder if that’ll give us any more clues. In particular, stop looking at it as a function of human counting numbers and start looking at it as dots.
Can you point me at a high resolution version of the plot you showed alongside the game of life? I'd like to stare at it a bit.
sure thing @MelindaGreen, go to math-kook-book.github.io/base2.png ... the different runs are graphically scaled to the same height, even though some runs take longer than others. (also, this is a base2 version that's clearer to read than the base10 version in the video)
Not a mathematician. Haven't seen it anywhere else, and I'm sure it isn't useful at all, but I found it interesting nonetheless.
I started by looking at the last digit only, and decided upon a sequence of that last digit say 6,3,0,5 (any will do). When you look at all the starting numbers that end with that last digit for example 6,16,26,36... 686,696, etc. and stop it when it first breaks the 6,3,0,5 sequence, the lengths of these sequences end up looking like a lined ruler with equally spaced markings.
Would it not be solved if it can be shown that all numbers reach a multiple of 2^n?
Thanks for this it was very informative!
This was an amazing video.
Are there any conjectures like this that are thought to be impossible due to checking insane amounts of numbers, but it was later proved that the solution is just stupidly large?
Yes, the sum of 3 integer cubed numbers being equal to 3.
It had 2 known solutions and it was conjectured no other solutions existed, until someone published another triplet that worked
2^15 ~ 181^2 views!
If you start with an even or odd number the sequence would produce more even numbers then odd numbers?
Great talk! Thank you 😊
Where are you getting that "collatz" numbers are not random from?
I seee the pattern. I am not able to publish because I am not endorsed. Can you please help me or check my solution. I am serious! Thanks
This is among the most beautiful problems in all of mathematics. I guess I am an alien.
I got the answer i will soon publish. Its very easy than we think...
Well I did not "Avoid it at all Costs". Rather I kept at it and did not stop. I put in all the necessary extra time that I needed until I finally solved it. The answer was NOT to give up! It also helps that I've always been a whiz in Math and I tend to look at numbers in different ways than others do. Instead of letting the numbers defeat you, you just figure them out. Anyways...
I just wanted to officially say that I Solved the Collatz Conjecture at 3:34 AM, September 26th, 2024. : )
Have a Most Wonderful Day! : )
MonsterPianoPlayer
Now that's very interesting. I wonder if you could invert it somehow. Instead of a finite sequence ending at 1, you let it be a infinite sequence starting at one. Then proving the conjecture is just proving that the sequence contains every integer.
That’s the approach I’m using!
@@KnufWons Ooh nice! I hope you give an update on how that turns out. I'd be very interested to know if it works.
that is how you generate the tree shown at the beginning
if a number is even and one more than a multiple of 3
then you can do (n-1)/3 to find out which odd number would get to it
and of course you can always include 2n for each number on the tree, as it will always be even and divide to get to n
You still have to resolve the loops question. Alf.
I thought I would be clever with my approach to do this calculation in binary, but it led to nowhere. I hoped, 3n+1 would yield a certain pattern. In the end one has to proof that 3n+1 at some point leads to a binary number which contains only a single 1, counting all digits (as powers of two collapse the 1-2-4 loop).
Never hurts to try, but it's very unlikely that a simple transformation will turn a hard problem into an easy one. Especially if it's a famous problem, where all the easy approaches have surely already been tried.
you cant change a problem by changing the base. some patterns may be more apparent to a lazy human eye in one base as opposed to another, but regardless those same patterns exist in all bases. 3n+1 is especially beautiful in binary, but ultimately the pattern boils down to the fact that you still need to solve the conjecture in order to prove the conjecture.
After messing about in binary for fun, I did see the pattern that strings of 1 lead to recurring odd numbers. It's quite fun to pick a random large number and let it run, see what'll happen.
It's actually FAR better to look at in binary, and generally considered that way. Still intractible, just more intelligibly.
The steps just become "add the number to itself, bitshifted left by 1, plus one. Then truncate all trailing zeroes. Check for 1."
So simple you could build a specialist computer chip to solve it nearly instantly for any given starting number. You're still left checking infinite starting numbers, of course. Lol
@@tristanridley1601 "add the number to itself, bitshifted left by 1, plus one" is no simpler than multiplying by 3 and adding 1; truncating all leading zeros is no simpler than dividing repeatedly by 2. Recasting it into binary doesn't make it conceptually any simpler, and it doesn't make it any easier for a computer, because everything we put into computers is encoded in binary anyway.
I've found an interesting way to map this, but no one seems to be interested. It reveals some interesting patterns.
great lecture❤
Where in real problems does that 3n+1 come from?
In the probabilistic sense, can the problem be described as always convergent, since no matter how big the number is, the odds of it never being a power of 2 is next to none due to the sheer amount of numbers it goes through?
next to none is not none.
@@ianallen738 Given that no natural number can be uncountable, a sequence can't have zero probability of being a power of 2 since the succession itself is never ending. Thus, the probability of landing in a power of 2 is non zero for every sequence since they're not finite.
@@bazooka712but they are finite, for any starting number, theres a finite set of numbers that it traverses.Yes you can extend the list infinitely with 1>4>2>1, but its not seeing new numbers, so you can, to use your argument, state that the odds of this sequence ever reaching 3 is 0%. you may have crossed 3 earlier, but theres no point continuing once the sequence has reached a number its already been too. its guaranteed to never see another number.
Even without knowing the actual truth of the collatz conjecture, we know theres 3 outcomes.
it goes to 1, and loops
it goes to itself, and loops
or it somehow extends upwards infinitely.
2 of those options see finitely many numbers, always. So you cant just say theyre not finite and use probability to make an argument
We can use probability to tell us the LIKELY answer. But not proof.
@@bazooka712 Doesnt matter because yoy need a finite counter example. Your case would only work if you were looking for an infinite number of exceptions.
For example, imagine 3 didn't work but every single other number did; your convergence would still hold.
Actually, I think you could probably find a way to encode an initial starting pattern in binary for conways game of life, and if you applied the same logic to the collatz conjecture, you could likely make interesting simulations
(1)if n is even, n := -n/2
(2)if n is odd, n := -3n + 1
(3)if n is not 1, repeat(1)(2)
for example，n = -7
-7→22→ -11→34→ -17→52→ -26→13→ -38→19→ -56→ 28→ -14→7→ -20→10→ -5 →16→ -8→4→ -2→1
I can't find counter-example.
2:22 Two Andrews disproved there were only two.
Wait a minute! At 12:48 you said that no positive whole-numbered cycles of length 3 exist. What about 4-2-1-4 ? Isn't that a cycle of length 3? What did you really mean, and where's the proof?
@dudethebagman Thanks for the reminder. I'm using the "short cut" rule that takes odds to (3n+1)/2 instead of (3n+1). So -5 goes to -7 instead of -14 (then to -7). Under the short-cut rule, the trivial loop is 2-1-2, of length 2.
Okay then. I see what you mean. It's "New Rule." The trivial loop is length 2. @@mathkook
great xkcd link :)
Too late, I am already in it!
Just change 1 + 1 to equal 3, the unity of 2 creates something new a third, do this and 3n + 1 becomes infinite
Thanks to computer scientists, we know the conjecture holds true for all numbers up to 2^69.
Actually it was 420^69
If a value in an array is checked than skip. like the Fibonacci sequence is self checking. Powers of 2 always divide.
this is how to solve problem 100 on UVa Online Judge for computer algorithm competitions
stack all value until you find a known solved n
unstack filling up the array when the index is not out of bound
repeat until you know enough for each query
cool problem and how i first heard of 3n+1 to begin with
but working this out only gives a fast way to calculate solvable numbers and detect a loop if it exists
however it does not tell us if a loop exists or if all numbers are solvable
Bruh, just because someone has a 19$ license, doesn't mean they have any prior experience in coding. Had to prove fandoms would ban those that have a lifetime license to test apps because fandoms be toxic on general populace. Proved promotion systems to be just as toxic as fandom hijackers.
But in general math & coding. I'd at least like to learn Address & directory scripting in programing. Because why not.!?
If Hex is ended in H,
Than Bin is end: I/O,
Than Octo ends: Ot?
Decimal be tagged!?
Why not just use n+1? That also goes down to one?
I think it's pretty easy to prove this one terminates, since the numbers decrease much more quickly. Starting any number n, you either go to n/2 in one step or (n+1)/2 in two steps. In both cases, you end up with a smaller number than you started with*, so you'll end up at 1 within 2lg(n) steps, and usually around 1.5lg(n) steps since you're dividing by 2 every one or two steps and I would expect the two possibilities to be roughly equally probable.
Sanity check: lg(10000)≈13.3, and 10000 goes to 1 in 20 steps (10000, 5000, 2500, 1250, 625, 626, 313, 314, 157, 158, 79, 80, 40, 20, 10, 5, 6, 3, 4, 2, 1). Almost exactly 1.5lg(10000)!
*this is only true for numbers greater than two. But 2 and 1 obviously go to 1.
I think the reason 3n+1 makes it so much harder is that the next number can either go up or down by a reasonably similar amount (either a factor of 2 or 3), whereas with the n+1 version it can go down by a factor of two but only go up by a measly constant.
@@radeklew1you are correct, half of the odds become a multiple of 2 and the other half a multiple of 4.
So it gives 3n/2 and 3n/4 for those cases, which keeps some of the starting numbers floating in a narrow range until they hit a value that likes to jump particularly high or that falls particularly fast
There's gotta be a way to make a fractal structure with this
Already done.
@@markshiman5690 do tell?
N= positive odd number.
N changes to (3N+1)/2
(3N+1)/2 could be:
1- (3N+1)/2 = positive odd integer
2- (3N+1)/2 = positive even integer
1- assume (3N+1)/2 = positive odd integer.
Since N = positive odd integer, it could be a value for (3N+1)/2
So, (3N+1)/2 = N
3N + 1 = 2N
3N - 2N = -1
N = -1, which contradicts with N = positive odd integer.
So, the assumption (3N+1)/2 = positive odd integer is false.
2- assume (3N+1)/2 = positive even integer.
Since N + 1 = positive even integer, it could be a value for (3N+1)/2
So, (3N+1)/2 = N + 1
3N + 1 = 2N + 2
3N - 2N = 2 - 1
N = 1, which does not contradict with N = positive odd integer.
So, the assumption (3N+1)/2 = positive even integer is true, and (3N+1)/2 will change to smaller value (3N+1)/4 < N, getting toward the destination 1.
If N = 1, (3N+1)/4 will equal 1, which is a term within the destination loop 1 → 2 → 1.
So, N = positive odd integer, just changes to (3N+1)/2 = positive even integer, which changes to (3N+1)/4 < N, getting toward the destination 1. So, Collatz conjecture is true.
Eng. Mahmoud Attalla.
WhatsApp: +20 1112669096.
Maybe an ever increasing sequence is somehow possible. Starting with some odd number, adding a prime factor 3, and then incrementing the number by 1, should produce a number with only one 2 prime factor. And this should remain true when doing this repeatly. It seems to be about how incrementing a number affects its prime factors.
If a number has at least one 2 (prime factor), incrementing it removes all 2's because it becomes odd. But if a number has no 2, incrementing it adds one or multiple 2's. And here the numbers should always remain such that only one 2 will be added.
So all the words in your comment are nonsense! Don't just waffle on, just tell us your solution!
I don't really think you're considering the impact of addition on factors. It pretty well scrambles them.
maybe going from the other direction could be useful. let's prove that if we take the number 1 and apply the reverse collatz, then all natural numbers can be created that way.
Good idea & one would hope! See Episode 41 for a glimpse in this direction.
thats equivalent. if you can prove it going up, you have proved it going down, and vice-versa. it makes no effective difference on the difficulty of solving the problem.
That's basically the thought behind looking at the trees.
Done that. Still have to resolve the question of possible loops. Alf.
Is the 1 million dollat prize legit? I cannot find any source of that in any trustable source. Only in a obscure web which doesn't seem to be legit
Just Google Collatz Bakuage it was in the news a couple years ago. But don't waste your time on the conjecture, as if you aren't smart enough to do basic web searches well...
leggit a tokyo company
Yes it is
I don’t know much about math. If it’s about closeness of powers; then 2 raised to a power is missing the odd numbers and prime numbers. So, if you want to find some closeness, then you have to raise those numbers to some power. So maybe there’s a better question to be asked. Anyway I found it very entertaining fiddling around with numbers.
instructions unclear, I am now out of paper
Maybe this might be a mathematically guaranteed unprovable problem... Also, thank you for the great explanation video.
john conway proved a generalization of this problem is undecidable in 1972 - en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations
his functions, however, do not use any addition, which gives them significantly different dynamics than the standard collatz conjecture
So far no one has successfully proven THAT either. Yet. Probably we'll prove one or the other eventually.
Avoid it like a hotpo tato!
Too late … the last part is too entangled and too beautiful to let go
You have displayed the 7-cycles, so why don't you say you proved the conjecture false?
They're not for the collatz conjecture (,3n+1), They're for 5n+1
And that is, in fact, a big difference (not kidding). @@FadkinsDiet
We should probably not ask an AI the answer to this in case it decides the universe needs converting into stuff better suited for answering the 3x+1 conjecture
Psshhh - I will solve it and you heard it here first!
An incomplete explanation of my proof of the Collatz conjecture is shown in the following video.
th-cam.com/video/ewZnfVO3wX8/w-d-xo.html
Dear, can I discuss about Collatz.
you cant stop me i will not avoid 3n+1
😂😂😂😂😂
(3x+1)^n / 2^n = 1
I have found multiple repeating patterns within the Collatz Conjecture
I just haven’t taken a proper class on Proof Writing so I can make a proper paper to submit
talk with a university mathematics professor. they'd help you. probably dont even have to attend that university
@@PlaceholderAlex tried. Local community college and the local university both told me that their maths departments are too busy to devote extra time with non-campus work.
It’s alright though. I’ll get there. I’m signed up with a program.
But yeah. I’ve found multiple repeating patterns. The funny thing is one set of patterns changes every time time you apply the Collatz Conjecture. EVERY. TIME. While I cannot predict what that pattern will look like, I can tell you exactly how many Odds and Evens will be in that pattern. (Note as that set of patterns approaches infinity, the quantity of Odds and Evens on the Numberline both approach a limit. 33.333…% Odd & 66.67% Even.
But the more important pattern. Makes the numberline look like a Ruler. With evenly spaced lines.
@@PlaceholderAlex in fact the Ruler Pattern is thee most important pattern. As it basically proves that at infinity, there’s an odd number with an Infinite number of Evens between the initial odd number and the next odd number.
@@HoushouRattengod Just to be clear, are you talking about a counterexample, or just some odd side patterns that you found while playing with the conjecture?
If you have a counterexample, then you shouldn't really bother reporting more than the single list of numbers in _one_ of your counterexamples (at least until someone impressed comes to you asking how you found it).
@@Tzizenorec it’s not a counter example. Just the opposite. I’m fairly certain it is the proof needed to show that all numbers will go to one.
The pattern(s) in the first section shows that as you continue to use and apply the Collatz Conjecture. The literal Numberline starts to skew towards two limits. 33.3333…% Odd and 66.67% Even
Look. 1,2,3,4, ….
The numberline before The Collatz Conjecture. 50% Odd, 50% Even. Now apply the rules. Pattern: Odd-Even,
Collatz, 1 Time (No shortcut)
4, 1, 10, 2, …
Pattern: Even-Odd-Even-Even
The pattern has doubled in size and the % of Odds:Evens is 25% Odd / 75% Even
Don’t believe me?
Watch: 5, 6, 7, 8, … -> 16, 3, 22, 4
Even-Odd-Even-Even
That’s just on applying the Collatz Conjecture once.
Do it again and you get a new pattern.
1, 2, 3, 4, 5, 6, 7, 8, … (base)
4, 1, 10, 2, 16, 3, 22, 4, … (Collatz-1 (C1))
2, 4, 5, 1, 8, 10, 11, 2, … (C2)
The pattern doubles in size a second time and changes to:
E-E-O-O-E-E-O-E
3 Odds / 5 Evens
Every time you apply the Collatz Conjecture, there is a new pattern. I cannot predict what the pattern will look like. But I can tell you that the size of the pattern is equal to 2^n , where n equals the number of times you have applied the Collatz Conjecture +1. That way the Base Integer Numberline is 2^(0+1) = 2^1
The formula for how many Odd numbers is a LOT more tricky.
But it is based on a recurrence relation formula. And basically, if you map these out, you start to see that a limit starts to appear. And that limit is 1/3 of the Numberline are Odds, and 2/3 are Even.
And while /that/ doesn’t prove the Collatz Conjecture. The process I went through to find that, is the basis of “The Ruler” pattern I have.
It might be better to model the problem with a Poset, and see if it converges.
Still a huge waste of time. Unless we can reapply the logic to another expression (ie 5x+1 )
Narrator: _But he did not, in fact, avoid the Collatz Conjecture. And so he spent countless hours on making various videos about the Collatz Conjecture, for months to no end...._
So multiplying two odd numbers results in an odd number. They make you add one to always make the result even. Then you have to divide the even numbers by 2. You will always go down because you are halving the result every time. The only reason you end up with the familiar 8-4-2-1 sequence is because of dividing by 2. This is only a result of the mechanics of math and our number system, not some mystical sequence.
It's not that simple. (3n+1)/2 is still > n. An alternating sequence of odd-even will always grow, not shrink. Easy example is n=5. You get 5->16->8, so it does increase. The question is, is there a chain that doesn't eventually hit a power of 2, and we can't know that without a more rigorous proof.
@@andrewhargreave7246 This isn't that amazing to me. The only interesting thing that happens is that sometimes when you have an even number and divide by two you get an odd number. That's just the mechanics of our number system. The rules force any odd number to become even thereby halving the number. Do it enough times and you will get to the 8-4-2-1 sequence which is ONLY divisible by 2 as per the rules. There is no upper limit to this sequence as it works on any whole number. This sequence only works with divide by two and is therefor just a curiosity and a mechanic of our number system.
@@o0Donuts0oThe conjecture interests so many people entirely because its not nearly as simple as you seem to believe. Noone has been able to prove that it always reaches 1, many people believe so, but proof of that is a lot harder to make.
As Andrew mentioned (3n+1)/2 is larger than n, and if it results in an odd number it can continue to grow. It will almost go back down again, but in doing so it may go down to the original odd number, in which case it then repeats the loop
@@o0Donuts0o someone else could argument that if you keep dividing by 2, it will be odd, and jump times 3.
Even if you divide it again, half the time you will get another odd number and become approximatedly 3n/2 from n/2 from n.
Your argument with words only is not strong enough to apply the induction principle.
More importantly, it is not strong enough to resist the flipping of terms of your own argument as i wrote above.
For example, your argument doesn't say anything about 3 being the multiplier, but 7n+1 grows to infinity.
If the multiplier matters, then your logic is either incomplete or wrong.
Over simplifying an approach only solves easy problems, this one is open for more than 75 years and some of the best mathematicians of their days tried it.
If it was that simple, it would be solved already.
@@RadeticDaniel no. You want it to be hard and mysterious. This isn’t something like solving primes. The rules are made up to make every odd number forcefully be even. And every even number divisible by two. This “puzzle” does not work if you divide by 4 or any other even number. It’s just product of our number system. It won’t work on any other base. All it shows is that if you halve certain numbers by two you may get the 8-4-2-1 sequence. Don’t make this some sort of golden ratio mysticism.
Too many words to describe the problem, transition without algebra, recursion incapable. Not worth investing time
Let F( n ) = 3n+1 if 2|n, n/2 otherwise.
Prove all natural values of n always reach 1.
That's the simplest way to describe it and it has been open for nearly 80 years.
Have fun!
P.S.: ready Tao's paper for plenty of Algebra or Conway's automaton solution attempt for another incredibly puzzling perspective
@@RadeticDaniel Let f(x) be a real valued function. If x is rational than f(x)=1, otherwise f(x)=0.. Many would say that's description of a function is ok. I would say it describes a $hit.
@@imeprezime1285 you still don't say what is wrong with the description in your opinion and either ignored or just didn't acknowledge the reference to well known researchers with papers you could probably easily find...
As far as I know even calculus books will describe the absolute value function over real numbers as
Let F( x ) = -x if x
@@RadeticDaniel You are missing the point and give a supereasy calculable example to face my example. How would you build an algorithm in order to calculate f(x) for every given x? You must know for every possible x if it is irrational or not. Math will never be able to answer that. There are problems that math simply can't solve. Collatz conjecture, Goldbach conjecture and some others are very likely such problems. Words come easy, and with them you can describe almost everything. But that's not enough to reach constructible proof in some cases (and that's hard to prove as well)
You need 99.999...% odds to stay above the start number because even numbers on average don't just get divided by 2, every multiple of 4 gets divided by 4, every multiple of 8 gets divided by 8 etc... diverges to on average even numbers get divided an infinite number of times
This "conjecture" is one of the most useless and dumbest thing that ever happened in mathematics.
It's just ridiculous that people spend time on it. I am almost certain you can generalize it to work with different iterations, some n