@@raydarable Cause as he explained in the video, an odd number multiplied by 3+1 is always even so he goes 1 step further and divides it by 2 So the formula would be : if it's even : n/2 if it's odd (3n+1)/2
I'm reminded of the wikipedia phenomenon where, if you click the first link in almost any article that isn't in parenthesis or italics, and keep doing that long enough, you will eventually end up at philosophy.
But if there is a study showing that people pick 7 or 3 as a common answer, doing the test again would result in different numbers or the same numbers. we don't know if the data is correct simply because we can't tell if people are really just randomly picking those numbers or picking them on purpose because the information they got from the initial test. i guess what i'm trying to say is the moment we "record" something is the moment that bit of information becomes irrelevant.
Also, he obviously *knew* the subject he was asking about, so he was not very likely to pick 1, 2, 4 or 8 given how short a chain that would be... 5 would also be sort of short. It just made for the best example here.
I notice that if you start with 0, you don't get to 1, but you keep looping back to 0 over and over again, since 0 is even. Also, at the end when they ask "Why not 3*n - 1?", I thought "Hey, if we do the 3*n + 1 problem with negative numbers, then if we let n = -m, where m is a positive odd number, then we get 3n + 1 = 3*(-m) + 1 = -3*m - (-1) = - (3*m - 1), and if m is even, then we get 2*n = 2*(-m) = -(2*m), so the negative cases reduce to the 3*n - 1 problem for positive n (if we take the absolute value)!"
It's amazing how many teachers shouldn't be teachers , after just paying a few minutes of attention while I was eating I just posted the solution in the comments section.
My first introduction to the problem was one of the example in former Bell Labs Unix co-pioneer Jon Bentley's book "Programming Pearls", which is a collection of columns on the theory and practice of software design he wrote for seminal comp sci journal Communications of the ACM over the years, expanded and with exercises. One of the exercises in one of the early chapters was this conjecture (in the Second Edition it's Column 4 Question 5). In the back of the book is a collection of hints. Here is the hint for this question. It has stuck with me ever since I first read it: "If you solve this problem, run to the nearest mathematics department and ask for a Ph.D."
elrak0 2 I think it's because of the "+1", adding a positive to a positive is different than adding a positive to a negative, since 5+1=6 but -5+1=-4. But I'm no math genius, so idk. For example: -5 -5(3)+1=-14 -14/2=-7 -7(3)+1=-20 -20/2=-10 -10/2=-5 Cycle repeats.
Danish Qureshi That’s exactly how it works, I believe there are four total loops fot starting at a negative(if you do a quick google search for 3n+1, you should find a Wikipedia page that has more than enough information on variation, loops, mathematics, etc.)
@@elrak0219 n could be negative, but then it wouldn't be the Collatz Conjecture. A conjecture is an educated guess in math. The collatz conjecture was an educated guess by the mathematician Lothar Collatz. The conjecture is something like, "I think that every positive whole number n goes to one under this process". While these are probably not his exact words you get the idea. He said nothing about n being negative. You could ask about negative numbers, but that is its own separate, but still interesting problem. I hope that clears things up.
What is the formula trying to decipher? Like why did they choose those numbers 3x+1 and not 4x+1 or 3x-1 and so on , what is the end game ? Is it the Only formula that always falls back to 1 and they dont know why? I'm trying to figure out what it would prove if there is a number that goes onto infinity or completely forms a separate loop , then what would that determine? Sorry for not understanding and seeing what I'm missing .
it is interesting to look at the problem with binary numbers. dividing by 2 is just binary shifting to the right, because lowest bit is 0 for even number. 3n+1 is shifting the initial number to the left, adding the original number and then add 1. the middle path is reached when the highest bit is 1 and the rest is 0. they then can be reduced to "1" by shifting to the right.
The first part of every numberphile video gets me excited to try to solve a problem, the second part convinces me that there's no point in trying because tons of people have already tried. :/
+Numberphile Can you explain to me why sequences that follow any number that solely consists of a lot of ones (like 1111111111111111111111111111111111111111111111111111111111111111111111 ) always follow the next general rule: {meaningless number}25{a lot of zeroes}4 {meaningless number}25{a lot of zeroes}2 {meaningless number}25{a lot of zeroes}1 {meaningless number}75{a lot of zeroes}4 {meaningless number}75{a lot of zeroes}2 {meaningless number}75{a lot of zeroes}1 and so on... the {meaningless number} gets bigger and the number of zeroes gets lower, until there are no more zeroes left and then the sequence turns ""normal"" like any other sequence...
+JustLikeDirt. Its a joke. Fermat wrote that he had a an elegant solution to his last theorem but the margin in the book he was studying was too small to contain it.
The cover of the book is taking a short cut. It has an arrow going from 1 to 2 so it's showing two steps n-> (3n+1)/2 (combining the multiplication and the division by 2).
I was messing around on my calculator and I think I found a similar problem. It has 3 rules. If even dived by 2, If divisible by 3 dived by 3, IF the number isn't divisible by 2 or 3 the multiply by 5 and add 1. do this and It always seems to get stuck at the loop 6, 3, 1, 6, 3, 1. Or depending on If you divided by 3 or 2 first 6 ,2, 1, 6, 2, 1. This works regardless of the number.
Thanks for ruining my life. I've been absolutely obsessed with this since the video came out and cannot function as a productive member of the society anymore.
How far did you get? I went as far as translating the function over 4x. But stopped working on it. I'm sure if I analyzed the x sequences, I'd end up just as lost as everyone else. :-) -- I prefer spending my time on the factoring problem though. It's just such a fun challenge. For anyone else who wants to play with it (yanked from my notes): Lets recap, originally we defined the function as follows: f(2n) -> n/2 f(2n+1) -> 3n+1 but with our new found knowledge we can define it further as: f(4n+0) -> n/2 f(4n+1) -> 4 * (3 * (n/4) + 1) f(4n+2) -> 4 * floor(n/8) + (2 + -1^((n/4)+1)) f(4n+3) -> 4 * (3 * (n/4) + 2) + 2
So every number is eventually gonna hit a power of 2 and is done than. Even if they tend towards infinity, they would allways somewhere hit a power of 2 and than go all the way down to 1.
But what if it gets caught in its own loop BEFORE it hits a power of 2 and drops to the ground --- for example see the extra footage linked in the description... If you use 3n-1 instead of 3n+1 that happens to 7....
+BuildA Snowman Because the only way for a number to become smaller (to become 1) is by dividing by 2, so if all will eventually get to 1 they must hit a power of 2
"I bet the person who found it thought maybe he was on to something..." I'm willing to bet the guy who found the tree for 63,728,127 wasn't sitting down and doing it 😂
When he said any fourth grader could understand it, I was like, that's probably an exaggeration. Then he explained it and sure enough I remembered reading about it in a children's math book called "Math For Smarty Pants" in elementary school.
I think the key to this conjecture takes the form of yet another such - if we find the probability of *n* either being odd or even in the simple expression *x∙y=n* (where x and y are odd and even whole numbers) then I reckon it'd just be a game of permutations from there.
My bad. Some poorly written code on my part, I forgot to set up the count properly (oops). 73 actually has 115 steps. The only number in the first 100 numbers is 5, although the number 91 comes close with 92 steps.
This only shows that it doesn't return to the same number after just one 3m+1 step, no matter how many consecutive /2 steps afterwards, except for m=1. But it doesn't exclude cycles with multiple 3m+1 steps, or the possibility that it doesn't end.
I think it has to do with an odd number multiplied by 3 adding 1 always being an even number, but an even number divided by two could give ya an odd number or another even number, so it kinda eventually forces it into powers of 2 and we all know it's downhill from there
@@kb9880 I don't think you can ever prove by doing it the hard way from here the upper limit of a diverging infinite set of " " prime values when he talks about records he's making a very important point because what is the biggest number in the list of records how can you define that as being the biggest without a sense of something greater it means nothing without the idea that there is yet another number. I was thinking this morning about this powers of two thing it's weird to see it show up in my TH-cam feed because I wasn't saying much of it out loud. I was thinking of the difference between square roots cube roots and different numerals versus decimal integers so I found the whole thing fascinating to think about but part of it was because you're dealing with recursion once you start adding a decimal and going beyond and so you're back into these recursive trees when thinking about decimal roots it's weird that this would show up I like this video.
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.
today was my first day at uni and my professor mentioned this conjecture. i was intrigued so i decided to look into it more THANKS NUMBERPHILE FOR COVERING IT
Here's another function that generates a different 'hailstone sequence': if n is divisible by 3, n/3 if n+1 is divisible by 3, 2n if n+2 is divisible by 3, 2n-1 Every positive integer eventually goes to 1.
That isn't true, since any number when entering phase of n~1(mod 3) cannot escape since 2n-1~n (mod 3) in that case, and it diverges. Perhaps you interchaned the cases of remainder being 1/2.
@@kgc0609 The remainder is never 1/2. The only division is by 3, and that only happens when it is divisible (with no remainder) by 3. There are quite a number of functions like this that generate various sequences. Collatz is the simplest I'm aware of. This function family has some other kind of deep connection that I have never been able to figure out. I once thought that if I could figure it out I could fully understand what causes these sequences to converge. But I never could. There's no way I know of to predict whether a function has the property or not, but I wasted quite a bit of time trying to figure it out.
I feel that this problem may be easy enough to find a counter example for if you could search for loops without testing any number. Maybe try plugging in 3(2x)+1=x, or other equations that show the process that might occur to any number, and if you find that a number that would, following the rules of the conjecture, normally be able to follow such a pattern, you would find a loop that hopefully does not end in 1.
Here is something I figured out: If the numbers will eventually end in a loop other than the 1-4-2 loop, it cant be in the pattern odd-even-odd-even... and so on, ending with an even and go back to the same odd number at the start. This might help!
I did some extremely precise calculations and all and here are the results. There's an infinite quantity of powers of 2 and of numbers that lead to a power of 2. Every single step you take with any number is literally just playing with fire and in the end you will get burnt.
@@drenzine My previous post included the full proof. There's no way to avoid the infinite number of death traps forever. Unless you could end up in a loop other than 1 4 2 1. Surely there's no such thing. My maths is too precise for that.
@@dmtc6913 wym by death traps? all will eventually lead to 1? just because there are an infinite amount of numbers that go to a power of two, doesn't mean other numbers will eventually branch into them. it's kind of like the that one orchard problem that numberphile covered (Tree Gaps and Orchard Problems) : in an infinite lattice grid, there is a line goes infinitely far but will miss all the lattice points if its gradient is irrational. maybe a special number is that line, and all the points are powers of two.
@@drenzine I must admit that my comments were mostly tongue in cheek, sorry. However, I can assure you with the utmost confidence that all numbers are doomed from the start. I didn't have to do any maths, I just come equipped with that knowledge. And give it out for free.
I have studied the Collatz Conjecture in my spare time. The closest thing I got to anything useful was, when n =/= 24*2^x+1, x in the integers, n going to 1 in the collatz function is equivalent to there existing integers a and b such that 4a | n+b and b | n +4a. This does work for certain n in the form of 24*2^x+1, but not all of them (ex n = 193)
Couldn't you build the tree in the opposite direction, ie. from the bottom up? In other words, start from 1 and do the reverse operations, always branching out when you can do both operations to the number.
***** Uh, no. You do the reverse operations, branching out every time you can do them both. In other words, you build the actual tree, but from bottom up.
It seems to me (although this has probably been pointed out many times) that just because (3n+1)/2 > n we do not have to show that there are more n/2's in order to reach 1. What we have to do is show that it hits some power of 2 (as then it will immediately go to 1)(the last 1/2 should be fine as hitting a power of 2 or the next power of 2 is equivalent for the purposes of going to 1). The issue then is whether this is the limiting case (all cases with more n/2's in them before a power of 2, so that there aren't equal amounts of them, will all go to a power of 2 if this one does/they will eventually goes on a track that goes to this alternating between even and odd sequence that we might be able to show goes to a power of 2, or if some do not necessarily do so and so go to infinity). However, I have a nasty feeling that actually showing this is pretty hard. But I thought I might as well throw this out there.
I just learned to make simple stuff in python yesterday and my second program was making a loop to take a random number between a set range and do this.
The numbers in the paths are on separate moduli. Take the number 7, and think of it as 128x+7 or 7 mod 128. Multiply by 3, add 1 and divide by 2 to get 192x+11 or 11 mod 192. Do that again, and you get 288x+17, then 216x+13, and 81x+5. Furthermore, you can cut out parts of these mods to show that the paths are part of even smaller moduli: 11 mod 192 is part of 11 mod 64. 17 mod 288 is part of 17 mod 32. And 13 mod 216 is part of 5 mod 8, leaving 5 mod 81 to be 2 mod 3 Because of this, we can clearly show the direction of the path along the branching tree of Collatz, and show that the number 7 (which we already knew) goes all the way to one. Generalizing it, we can show that any number above the point where we can verify has a matching pattern, a matching path, that lies within the numbers we can verify, and thus must also drop below itself to a number that has been verified, thus proving that all numbers, without exception, drop down to 1.
Rule #1 has a lowering effect on any number and outputs an even number a certain percentage of the time. While rule #2 increases the number, it always produces an even number which is reduced further. Seems obvious that the number would tend downward. One step forward and two steps back. The misdirection is that you're tripling the number half the time, that's simply not the case.
But if there was a number where the steps you take are like this: (3n+1)/2, (3n'+1)/2, (3n''+1)/2,... keep going like that forever, then the number would never reach 1.
This conjecture was in my maths test, it asked how many non-repeating primes was in the Collatz Conjecture. People failed because they thought 1 was prime
The Collatz Conjecture states that for any positive integer n, repeated application of the Collatz function f(n) = n/2 (if n is even) or f(n) = 3n+1 (if n is odd) eventually produces the number 1. To prove this, we will first show that f is a well-defined function from the positive integers N to the eventual outputs {1,1,1,...} of the Collatz function. We will then show that f is injective, meaning that different inputs produce different outputs, and that f is surjective, meaning that every output is produced by some input. This will establish that f is a bijection and hence that the sets N and {1,1,1,...} have equal cardinality, proving the Collatz Conjecture. To show that f is well-defined, suppose that we have two different sequences of Collatz function outputs that start from the same input n and eventually reach different outputs. Then, by definition of the Collatz function, these sequences must differ at some point. However, this contradicts the fact that the Collatz function is deterministic - given an input, there is only one possible output. Therefore, the Collatz function is well-defined. To show that f is injective, suppose that there exist two different inputs n and m such that f^k(n) = f^k(m) for some k ≥ 0, where f^k denotes the k-th iterate of the function f. We will show that this leads to a contradiction. Suppose that n and m have the same parity (i.e. they are both odd or both even). Then, applying the Collatz function once to both inputs produces two new inputs, either both even or both odd, which are still different from each other. Since the parity of the inputs remains the same, this process can be repeated indefinitely, producing an infinite sequence of different inputs. Therefore, if n and m have the same parity, they cannot produce the same output after repeated application of the Collatz function. Now suppose that n and m have different parity. Then, without loss of generality, suppose that n is even and m is odd. Then f(n) is even and f(m) is odd, so f^k(n) and f^k(m) will always have different parity for any k ≥ 0. Therefore, if n and m have different parity, they cannot produce the same output after repeated application of the Collatz function. In either case, we have reached a contradiction. Therefore, if n ≠ m, then f^i(n) ≠ f^i(m) for all i ≥ 0, and hence f is injective. To show that f is surjective, fix k ≥ 1. We will explicitly construct an n such that f^i(n) = k for some i ≥ 0: Let n0 = k. If n0 is even, set n1 = n0/2; otherwise, set n1 = 3n0+1. Let n2 = f(n1) (apply f to n1). Continuing in this way, we construct a sequence ni decreasing to 1. Let n be the first ni that satisfies f(ni) = ni. Then f^i(n) = k where i is the number of steps taken. To see that n exists, we note that each ni satisfies ni ≥ 1, and so the sequence ni must eventually reach 1. Moreover, since f^i(n) is strictly decreasing, there can be at most one ni satisfying f(ni) = ni. Therefore, for all k ≥ 1 we can construct an n such that f^i(n) = k for some i ≥ 0, which shows that f is surjective. Since we have shown that f is injective and surjective, we have established that f is a bijection from the positive integers N to the eventual outputs {1,1,1,...} of the Collatz function. Therefore, the sets N and {1,1,1,...} have equal cardinality, which proves the Collatz Conjecture. QED
proof: 1) we postulate that Collatz conjecture is valid as an axiom. There are axioms in mathematics, and noone can prescribe you what you can accept as am axiom 2) proof follows trivially. QED.
Actually, you can't add axioms arbitrarily. They must be consistent and independent of each other. Adding the Collatz conjecture as an axiom would only make sense if it's independent of the existing axioms of real number arithmetic (i.e., undecidable), and we don't know if that's the case. For instance, if we ever find a counterexample, we'll know that the Collatz conjecture is false, and so then we certainly can't add it as an axiom. Or, if someone proves that the conjecture is true, then it isn't an axiom either, since it would follow from the others. Of course, if you can prove that the Collatz conjecture is undecidable, then you can add it as an axiom.
@PotatoTornado You're right. If it's unprovable, then it's impossible to prove that it's unprovable, as this would imply that it is true. So, it can't be provably unprovable, but it could be unprovably unprovable. But we still can't safely stick it into arithmetic as another axiom, because this would be inconsistent if a counterexample does exist.
The next number with more steps than 63,728,127 has 1 step more and is double of it. And even though that 63 million number has 949 steps, the lowest number with over or equal to 1000 steps is 1,412,987,847 with exactly 1000 steps and is way bigger than that. And the number with the most steps that is under 4 billion is 2,610,744,987 with 1050 steps.
If one can arrive at a power of 2, or power of power of 2, etc, then one is sure to arrive at 1 eventually. Categorization of the evens based on their 'proximity' to the powers of 2 could help.
You did it!! The Collatz! Thank you! Now, I am about to be away from electronics for 9 months. At least I'll know that you guys made a video on the conjecture like I asked. I tried to prove it as an exercise. Going to watch the extra footage, of course. :)
I found a collatz calculator online and right off the bat found 2 numbers that last a long time. 447 for 80-something and 447123 which lasts for 138 iterations.
To the OP: What is the source of the graph I see in the "collage" at 2:45? It's the one in the bottom center of the screen with the red dots on white background. This is exactly the data set that I have been playing with since I first heard of this problem in my college days over 25 years ago. I'd never seen the data presented that way before, and then I saw "my" graph in your video! Thanks in advance! (and hopefully someone will see this ... :( )
If you look at (3k+1)/2. It is consistent that after some trials you will find a number that fulfills the request of (2^n). So really you’re looking for a number that doesn’t satisfy the equation (3k+1)/2 = 2^n + 2^q + 2^..... so find a number that when put into (3k+1) isn’t a series of 2, however i don’t think one exists...
I love watching your videos! They always give me something new to think about, as a future mathematician it's great to get a glimpse of what I could be working on!
I will state it here: 1: we do not care about the even numbers. They always go down. 2: all odd numbers, 1,3,5, etc., by using the formula provided 3x+1 have between them a difference of 6. With f(x) = 3x+1, f(3x+3)-f(3x+1) = 6... always. All odd numbers, if applied the formula 3x+1 have a difference of 6 between them. 1 is 4, 3 is 10, 5 is 16 etc. 3: to prove the conjecture, you need to prove that the result of the formula applied for number n at any step is lower than the odd value f(of that step + 1). Remember that (3x+1) always produces an even number. By my calculations, for a number to fail to reach 1, it needs to be lower that -13/3 (my math is bad so I might be wrong), thus, proved. Or so I think until a true mathematician hits me in the head with it.
I decided to try a graph approach to this, specifically digraphs, every vertex has two incoming edges, one representing 3n+1 for some n and one representing n/2 for some n. Additionally each vertex has one outgoing edge which goes to a vertex representing the collatz function being applied. Basically every number has two incoming edges and one outgoing edge
For any positive integer which can be reduced by the Collatz conjecture to 1, it can be proposed the special kind of equation. On the other hand If this equation can be created for the particular positive integer, this integer can be reduced by the Collatz conjecture to 1. (v1xr4 2105.0003) As another step it can be proven that such equation can be created for any particular positive integer.
I feel like there's been a video about this here before, but considering how many maths videos I watch, it's entirely possible that was someone else's video, especially since some of the people I watch occasionally appear here as well
Xkcd collatz conjecture: “if it’s odd, multiply by three and add one, if it’s even, divide by two, and eventually your friends will ask if you want to hang out”
I could be thinking about this incorrectly but, it seems to me once you touch a power of 2 you're guaranteed to fall down to 1. So the question is ultimately, is there a positive integer you can insert into this function that, no matter the iteration, would never result in a power of 2. Simple logic, it seems to me, indicates that since every positive integer can be expressed as some combination of powers of two, that this would be impossible. I could be down a rabbit hole though, I'm not a mathematician.
@Orion Hunter Oh, I meant to say that 1 + 2^(odd number) is always divisible by 3, for instance: - 2^5 + 1 = 33 - 2^7 + 1 = 129 - 2^15 + 1 = 32769 My english is pretty mediocre at best so... sorry z.z
The " collatz behavior " is first shown when converting an odd p into even using p+1 and repeating collatz process infinitely. This collatz behavior originates from 1(p)+1. This exact behavior is observed using 3p+1. But loses using 5p+1.
cant we roll this up from the back side by calculating numbers up from 1? like all the powers of 2, and deviations thereof. would guarantee completion i think
That's basically what people have in mind when they're building up those trees. The problem is, how do you prove that every single natural number appears as a node eventually?
Extremely interesting! Just going over it I can already kinda see why this is a problem. You would have to find a set of numbers either where 3n+1/2 appears more than n/2, or you'd have to find a set of numbers that creates its own tree, which would probably be an extraordinary large number considering that, as numbers increase, it's less likely that you'll get a cyclical sequence.
A cyclical sequence is inevitable as there are only six rules for finding the pivot of the 1-chain which effectively boil down to 3. The length of the cycle triples at every step up. The numbers do get huge but are consistent. Easier to talk directly.
The sequence of 2^n in the middle column is also connected to a 5, which is connected to a 3, and is then attached to a 7. This shows that all integers of the form 5(2^n), 3(2^n), 7(2^n) and 2^n are all going to collapse to one. If we can prove that at least all odd numbers end up in any of these numbers, we can prove that Collatz conjecture. The first thing is that every second number in the 5(2^n) pattern is of the form 3n + 1 where n is a positive integer. 10 reduces to 3, 40 reduces to 13, 160 reduces to 53, 640 reduces to 213. 2560 reduces to 853. They are all of the form (10(2^(2n)-1))/3. In the 7's, every second number is also of the form 3n + 1. 7 reduces to 2, 28 reduces to 9, 112 reduces to 37, 448 reduces to 149. These are all of the form (14(2^(2n)-1))/3. This shows that in x(2^n) where x is of either of the forms above, it will reduce down to one. This doesn't prove anything; feel free to mess around with it though.
When there's a still not understood randomness underlying the Collatz conjecture, couldn't you use that conjecture for encryption purposes / for creating random numbers?
If you can prove it isn't possible, then it's interesting, otherwise it's just some "it seems that..." which isn't bringing much more about this problem than what people already know
That doesn't follow. There are countably infinitely many positive integers that aren't powers of 2, and the gap between powers of 2 doubles with every power. So avoiding powers of 2 doesn't even rule out a countably infinite sequence of integers that never leads back to 1, let alone a finite loop that doesn't contain 1.
It seems that this works not only with 3x + 1, but also with a polynomial of the form mx + 1, where m is an odd number, m∈N ... Let's take x = 1 and substitute odd numbers for the coefficient m: For m = 1, everything is reduced to the cycle 2 → 1 *; For m = 3, everything is clear; For m = 5 we come to 4 → 2 → 1; For m = 7 we also get 4 → 2 → 1 * But with m = 1 and x = 2 it will turn out 4 → 2 → 1 To test the values of m> 7 and x> 1, it would be nice to write a computer program ...
I have the solution. It's very simple and elegant, the collatz conjecture is a corollary of it. I'll publish it on arxiv once i fix the lettering. I tend to reuse symbols while writing the proof.
@@usualunusualkid7149, you know I have not. I still haven't been able to get a mathematician to take me seriously enough. I'm even thinking about straight up signing up for undergrad at UC Michigan just to get access to Dr. Lagarias. I only have a minors in mathematics, my major was general science. I was only 2 or 3 classes off from having a second BS in mathematics however.
I used to think that there are only two possibilities: if you start with some number you either eventually get to 1 or the sequence would fluctuate but eventually grow to infinity. But there is one more possibility: the sequence might get to some other cycle, not 1 -> 4 -> 2 -> 1. As if you start with 7 and on some step get 7 again! Why why why it never actually happens?!!
it's pretty normal volume on my computer... I'm reluctant to start an arms war with advertisers and/or attention seekers who jack up their volume more and more... But I'll check it out.
My issue is mostly how much bass the voices have. I actually have to turn down my subwoofer to understand what you guys are saying (in a lot of videos actually), haha. Maybe that's why it's quiet for some people - all the noise is in the bass :)
Simplified 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've seen some comments here, proposing 0 as a solution to the problem. Though, 0 is a whole number, the definition of Collatz Conjecture calls for positive integers, thus we can't use 0 as an example of a number that doesn't fall to 1, because 0 is neither positive or negative integer.
It's potentially an infinite problem, so memory isn't really the issue. It's finding an efficient enough way to program it that you get a reliable answer in a reasonable amount of time...
python source code: def comes_down_to_one(x): print(f'input: {x}') steps_count = 0 while x != 1: if x % 2 == 0: x = x / 2 else: x = 3 * x + 1 print(x) steps_count += 1 print(f"steps_count: {steps_count}")
Hi, I want to offer a seemingly simple answer, though probably not new/right: 1. Any even number you continuously Divide by two will reach one. 2. What we need to show is that the division action is more dominant than the multiplication. 3. You can see that after every ‘up’ there is a ‘down’, but after a ‘down’ you can have either an ‘up’ or another ‘down’. Statistically this gives you 3 ‘up’s for every 5 ‘downs’. 4. Now, let’s say that the probability was 1 ‘up’ for 2 ‘downs’, in that case it would be easy to see why the division action is dominant. Since what you get from two successive division (/4) is more powerful than what you get from one multiplication (*3). 5. Now you can ask yourself what should the probability be in order for the actions to cancel each other out? Let’s assume extremely high numbers, so the +1 factor can be ignored. The answer is that the division (/2) should be one and a half times more probable than the multiplication (*3), in other words that for every 3 multiplications there should be 4.5 divisions. 6. Since we now that the probability exceeds that, then we can say that when reaching very high numbers the ‘down’ action will surely be more prominent. 7. Since we can see that what goes up will surely come down, but, what comes down will not surely come up, since it can get trapped in the 1-4 loop, then given enough time you will always get stuck in the loop. 8. Problem solved!
Is it also possible for some number to just get bigger and bigger as it follows the steps? (3n+1)/2>n so if the steps keep alternating, that would also be infinite. Or has it been proven that such a sequence is impossible?
+Dracarmen Winterspring its impossible, there are some numbers that get very high but they all eventually come back to 1. I think it's simply a matter of inevitability. You are dividing numbers by 2 when they are even and forcing them to be even when they're odd. eventually if you keep cutting a number in half and forcing it to be even it will have to inevitably reduce to 1.
+Dracarmen Winterspring The 3 possibilities would be: 1st: hitting 1 2nd: going towards Infinity 3rd: going into a circle that hits your starting number.
Solving it will provide a method that may be usable to solve other problems. Solution may tell us something profound about numbers that we didn't know. Math is basically nothing but the logical consequence of the concept of units. Matematicians aren't inventors, they are explorers, exploring these consequences. What to do with it is irrelevant. Fun fact: Electricity was discovered centuries before we knew what to do with it.
Why not try a proof by modified induction? E.g. Since we know the first 100 million numbers go to 1, the first 100 million even numbers go to 1 as well. This process (please correct if not do) can be extended to infinitum so all even numbers fall to 1. But then since all odd numbers are transform immediately by the function to an even number, all odd numbers must then also go to 1.
can't you answer this by contradiction, assume that there is a number that runs away to infinity, This number must be the smallest such number capable of running off to infinity This number must not have a factor of 2 and No number less than n may lead to it no number less than n therefore may lead to 2n, 2n must be 3a+3 or 3a-1 rather than 3a+1 for a an odd integer. a=1 3a-1 = 2 3a+3 = 6 a=3 3a-1 = 8 3a+3 = 12 a=k 3k-1 3k+3 a=k+2 3(k+2)-1=(3k-1)+6 3(k+2)+3=(3k+3)+6 all relevant even numbers covered by these choices (3a+3)/2 = n substitute into 3n+1 3(3a+3)/2+1 = 9a+9/2 +1 = 9a+5+1/2 9a+5+1/2 should be a whole number (and even but not divisible by 4) and 3a+3 should be a whole number (and even but not divisible by 4) if 9a+5+1/2 is a whole number then some whole number k must exist that 9a = k+1/2 Substitute 9a = k +1/2 into 3a+3 9a/3+3 = (k +1/2)/3 +3 = k/3+1/6+3 since k is a whole number any k will leave this expression with a fraction of 1/6, or 1/2 out from the whole number that should be 3a+3, this is a contradiction (3a-1)/2=n substitute into 3n+1 3(3a-1)/2+1 = 9a-3/2 +1 = 9a-1/2 9a-1/2 should be a whole number (and even but not divisible by 4) and 3a-1 should be a whole number (and even but not divisible by 4) if 9a-1/2 is a whole number then some whole number k must exist that 9a = k+1/2 Substitute 9a = k +1/2 into 3a-1 9a/3-1 = (k +1/2)/3-1 = k/3+1/6-1 since k is a whole number any k will leave this expression with a fraction of 1/6, or 1/2 out from the whole number that should be 3a+3, this is a contradiction so no integer can satisfy the equation 3a+3 or 3a-1 to give the number 2n and satisfy 3n+1 as a whole number therefore there can be no n that is run away to infinity by following the odd n -> 3n+1 even n -> n/2 I think the logic is sound but I might be wrong.
Even assuming your math is right, that wouldn't prove the conjecture. It's possible that there is a set of numbers that form a loop other than 4->2->1, which wouldn't run to infinity, but would never reach 1. The only way to prove the conjecture is to prove all values of n lead to 1, and the only way to disprove it is to find a value of n that doesn't.
Some nice arguing. You basically want to show that 3n+1 can not be a whole number if n is the smallest integer that does not eventually reach one. Obviously this can only be the case if already n is not a whole number. But you can't show that for n=(3a+3)/2. But suddenly you can if you substitute n in 3n+1. There is something smelling ;) You made a small error: 9a+5+1/2 is not equal to 3(3a+3)/2. You forgot to divide 9a by 2. The same error for the second part.
damn and that'd allow it to have whole numbers too, well that was a waste of 20 minutes, still I think there's a proof by contradiction in there somewhere, as for a cycle above the 1, 4, 2, 1 cycle I think that if you do find the smallest number that doesn't reduce to 1 is a contradiction then that'd also be proved wrong. But I've already made a mistake here so who knows
It's never a waste of time to try and prove/disprove something (within reason, of course). Imagine if all the great mathematicians never tried? We wouldn't even have Numberphile videos, lol. Props to you for trying!
Catch David on the Numberphile podcast: th-cam.com/video/9y1BGvnTyQA/w-d-xo.html
Why does the book show 1 going back to 2? Shouldn't it go to 4?
@@raydarable Cause as he explained in the video, an odd number multiplied by 3+1 is always even so he goes 1 step further and divides it by 2
So the formula would be :
if it's even : n/2
if it's odd (3n+1)/2
@@tejaspathak375 Check my comment below, I get a bit deeper into this question
@@ashkanledu2282 Thanks, didn't realize the cover was skipping that step.
Isnt this just a fractal if you layer all these solutions?
“Seven seems to be an odd number.”
That’s why he’s a maths professor.
What d u mean
@@user-sx2lc4jt1r he is clearly extremely skilled and educated in the field of mathematics
😆 😆
>_>
He's certainly no English professor. Love when people say "prehaps" (0:08) and then think they're smart.
This guy has legit the most calming and comforting voice I’ve ever heard
He reminds me of my university professor so it actually makes me nervous as it reminds me about the work I have to do damn
it’s like mathematics with Bob Ross
So frickin accurate 😤@@Asofia20
I was ready to fall asleep, but the topic was too interesting lol
This must be the formula that banks use, to calculate fees, that reduce my account to 1.
🤣🤣🤣🤣
🤣
I'm reminded of the wikipedia phenomenon where, if you click the first link in almost any article that isn't in parenthesis or italics, and keep doing that long enough, you will eventually end up at philosophy.
tried nuclear power plant ended in philosophy
tried C language, i'm looping when i reach math
they have read this :o
And your comment reminds me of the six degrees of separation.
The Wikipedia degrees of separation from Philosophy... it usually gets you there within 5-10 clicks from my experience, lol.
That's because philosophy is the source. Without philosophy, we could not be as advanced as we are. This is common knowledge to philosophers.
Also try that with Hitler
And as we learned, Brady was most likely to choose 7 out of all numbers from 1 to 10.
Actually, some studies have been done on this and turns out, if you ask people to pick a number between 1 and ten, 7 and 3 are the most common answer.
But if there is a study showing that people pick 7 or 3 as a common answer, doing the test again would result in different numbers or the same numbers. we don't know if the data is correct simply because we can't tell if people are really just randomly picking those numbers or picking them on purpose because the information they got from the initial test. i guess what i'm trying to say is the moment we "record" something is the moment that bit of information becomes irrelevant.
There's actually a video about this on this channel, that's why Vexatos said that.
Also, he obviously *knew* the subject he was asking about, so he was not very likely to pick 1, 2, 4 or 8 given how short a chain that would be... 5 would also be sort of short. It just made for the best example here.
People often pick 7, sometimes 2 or 3. People like primes and 5 is too central, it seems too obvious.
My friend in high school told me about this nearly 20 years ago, so cool to see a video about it!
I notice that if you start with 0, you don't get to 1, but you keep looping back to 0 over and over again, since 0 is even. Also, at the end when they ask "Why not 3*n - 1?", I thought "Hey, if we do the 3*n + 1 problem with negative numbers, then if we let n = -m, where m is a positive odd number, then we get 3n + 1 = 3*(-m) + 1 = -3*m - (-1) = - (3*m - 1), and if m is even, then we get 2*n = 2*(-m) = -(2*m), so the negative cases reduce to the 3*n - 1 problem for positive n (if we take the absolute value)!"
It's amazing how many teachers shouldn't be teachers , after just paying a few minutes of attention while I was eating I just posted the solution in the comments section.
@@megauser8512 0 not natural
@@megauser8512 The Conjecture is defined for Positive Integers ≥ 2
My first introduction to the problem was one of the example in former Bell Labs Unix co-pioneer Jon Bentley's book "Programming Pearls", which is a collection of columns on the theory and practice of software design he wrote for seminal comp sci journal Communications of the ACM over the years, expanded and with exercises. One of the exercises in one of the early chapters was this conjecture (in the Second Edition it's Column 4 Question 5).
In the back of the book is a collection of hints. Here is the hint for this question. It has stuck with me ever since I first read it:
"If you solve this problem, run to the nearest mathematics department and ask for a Ph.D."
Is there any reason that “n” can’t be negative? if you do it with a negative variable, it just ends up as -1 and not 1.
elrak0 2
I think it's because of the "+1", adding a positive to a positive is different than adding a positive to a negative, since 5+1=6 but -5+1=-4. But I'm no math genius, so idk.
For example:
-5
-5(3)+1=-14
-14/2=-7
-7(3)+1=-20
-20/2=-10
-10/2=-5
Cycle repeats.
Danish Qureshi That’s exactly how it works, I believe there are four total loops fot starting at a negative(if you do a quick google search for 3n+1, you should find a Wikipedia page that has more than enough information on variation, loops, mathematics, etc.)
@@elrak0219 n could be negative, but then it wouldn't be the Collatz Conjecture. A conjecture is an educated guess in math. The collatz conjecture was an educated guess by the mathematician Lothar Collatz. The conjecture is something like, "I think that every positive whole number n goes to one under this process". While these are probably not his exact words you get the idea. He said nothing about n being negative.
You could ask about negative numbers, but that is its own separate, but still interesting problem. I hope that clears things up.
What is the formula trying to decipher? Like why did they choose those numbers 3x+1 and not 4x+1 or 3x-1 and so on , what is the end game ? Is it the Only formula that always falls back to 1 and they dont know why? I'm trying to figure out what it would prove if there is a number that goes onto infinity or completely forms a separate loop , then what would that determine? Sorry for not understanding and seeing what I'm missing .
"Wow... 16, very even number!"
Because it's a power of 2!
That's right: it's quadruple even.
Shut up
Square root, fourth root, divide by two, divide by four
Your problem??
it is interesting to look at the problem with binary numbers. dividing by 2 is just binary shifting to the right, because lowest bit is 0 for even number. 3n+1 is shifting the initial number to the left, adding the original number and then add 1. the middle path is reached when the highest bit is 1 and the rest is 0. they then can be reduced to "1" by shifting to the right.
Man I chose 4 initially. Worst possible number…
i chose 1. :P
Jim Cullen 2
4 goes to 2. 2 goes to 1.
I chose 0.
I picked 8.
what about the 360 noscope conjecture tho
link pls, I want to see this dank conjecture
360j -n +s = 360nc
j= jump... n= n0sc0pe... s= sh0t... c= c0njecture
I leave it t0 y0u t0 s0lve... if y0u can write this int0 a sentence, y0u win
The 360 noscope conjecture equals a number between 360 and Conjecture.
MLG pro only
it always goes off to 420
The first part of every numberphile video gets me excited to try to solve a problem, the second part convinces me that there's no point in trying because tons of people have already tried. :/
Thank you for making this video!
+Jake S (blu4) thank you for watching it. Please show your friends. :)
+Numberphile Ok (no)
wat
Nissan > Suzuki
+Numberphile Can you explain to me why sequences that follow any number that solely consists of a lot of ones (like 1111111111111111111111111111111111111111111111111111111111111111111111 ) always follow the next general rule:
{meaningless number}25{a lot of zeroes}4
{meaningless number}25{a lot of zeroes}2
{meaningless number}25{a lot of zeroes}1
{meaningless number}75{a lot of zeroes}4
{meaningless number}75{a lot of zeroes}2
{meaningless number}75{a lot of zeroes}1
and so on...
the {meaningless number} gets bigger and the number of zeroes gets lower, until there are no more zeroes left and then the sequence turns ""normal"" like any other sequence...
*" Don't Judge a b̶o̶o̶k̶ problem by its c̶o̶v̶e̶r̶ statement "*
*- Collatz Conjecture*
Genius!
I found a counterexample, but the comment section is too small to contain it :P
Then your lying, or else you would take every way possible to show everyone collaz is wrong. Stop faking smarts to get attention.
+JustLikeDirt I think you missed Ijfa's reference...
+JustLikeDirt. Its a joke. Fermat wrote that he had a an elegant solution to his last theorem but the margin in the book he was studying was too small to contain it.
+JustLikeDirt it's a joke. it's what Fermat did about his theorem
made my day
The cover of the book is taking a short cut. It has an arrow going from 1 to 2 so it's showing two steps n-> (3n+1)/2 (combining the multiplication and the division by 2).
I have a truely marvelous proof to the collaz conjecture whitch this planet is too small to contain
)))))actually, math is going to end in this way for every single new proof someday)))))))
Outstanding move
Fermat is everywhere
Is that you, Fermat?
Aaahhh! Zombie Fermat!
I was messing around on my calculator and I think I found a similar problem. It has 3 rules. If even dived by 2, If divisible by 3 dived by 3, IF the number isn't divisible by 2 or 3 the multiply by 5 and add 1. do this and It always seems to get stuck at the loop 6, 3, 1, 6, 3, 1. Or depending on If you divided by 3 or 2 first 6 ,2, 1, 6, 2, 1. This works regardless of the number.
The Garrett guesstimate ?
Thanks for ruining my life. I've been absolutely obsessed with this since the video came out and cannot function as a productive member of the society anymore.
i feel your anguish
so does he still find a pattern?
Burak Bağdatlı zero will not result in one
How far did you get? I went as far as translating the function over 4x. But stopped working on it. I'm sure if I analyzed the x sequences, I'd end up just as lost as everyone else. :-) -- I prefer spending my time on the factoring problem though. It's just such a fun challenge.
For anyone else who wants to play with it (yanked from my notes):
Lets recap, originally we defined the function as follows:
f(2n) -> n/2
f(2n+1) -> 3n+1
but with our new found knowledge we can define it further as:
f(4n+0) -> n/2
f(4n+1) -> 4 * (3 * (n/4) + 1)
f(4n+2) -> 4 * floor(n/8) + (2 + -1^((n/4)+1))
f(4n+3) -> 4 * (3 * (n/4) + 2) + 2
Don't solve it before me! lol
I've been working hard on it. I keep thinking I have a thread on a solution.
0:16 He chose seven on purpose! He knows it's the least random number! Bold strategy.
So every number is eventually gonna hit a power of 2 and is done than. Even if they tend towards infinity, they would allways somewhere hit a power of 2 and than go all the way down to 1.
But what if it gets caught in its own loop BEFORE it hits a power of 2 and drops to the ground --- for example see the extra footage linked in the description... If you use 3n-1 instead of 3n+1 that happens to 7....
Why would they always hit a power of two?
Maybe. We assume it is true, and all our evidence so far points to it being true, but we can't prove that it is.
This is mathematics that involves powers of 2. Something math could do but not us humans
+BuildA Snowman Because the only way for a number to become smaller (to become 1) is by dividing by 2, so if all will eventually get to 1 they must hit a power of 2
"I bet the person who found it thought maybe he was on to something..."
I'm willing to bet the guy who found the tree for 63,728,127 wasn't sitting down and doing it 😂
Hold my java program for finding the steps
When he said any fourth grader could understand it, I was like, that's probably an exaggeration. Then he explained it and sure enough I remembered reading about it in a children's math book called "Math For Smarty Pants" in elementary school.
Ha, awesome.
I think the key to this conjecture takes the form of yet another such - if we find the probability of *n* either being odd or even in the simple expression *x∙y=n* (where x and y are odd and even whole numbers) then I reckon it'd just be a game of permutations from there.
I actually bet my friend 20$ that he couldn't do the 3n + 1 without getting to one
I won the bet
xD
I am working on Prime numbers and I am amazed to see your expression they are extremely useful in my work Thank you man
73 takes 73 steps to reach 1
+Stephen H I've not checked but of so, that's awesome. How many numbers have that property?
so many questions can be made.. damn
My bad. Some poorly written code on my part, I forgot to set up the count properly (oops). 73 actually has 115 steps. The only number in the first 100 numbers is 5, although the number 91 comes close with 92 steps.
73 takes 73 steps if you use the shortcut he mentioned to do (n*3+1)/2 as one step
For n = {1 ... 9999}, the highest number ever reached is 27,114,424, which happens at n = 9663, step #48 of an astounding 183 steps.
=====
N = 9663
=====
9663
28990
14495
43486
21743
65230
32615
97846
48923
146770
73385
220156
110078
55039
165118
82559
247678
123839
371518
185759
557278
278639
835918
417959
1253878
626939
1880818
940409
2821228
1410614
705307
2115922
1057961
3173884
1586942
793471
2380414
1190207
3570622
1785311
5355934
2677967
8033902
4016951
12050854
6025427
18076282
9038141
27114424
13557212
6778606
3389303
10167910
5083955
15251866
7625933
22877800
11438900
5719450
2859725
8579176
4289588
2144794
1072397
3217192
1608596
804298
402149
1206448
603224
301612
150806
75403
226210
113105
339316
169658
84829
254488
127244
63622
31811
95434
47717
143152
71576
35788
17894
8947
26842
13421
40264
20132
10066
5033
15100
7550
3775
11326
5663
16990
8495
25486
12743
38230
19115
57346
28673
86020
43010
21505
64516
32258
16129
48388
24194
12097
36292
18146
9073
27220
13610
6805
20416
10208
5104
2552
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
Highest: 27114424
This is literally just "4 is cosmic" in math form lol I appreciate that very much.
Reciprocal of (3m+1)/2^n rule of Collatz conjecture is (2^n*m-1)/3, can use (2^n*m-1)/3=m for both, it's only solution is m=1.
This only shows that it doesn't return to the same number after just one 3m+1 step, no matter how many consecutive /2 steps afterwards, except for m=1. But it doesn't exclude cycles with multiple 3m+1 steps, or the possibility that it doesn't end.
Please post more videos Enlong
I like how it started like the fibonacci sequence; 1, 1, 2, 3, 5.
I wonder if it follows that pattern even longer with a bigger tree..
I think it has to do with an odd number multiplied by 3 adding 1 always being an even number, but an even number divided by two could give ya an odd number or another even number, so it kinda eventually forces it into powers of 2 and we all know it's downhill from there
Yeah that's the intuition behind the "conjecture" but we can't prove that eventually it will reach powers of two.
@@kb9880 I don't think you can ever prove by doing it the hard way from here the upper limit of a diverging infinite set of " " prime values when he talks about records he's making a very important point because what is the biggest number in the list of records how can you define that as being the biggest without a sense of something greater it means nothing without the idea that there is yet another number. I was thinking this morning about this powers of two thing it's weird to see it show up in my TH-cam feed because I wasn't saying much of it out loud. I was thinking of the difference between square roots cube roots and different numerals versus decimal integers so I found the whole thing fascinating to think about but part of it was because you're dealing with recursion once you start adding a decimal and going beyond and so you're back into these recursive trees when thinking about decimal roots it's weird that this would show up I like this video.
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.
today was my first day at uni and my professor mentioned this conjecture. i was intrigued so i decided to look into it more THANKS NUMBERPHILE FOR COVERING IT
I didn't know that mathematics had a Bob Ross.
Homeboy mentions trees, clouds, and visual patterns in his explanation.
Here's another function that generates a different 'hailstone sequence':
if n is divisible by 3, n/3
if n+1 is divisible by 3, 2n
if n+2 is divisible by 3, 2n-1
Every positive integer eventually goes to 1.
That isn't true, since any number when entering phase of n~1(mod 3) cannot escape since 2n-1~n (mod 3) in that case, and it diverges. Perhaps you interchaned the cases of remainder being 1/2.
@@kgc0609 The remainder is never 1/2. The only division is by 3, and that only happens when it is divisible (with no remainder) by 3.
There are quite a number of functions like this that generate various sequences. Collatz is the simplest I'm aware of.
This function family has some other kind of deep connection that I have never been able to figure out.
I once thought that if I could figure it out I could fully understand what causes these sequences to converge. But I never could. There's no way I know of to predict whether a function has the property or not, but I wasted quite a bit of time trying to figure it out.
Is it just me, or is the quality of comments on this one weaker than usual? ;)
Michael Bauers Noticed that too. Thought I would see more educated comments.
Roses are red, Violets are blue, 3n+1, Is eventually 2. Or maybe "Or divide it by 2".
(raises champagne glass) I found 21 to be amusing... But 27 simply did not know when to stop!
I feel that this problem may be easy enough to find a counter example for if you could search for loops without testing any number. Maybe try plugging in 3(2x)+1=x, or other equations that show the process that might occur to any number, and if you find that a number that would, following the rules of the conjecture, normally be able to follow such a pattern, you would find a loop that hopefully does not end in 1.
Hey it’s been 5 years, did you manage to solve the Collatz conjecture?
lol@@JHashcroft
Surely 6 years was sufficient to find your counter example. After all, you said it's easy enough.
Let's hear it.
Here is something I figured out: If the numbers will eventually end in a loop other than the 1-4-2 loop, it cant be in the pattern odd-even-odd-even... and so on, ending with an even and go back to the same odd number at the start. This might help!
I did some extremely precise calculations and all and here are the results. There's an infinite quantity of powers of 2 and of numbers that lead to a power of 2. Every single step you take with any number is literally just playing with fire and in the end you will get burnt.
@@dmtc6913 so you solved it or somethin?
@@drenzine My previous post included the full proof. There's no way to avoid the infinite number of death traps forever. Unless you could end up in a loop other than 1 4 2 1. Surely there's no such thing. My maths is too precise for that.
@@dmtc6913 wym by death traps? all will eventually lead to 1? just because there are an infinite amount of numbers that go to a power of two, doesn't mean other numbers will eventually branch into them. it's kind of like the that one orchard problem that numberphile covered (Tree Gaps and Orchard Problems) : in an infinite lattice grid, there is a line goes infinitely far but will miss all the lattice points if its gradient is irrational. maybe a special number is that line, and all the points are powers of two.
@@drenzine I must admit that my comments were mostly tongue in cheek, sorry.
However, I can assure you with the utmost confidence that all numbers are doomed from the start. I didn't have to do any maths, I just come equipped with that knowledge. And give it out for free.
I have studied the Collatz Conjecture in my spare time. The closest thing I got to anything useful was, when n =/= 24*2^x+1, x in the integers, n going to 1 in the collatz function is equivalent to there existing integers a and b such that 4a | n+b and b | n +4a. This does work for certain n in the form of 24*2^x+1, but not all of them (ex n = 193)
Couldn't you build the tree in the opposite direction, ie. from the bottom up? In other words, start from 1 and do the reverse operations, always branching out when you can do both operations to the number.
Yes you can. But it doesn't help.
Treufuß
It helps building a complete tree up to a certain depth, which will then help you with further calculations.
*****
Uh, no. You do the reverse operations, branching out every time you can do them both.
In other words, you build the actual tree, but from bottom up.
I think I saw a program that did that when I searched for more videos on the subject on youtube earlier
+WarpRulez You would only be getting even numbers
It seems to me (although this has probably been pointed out many times) that just because (3n+1)/2 > n we do not have to show that there are more n/2's in order to reach 1. What we have to do is show that it hits some power of 2 (as then it will immediately go to 1)(the last 1/2 should be fine as hitting a power of 2 or the next power of 2 is equivalent for the purposes of going to 1).
The issue then is whether this is the limiting case (all cases with more n/2's in them before a power of 2, so that there aren't equal amounts of them, will all go to a power of 2 if this one does/they will eventually goes on a track that goes to this alternating between even and odd sequence that we might be able to show goes to a power of 2, or if some do not necessarily do so and so go to infinity).
However, I have a nasty feeling that actually showing this is pretty hard. But I thought I might as well throw this out there.
I just learned to make simple stuff in python yesterday and my second program was making a loop to take a random number between a set range and do this.
why do they always draw on brown toilet papers?
That's clearly not toilet paper
Who poops on brown paper?
Remind me to never use a bathroom where you live if that's what the toilet paper is like
iiDioxide Brown toilet paper, to use your vocabulary, is the iconic symbol of Numberphile.
it's cheap.
If a number is to not reach one, a constraint is that it must be congruent to 63 mod 96.
Why?
I don't believe you. Prove it to me.
??
?
@@official-obama yeah but we dont care about non-positive integers
I see why it tends towards 1: 2>1.5+c (for all big numbers and all small are checked)
but I wonder what keeps it from ever entering a loop...
The numbers in the paths are on separate moduli. Take the number 7, and think of it as 128x+7 or 7 mod 128. Multiply by 3, add 1 and divide by 2 to get 192x+11 or 11 mod 192.
Do that again, and you get 288x+17, then 216x+13, and 81x+5. Furthermore, you can cut out parts of these mods to show that the paths are part of even smaller moduli:
11 mod 192 is part of 11 mod 64. 17 mod 288 is part of 17 mod 32. And 13 mod 216 is part of 5 mod 8, leaving 5 mod 81 to be 2 mod 3
Because of this, we can clearly show the direction of the path along the branching tree of Collatz, and show that the number 7 (which we already knew) goes all the way to one.
Generalizing it, we can show that any number above the point where we can verify has a matching pattern, a matching path, that lies within the numbers we can verify, and thus must also drop below itself to a number that has been verified, thus proving that all numbers, without exception, drop down to 1.
Finally!! A video about the 3x+1 problem :) Liked
i'm gonna call all the powers of 2 "very even numbers" from now on, thanks professor
Rule #1 has a lowering effect on any number and outputs an even number a certain percentage of the time. While rule #2 increases the number, it always produces an even number which is reduced further. Seems obvious that the number would tend downward. One step forward and two steps back. The misdirection is that you're tripling the number half the time, that's simply not the case.
Agree completely.
But if there was a number where the steps you take are like this: (3n+1)/2, (3n'+1)/2, (3n''+1)/2,... keep going like that forever, then the number would never reach 1.
This conjecture was in my maths test, it asked how many non-repeating primes was in the Collatz Conjecture. People failed because they thought 1 was prime
The Collatz Conjecture states that for any positive integer n, repeated application of the Collatz function f(n) = n/2 (if n is even) or f(n) = 3n+1 (if n is odd) eventually produces the number 1.
To prove this, we will first show that f is a well-defined function from the positive integers N to the eventual outputs {1,1,1,...} of the Collatz function. We will then show that f is injective, meaning that different inputs produce different outputs, and that f is surjective, meaning that every output is produced by some input. This will establish that f is a bijection and hence that the sets N and {1,1,1,...} have equal cardinality, proving the Collatz Conjecture.
To show that f is well-defined, suppose that we have two different sequences of Collatz function outputs that start from the same input n and eventually reach different outputs. Then, by definition of the Collatz function, these sequences must differ at some point. However, this contradicts the fact that the Collatz function is deterministic - given an input, there is only one possible output. Therefore, the Collatz function is well-defined.
To show that f is injective, suppose that there exist two different inputs n and m such that f^k(n) = f^k(m) for some k ≥ 0, where f^k denotes the k-th iterate of the function f. We will show that this leads to a contradiction.
Suppose that n and m have the same parity (i.e. they are both odd or both even). Then, applying the Collatz function once to both inputs produces two new inputs, either both even or both odd, which are still different from each other. Since the parity of the inputs remains the same, this process can be repeated indefinitely, producing an infinite sequence of different inputs. Therefore, if n and m have the same parity, they cannot produce the same output after repeated application of the Collatz function.
Now suppose that n and m have different parity. Then, without loss of generality, suppose that n is even and m is odd. Then f(n) is even and f(m) is odd, so f^k(n) and f^k(m) will always have different parity for any k ≥ 0. Therefore, if n and m have different parity, they cannot produce the same output after repeated application of the Collatz function.
In either case, we have reached a contradiction. Therefore, if n ≠ m, then f^i(n) ≠ f^i(m) for all i ≥ 0, and hence f is injective.
To show that f is surjective, fix k ≥ 1. We will explicitly construct an n such that f^i(n) = k for some i ≥ 0:
Let n0 = k. If n0 is even, set n1 = n0/2; otherwise, set n1 = 3n0+1.
Let n2 = f(n1) (apply f to n1). Continuing in this way, we construct a sequence ni decreasing to 1.
Let n be the first ni that satisfies f(ni) = ni. Then f^i(n) = k where i is the number of steps taken.
To see that n exists, we note that each ni satisfies ni ≥ 1, and so the sequence ni must eventually reach 1. Moreover, since f^i(n) is strictly decreasing, there can be at most one ni satisfying f(ni) = ni. Therefore, for all k ≥ 1 we can construct an n such that f^i(n) = k for some i ≥ 0, which shows that f is surjective.
Since we have shown that f is injective and surjective, we have established that f is a bijection from the positive integers N to the eventual outputs {1,1,1,...} of the Collatz function. Therefore, the sets N and {1,1,1,...} have equal cardinality, which proves the Collatz Conjecture.
QED
2:50 to the right, it's not a paper, It's an XKCD comic.
it's comic on the collatz conjecture
Well-spotted! Don't think I'm familiar with that page, I'll have to Google it later!
lol I saw that too
proof:
1) we postulate that Collatz conjecture is valid as an axiom. There are axioms in mathematics, and noone can prescribe you what you can accept as am axiom
2) proof follows trivially.
QED.
Harvard: You want a free scholarship?
the problem is not just proving it, the problem is proving it using the given axioms
But then you have to prove it IS an axiom and not a property derived and provable from other properties. Math works that way.
Actually, you can't add axioms arbitrarily. They must be consistent and independent of each other. Adding the Collatz conjecture as an axiom would only make sense if it's independent of the existing axioms of real number arithmetic (i.e., undecidable), and we don't know if that's the case. For instance, if we ever find a counterexample, we'll know that the Collatz conjecture is false, and so then we certainly can't add it as an axiom. Or, if someone proves that the conjecture is true, then it isn't an axiom either, since it would follow from the others. Of course, if you can prove that the Collatz conjecture is undecidable, then you can add it as an axiom.
@PotatoTornado You're right. If it's unprovable, then it's impossible to prove that it's unprovable, as this would imply that it is true. So, it can't be provably unprovable, but it could be unprovably unprovable.
But we still can't safely stick it into arithmetic as another axiom, because this would be inconsistent if a counterexample does exist.
The next number with more steps than 63,728,127 has 1 step more and is double of it.
And even though that 63 million number has 949 steps, the lowest number with over or equal to 1000 steps is 1,412,987,847 with exactly 1000 steps and is way bigger than that.
And the number with the most steps that is under 4 billion is 2,610,744,987 with 1050 steps.
5:43 and then eVENTUALLY
eV *ENT* U A ll y
Your point?
"I've become more powerful than any jedi."
Twice the pride double the fall
If one can arrive at a power of 2, or power of power of 2, etc, then one is sure to arrive at 1 eventually. Categorization of the evens based on their 'proximity' to the powers of 2 could help.
You did it!! The Collatz! Thank you! Now, I am about to be away from electronics for 9 months. At least I'll know that you guys made a video on the conjecture like I asked. I tried to prove it as an exercise. Going to watch the extra footage, of course. :)
1:26 I always knew no one uses multiplication tables!!😃
No, he just broke it down into something that fit in the (US) multiplication tables.
I found a collatz calculator online and right off the bat found 2 numbers that last a long time. 447 for 80-something and 447123 which lasts for 138 iterations.
2:36
I've done checking 10 ^ 100 + 1 on my pc and it still got 1.
A googol plus one. Down to ONE.
how many steps?
@@inx1819 It only takes 2173 steps. What's kinda interesting is that 10^100 + 2 and 10^100 + 3 also take this many steps
@@Quantris yeah I made a program for that as well, it was pretty fun. got the same results
To the OP: What is the source of the graph I see in the "collage" at 2:45? It's the one in the bottom center of the screen with the red dots on white background. This is exactly the data set that I have been playing with since I first heard of this problem in my college days over 25 years ago. I'd never seen the data presented that way before, and then I saw "my" graph in your video! Thanks in advance! (and hopefully someone will see this ... :( )
I have seen that graph on the Wikipedia page for collate conjecture and I am sure they list a source
If you look at (3k+1)/2. It is consistent that after some trials you will find a number that fulfills the request of (2^n). So really you’re looking for a number that doesn’t satisfy the equation (3k+1)/2 = 2^n + 2^q + 2^..... so find a number that when put into (3k+1) isn’t a series of 2, however i don’t think one exists...
2^950
Now i just need a universe large enough.
Maybe ill find a lever large enough there too. 🎣🎣🎣
You can:
2^950 = 9516908214257811601907599988159363584840065290620124537956939899622020205826587990689077212775400643774711832257235027522909345571487396529861315719055325605011013378863743193233193022939505515969530853007049198118833591724018432564205433218231411731277088674906521042072098232413978624
Steps 950
I love watching your videos! They always give me something new to think about, as a future mathematician it's great to get a glimpse of what I could be working on!
I think I may have found the solution. Not sure what to do with it. It's a constant: 6
I will state it here:
1: we do not care about the even numbers. They always go down.
2: all odd numbers, 1,3,5, etc., by using the formula provided 3x+1 have between them a difference of 6. With f(x) = 3x+1, f(3x+3)-f(3x+1) = 6... always. All odd numbers, if applied the formula 3x+1 have a difference of 6 between them. 1 is 4, 3 is 10, 5 is 16 etc.
3: to prove the conjecture, you need to prove that the result of the formula applied for number n at any step is lower than the odd value f(of that step + 1). Remember that (3x+1) always produces an even number. By my calculations, for a number to fail to reach 1, it needs to be lower that -13/3 (my math is bad so I might be wrong), thus, proved. Or so I think until a true mathematician hits me in the head with it.
@@ManticoreRO "my math is bad so I might be wrong" 🤣🤣
"If they never get to earth, of course, they're not hailstones."
😄😁😆
I decided to try a graph approach to this, specifically digraphs, every vertex has two incoming edges, one representing 3n+1 for some n and one representing n/2 for some n. Additionally each vertex has one outgoing edge which goes to a vertex representing the collatz function being applied. Basically every number has two incoming edges and one outgoing edge
For any positive integer which can be reduced by the Collatz conjecture to 1, it can be proposed the special kind of equation. On the other hand If this equation can be created for the particular positive integer, this integer can be reduced by the Collatz conjecture to 1. (v1xr4 2105.0003) As another step it can be proven that such equation can be created for any particular positive integer.
I feel like there's been a video about this here before, but considering how many maths videos I watch, it's entirely possible that was someone else's video, especially since some of the people I watch occasionally appear here as well
Yeah. I remember seeing this recently as well, but a search for "collatz" doesn't turn up any videos I've watched recently.
Pretty confident they've never ever covered this.
Xkcd collatz conjecture: “if it’s odd, multiply by three and add one, if it’s even, divide by two, and eventually your friends will ask if you want to hang out”
Lol nice one
Laksh Sind just remember, xkcd came up with it
your friends will stop* calling to see if you want to hang out lol
I could be thinking about this incorrectly but, it seems to me once you touch a power of 2 you're guaranteed to fall down to 1. So the question is ultimately, is there a positive integer you can insert into this function that, no matter the iteration, would never result in a power of 2.
Simple logic, it seems to me, indicates that since every positive integer can be expressed as some combination of powers of two, that this would be impossible. I could be down a rabbit hole though, I'm not a mathematician.
The only pattern I see is that powers of two with even exponential, once you subtract one, become odd numbers that can be divided by 3.
If you have odd powers of two and add one, that number is divisible by 3
This is a result in number theory which is more formally defined as 4^x-1|3
@@cuentafake140 subtract* Also the only odd power of two is 1
@Orion Hunter Oh, I meant to say that 1 + 2^(odd number) is always divisible by 3, for instance:
- 2^5 + 1 = 33
- 2^7 + 1 = 129
- 2^15 + 1 = 32769
My english is pretty mediocre at best so... sorry z.z
Thanks for the book reference. I ordered it!
The " collatz behavior " is first shown when converting an odd p into even using p+1 and repeating collatz process infinitely.
This collatz behavior originates from 1(p)+1.
This exact behavior is observed using 3p+1. But loses using 5p+1.
cant we roll this up from the back side by calculating numbers up from 1? like all the powers of 2, and deviations thereof.
would guarantee completion i think
That's basically what people have in mind when they're building up those trees. The problem is, how do you prove that every single natural number appears as a node eventually?
@@lonestarr1490 Exactly. 1, 2, 3, 4, 5... they all come in very quickly. but 27 dooesn't appear until after the 60th ROW of numbers.
what a lovely teacher.
Extremely interesting! Just going over it I can already kinda see why this is a problem. You would have to find a set of numbers either where 3n+1/2 appears more than n/2, or you'd have to find a set of numbers that creates its own tree, which would probably be an extraordinary large number considering that, as numbers increase, it's less likely that you'll get a cyclical sequence.
A cyclical sequence is inevitable as there are only six rules for finding the pivot of the 1-chain which effectively boil down to 3. The length of the cycle triples at every step up. The numbers do get huge but are consistent. Easier to talk directly.
Stop with all the "first" comments, it accomplishes nothing and wastes your time.
By the way why won't Brady start another podcast, or has he got too much work already?
+Sebastian Karlsson just had to get it out of my system, it frustrates me.
reading your useless comment and replying to it was a bigger waste if time, thanks :/
First
first
The sequence of 2^n in the middle column is also connected to a 5, which is connected to a 3, and is then attached to a 7. This shows that all integers of the form 5(2^n), 3(2^n), 7(2^n) and 2^n are all going to collapse to one. If we can prove that at least all odd numbers end up in any of these numbers, we can prove that Collatz conjecture.
The first thing is that every second number in the 5(2^n) pattern is of the form 3n + 1 where n is a positive integer. 10 reduces to 3, 40 reduces to 13, 160 reduces to 53, 640 reduces to 213. 2560 reduces to 853. They are all of the form (10(2^(2n)-1))/3. In the 7's, every second number is also of the form 3n + 1. 7 reduces to 2, 28 reduces to 9, 112 reduces to 37, 448 reduces to 149. These are all of the form (14(2^(2n)-1))/3. This shows that in x(2^n) where x is of either of the forms above, it will reduce down to one.
This doesn't prove anything; feel free to mess around with it though.
When there's a still not understood randomness underlying the Collatz conjecture, couldn't you use that conjecture for encryption purposes / for creating random numbers?
It’s not exactly the most efficient way of screwing around with cryptanalysts.
Any counter example would have to avoid any exponent of 2. Doesn't seem possible.
If you can prove it isn't possible, then it's interesting, otherwise it's just some "it seems that..." which isn't bringing much more about this problem than what people already know
It's possible with a loop, which is the main thing you have to prove. How do you prove no number except 1 ever returns to itself?
I don't wanna name my channel i have a proof don't call me a liar
Evidence or it never happened...
"Lawyer, Lawyer!" :P
That doesn't follow. There are countably infinitely many positive integers that aren't powers of 2, and the gap between powers of 2 doubles with every power. So avoiding powers of 2 doesn't even rule out a countably infinite sequence of integers that never leads back to 1, let alone a finite loop that doesn't contain 1.
It seems that this works not only with 3x + 1, but also with a polynomial of the form mx + 1, where m is an odd number, m∈N ...
Let's take x = 1 and substitute odd numbers for the coefficient m:
For m = 1, everything is reduced to the cycle 2 → 1 *;
For m = 3, everything is clear;
For m = 5 we come to 4 → 2 → 1;
For m = 7 we also get 4 → 2 → 1
* But with m = 1 and x = 2 it will turn out 4 → 2 → 1
To test the values of m> 7 and x> 1, it would be nice to write a computer program ...
I hope that 7,382,036,203,215,362,117 works! Can someone check? ;)
7,382,036,203,215,362,117 terminates after 492 iterations
How in the world did you figure that out so quickly? Wow! I was just fooling around when I said that number.
maybe it programmed something to check it
He probably wrote a program to calculate it
Computers are really fast
I have the solution. It's very simple and elegant, the collatz conjecture is a corollary of it. I'll publish it on arxiv once i fix the lettering. I tend to reuse symbols while writing the proof.
are you kidding... or???
@@АбдаллахМуслим no. Seems weird that i would kid.
@@ZolarV Have you finished it yet?
@@usualunusualkid7149, you know I have not. I still haven't been able to get a mathematician to take me seriously enough. I'm even thinking about straight up signing up for undergrad at UC Michigan just to get access to Dr. Lagarias.
I only have a minors in mathematics, my major was general science. I was only 2 or 3 classes off from having a second BS in mathematics however.
I used to think that there are only two possibilities: if you start with some number you either eventually get to 1 or the sequence would fluctuate but eventually grow to infinity. But there is one more possibility: the sequence might get to some other cycle, not 1 -> 4 -> 2 -> 1. As if you start with 7 and on some step get 7 again!
Why why why it never actually happens?!!
Brady please! your videos are so quiet. I love the material, but it's so hard to hear. then the ad for the next video blows up my ears.
it's pretty normal volume on my computer... I'm reluctant to start an arms war with advertisers and/or attention seekers who jack up their volume more and more... But I'll check it out.
My issue is mostly how much bass the voices have. I actually have to turn down my subwoofer to understand what you guys are saying (in a lot of videos actually), haha. Maybe that's why it's quiet for some people - all the noise is in the bass :)
Just tested. To hear what they are saying:
TommyEdison video: speakers 14%
This video: speakers 31%
The video doesn't seem to be quiet to me but some of the ads can be really loud
+Numberphile thanks for taking it as constructive. thanks for taking a look at it. I really love the content.
4:58 1 goes to 2 on the cover?
they used the shortened version for that tree. So... not 3n + 1 but (3n + 1)/2
3:23
Simplified 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
And this is, why I love mathematics :)
I've seen some comments here, proposing 0 as a solution to the problem. Though, 0 is a whole number, the definition of Collatz Conjecture calls for positive integers, thus we can't use 0 as an example of a number that doesn't fall to 1, because 0 is neither positive or negative integer.
When our computers will have enough memory, we might be able to get into a loop, that also starts and ends between two powers of 2.
It's potentially an infinite problem, so memory isn't really the issue. It's finding an efficient enough way to program it that you get a reliable answer in a reasonable amount of time...
L'homme Baguette im getting P vs NP vibes...
What if I take the record holder for the most amount of steps to get to 1, and multiply it by 2? Boom, new record holder!
Then it exceeds the upper bound. 62 million × 2 is 124 million, which is more than 100 million.
Then for being twice as big it only has 1 extra step
@1729 math_blog what if you get an even number by that?
@1729 math_blog and what if it’s a fraction?
python source code:
def comes_down_to_one(x):
print(f'input: {x}')
steps_count = 0
while x != 1:
if x % 2 == 0:
x = x / 2
else:
x = 3 * x + 1
print(x)
steps_count += 1
print(f"steps_count: {steps_count}")
Hi, I want to offer a seemingly simple answer, though probably not new/right:
1. Any even number you continuously Divide by two will reach one.
2. What we need to show is that the division action is more dominant than the multiplication.
3. You can see that after every ‘up’ there is a ‘down’, but after a ‘down’ you can have either an ‘up’ or another ‘down’. Statistically this gives you 3 ‘up’s for every 5 ‘downs’.
4. Now, let’s say that the probability was 1 ‘up’ for 2 ‘downs’, in that case it would be easy to see why the division action is dominant. Since what you get from two successive division (/4) is more powerful than what you get from one multiplication (*3).
5. Now you can ask yourself what should the probability be in order for the actions to cancel each other out? Let’s assume extremely high numbers, so the +1 factor can be ignored. The answer is that the division (/2) should be one and a half times more probable than the multiplication (*3), in other words that for every 3 multiplications there should be 4.5 divisions.
6. Since we now that the probability exceeds that, then we can say that when reaching very high numbers the ‘down’ action will surely be more prominent.
7. Since we can see that what goes up will surely come down, but, what comes down will not surely come up, since it can get trapped in the 1-4 loop, then given enough time you will always get stuck in the loop.
8. Problem solved!
surely the easiest thing to do is to find another loop that doesn't include 1?
+Alice Roberts find that loop and you will disprove the conjecture and become very math famous!
Is it also possible for some number to just get bigger and bigger as it follows the steps? (3n+1)/2>n so if the steps keep alternating, that would also be infinite. Or has it been proven that such a sequence is impossible?
+Dracarmen Winterspring its impossible, there are some numbers that get very high but they all eventually come back to 1. I think it's simply a matter of inevitability. You are dividing numbers by 2 when they are even and forcing them to be even when they're odd. eventually if you keep cutting a number in half and forcing it to be even it will have to inevitably reduce to 1.
+Dracarmen Winterspring The 3 possibilities would be:
1st: hitting 1
2nd: going towards Infinity
3rd: going into a circle that hits your starting number.
That would answer the question, yes. But no one has ever found one. Nor have they proved it doesn't exist.
dis anyone notice the fibonacci sequence on the 7's tree?
(quantities of numbers going down)
1
1
2
3
5
then the sequence ends
This is interesting and all, but I can't for the life of me figure out why it matters.
Solving it will provide a method that may be usable to solve other problems. Solution may tell us something profound about numbers that we didn't know. Math is basically nothing but the logical consequence of the concept of units. Matematicians aren't inventors, they are explorers, exploring these consequences. What to do with it is irrelevant. Fun fact: Electricity was discovered centuries before we knew what to do with it.
Why not try a proof by modified induction?
E.g. Since we know the first 100 million numbers go to 1, the first 100 million even numbers go to 1 as well. This process (please correct if not do) can be extended to infinitum so all even numbers fall to 1. But then since all odd numbers are transform immediately by the function to an even number, all odd numbers must then also go to 1.
can't you answer this by contradiction, assume that there is a number that runs away to infinity,
This number must be the smallest such number capable of running off to infinity
This number must not have a factor of 2 and No number less than n may lead to it
no number less than n therefore may lead to 2n, 2n must be 3a+3 or 3a-1 rather than 3a+1 for a an odd integer.
a=1
3a-1 = 2
3a+3 = 6
a=3
3a-1 = 8
3a+3 = 12
a=k
3k-1
3k+3
a=k+2
3(k+2)-1=(3k-1)+6
3(k+2)+3=(3k+3)+6
all relevant even numbers covered by these choices
(3a+3)/2 = n
substitute into 3n+1
3(3a+3)/2+1 = 9a+9/2 +1 = 9a+5+1/2
9a+5+1/2 should be a whole number (and even but not divisible by 4) and 3a+3 should be a whole number (and even but not divisible by 4)
if 9a+5+1/2 is a whole number then some whole number k must exist that 9a = k+1/2
Substitute 9a = k +1/2 into 3a+3
9a/3+3 = (k +1/2)/3 +3 = k/3+1/6+3 since k is a whole number any k will leave this expression with a fraction of 1/6, or 1/2 out from the whole number that should be 3a+3, this is a contradiction
(3a-1)/2=n
substitute into 3n+1
3(3a-1)/2+1 = 9a-3/2 +1 = 9a-1/2
9a-1/2 should be a whole number (and even but not divisible by 4) and 3a-1 should be a whole number (and even but not divisible by 4)
if 9a-1/2 is a whole number then some whole number k must exist that 9a = k+1/2
Substitute 9a = k +1/2 into 3a-1
9a/3-1 = (k +1/2)/3-1 = k/3+1/6-1 since k is a whole number any k will leave this expression with a fraction of 1/6, or 1/2 out from the whole number that should be 3a+3, this is a contradiction
so no integer can satisfy the equation 3a+3 or 3a-1 to give the number 2n and satisfy 3n+1 as a whole number
therefore there can be no n that is run away to infinity by following the odd n -> 3n+1 even n -> n/2
I think the logic is sound but I might be wrong.
Even assuming your math is right, that wouldn't prove the conjecture. It's possible that there is a set of numbers that form a loop other than 4->2->1, which wouldn't run to infinity, but would never reach 1. The only way to prove the conjecture is to prove all values of n lead to 1, and the only way to disprove it is to find a value of n that doesn't.
you made an error when subbing n into 3n+1... you didn't divide the 9 by 2
Some nice arguing.
You basically want to show that 3n+1 can not be a whole number if n is the smallest integer that does not eventually reach one. Obviously this can only be the case if already n is not a whole number. But you can't show that for n=(3a+3)/2. But suddenly you can if you substitute n in 3n+1. There is something smelling ;)
You made a small error: 9a+5+1/2 is not equal to 3(3a+3)/2. You forgot to divide 9a by 2. The same error for the second part.
damn and that'd allow it to have whole numbers too, well that was a waste of 20 minutes, still I think there's a proof by contradiction in there somewhere, as for a cycle above the 1, 4, 2, 1 cycle I think that if you do find the smallest number that doesn't reduce to 1 is a contradiction then that'd also be proved wrong. But I've already made a mistake here so who knows
It's never a waste of time to try and prove/disprove something (within reason, of course). Imagine if all the great mathematicians never tried? We wouldn't even have Numberphile videos, lol. Props to you for trying!