a computer does and without information you can't have an image so you can say you read the individual frames or the closed captioning or that the information that's talked about has sound involved which is another source of information read can mean to a storage medium ( aka the brain).
Trying to solve the Collatz conjecture simplifies to answering the question, "Can you get to 1 if we start from any odd number?", simply because that if we start with an even number, it will go to 1 if it is a power of 2, and it will go to an odd number otherwise. Furthermore, we know odd numbers are of the form m = 2n - 1 for all natural n. Hence 3(2n - 1) + 1 = 6n - 2 is always an even number, so we can divide by 2, obtaining 3n - 1 for all n. Then, every odd number of the form 2m - 1 = (2^p + 1)/3 is guaranteed to be go to 1 eventually since 3m - 1 = 2^p, and powers of 2 are guaranteed to go to 1. Thus, now we are interested in the question, "Starting from any odd number, can we always get to a number of the form 2(2^n + 1)/3 - 1 = 2^(n + 1)/3 + 2/3 - 1 = (2^(n + 1) - 1)/3 for some n?" An affirmative answer would prove the Collatz conjecture. Now, is this not beautiful?
1:27 he suggests getting a computer to solve the general case of: even n ---> n/2 Odd n ---> an + b. I can solve one class of cases: If a is odd and b is 0, the values diverge for almost all starting n. You’re welcome.
Well yeah, cuz an odd times 3 (another odd) will always be odd, so if your b term is 0, you just reach odd numbers and then zoom off to infinity. Edit 2 years later: I'm a fool in a man's shoes
That seems unlikely. Most people who won Erdos's prizes were professional mathematicians so were earning above the minimum wage pretty much by definition. Perhaps he said that if your only source of income was winning his prizes, you'd be working for less than the minimum wage? That seems much more plausible, since Erdos's prizes were typically somewhere between a few tens and a few hundred dollars, but most people would have to work for several hundred hours to win any of them.
I think you could find more about mathematics by taking the problem backwards rather than forwards. Instead of starting at a number and using the x/2 and 3x+1 rules, you could start at 1 and use a 2n and (n-1)/3 ruleset for all whole numbers. You then have a tree starting with n=1 which includes n=2 and eventually splits when the (n-1)/3 rule is available to use. Instead of checking every single number and then drawing a line to the original tree, you could create the tree from the ground up and know that you have gotten every single possible branch. This would take up as much processing power as the original way due to branches "annihilating" when they become a number that already exists in the line therefor meaning you no longer have to calculate that branch.
if you still want to keep the even/odd distinction, you have to use 2n when n is odd, and (n-1)/3 when it is even, otherwise you will immediately get zero from one which will cycle through 2n repeatedly. Even if you do this, though, you get the sequence of 1, 2, 1/3... you can already see the issue. It doesn't recreate any original branches. But let's assume you just stop when you get a fraction, and use the next whole number you haven't already produced. So, 3, for us. 3 is odd, so 2n is 6... which immediately becomes 5/3. We haven't got 4 yet, which... becomes 7/3. Not only is it not recreating the branches we've seen before, it falls apart very quickly. If we just try the other way around, 2n for even numbers and (n-1)/3 for odds, despite the fact that it falls apart with one, we can try 2. 2 becomes 4, which becomes 8... so the even numbers grow to infinity. 3 becomes 1, which becomes zero. 5 becomes 4/3, 7 becomes 2 which grows to infinity as we said before, 9 becomes 8/3... it's just not a useful way of recreating the tree. Perhaps there is a way, but not by inverting the steps of the original problem.
GelidGanef You kept using "can". It's supposed to be an algorithm, so we have to know when we must use a rule. Each step has to be forced. Say we use rule 1 whenever we can and rule 2 when rule 1 does not work. Starting with 1, the sequence will be 1, 2, 4, 1, repeat. That didn't get us very far. New rule: rule 1 applies to any integer at most once. The second time, we use rule 2. 1, 2, 4, 1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, ... That gets us all the integers of the form 3*2^n, which is something. But it is trivial that if the 3x+1 algorithm sends k to 1, then it will also send k*2^n to 1. What if we run the algorithm multiple times, ignoring the 1st chance to use rule 1 in the 1st run, the 1st and 2nd chances to use rule 1 in the 2nd run, etc. 1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, ...3*2^(n-8) ... 1, 2, 4, 8, 16, 32, 64, 21, 42, 84, ... 3*7*2(n-8) ... 1, 2, 7, 8, 16, 32, 64, 128, 256, 85, 170, 340, 113, 226, 75, 150, 300, ... 3 * 5^2 * 2^(n-15) Interesting, but I'm skipping over a lot of integers. One research question occurred to me when looking at the results above. If 3x+1 sends both x and y to 1, does it follow that x*y is also sent to 1? That is, can the result of run 2, that 3x+1 sends 3*7*2^k for k = 0, 1, ... be derived independetly from knowing that 3x+1 works for 3 and 7?
DrGerbils If you run the algorithm forwards, it is theorized to force all n integers down to 1, and typically through a path shorter than log(n) it seems, or something like that. So when you run it backwards, the path has to split. Your output should be a tree, where you move from 1, and branch out into different paths that eventually cover all integers. Here's an example. My rules would start with 1, which means you can generate 2,4,8,16, and 32. Out of these, only 4 and 16 qualify for the other rule. (4-1)/3 just yields 1 again, which is already on our list. (16-1)/3 yields 5 which is a new number. We can see that this is also a consistent result. 5 is odd, so it would've normally been "forced" to follow the 3n+1 rule, giving 16. 32 is even, so it would've also been "forced" to follow the other rule, also giving 16. So clearly, any algorithm that worked "backwards", but exhaustively gives all the same results as the forward algorithm, winds up looking like a tree, where splitting is sometimes possible. You wish to make your method an "algorithm" in the strictest sense, which is linear. Your method accomplishes this in an equivalent way. But it throws out the efficiency that OP was hoping for, where you only have to traverse each branch one time, so you can exhaustively traverse the tree in one go, without repeating calculations. Any real world implementation would require you to linearize in some way, but hopefully not be restarting the whole computation from 1. As for whether number lengths are related to their factors, no, I don't think so. That +1 part is the devil. From the perspective of n's factors, it makes the problem almost impossible to compute. If you could work out how the +1 affects every number in its factor-form, you wouldn't just have the solution to this problem, and a very general class of this problem too, you'd have a perfect prime number generator.
GelidGanef i see what you mean. Rule 2 generates the tree 1, 2, 4, 8, 16, 32, 64, ... Some nodes of that tree are 6k+4, so rule 1 can be applied. From 16, a new branch is created: 16, 5, 10, 20, 40, 80, ... From 10 another branch is created 10, 3, 6, 12, 24, 48 ... That branch does not branch further, but we can look at the 40 node on the branch rooted at 16, etc. You're right. That seems to generate the same tree you would get by running the 3x+1 algorithm on each successive integer. "As for whether number lengths are related to their factors, no, I don't think so. " I'm not sure where that came from, but I understand from the rest of the paragraph that you are skeptical about my conjecture that if 3x+1 works for x and y, then it works for xy.
It's interesting that the general an+b problem is undecidable, but I was wondering if there is some list of (a; b) pairs that are known to cycle, another list for those conjectured to go at 1 and another for those conjectured to go to infinity. That's something I've been looking for a while, though it's not too hard to generate them with some code.
Yes, there are some obvious pairs. If the parity is different it obviously approaches infinity, and if they're both even then you can reduce it - (6,2) is the same as (3,1). So it's sufficient to examine only two odds, but it's still interesting. Also, a further extension would be to replace the divison by 2 to division by c and examine "collatz triples" (a,b,c), which was my initial idea, but it might turn out that c>2 is not interesting. Anyway, I'm a decent programmer so I will code it up sometime and see for myself if there's some other interesting pair/triple.
I have proven the Collatz Conjecture to be false. But alas, the character limit of this comment section is too small to contain the proof and counter example.
@Gus Thomas Not necessarily true. To disprove Collatz you would have to show that such a number exists, but not necessarily find the value of the number.
The beauty of 3n+1 is that it ends with always the same cycle: [4 → 2 → 1]... meaning that it always reaches 4. 1 is just part of the cycle that brings back to 4. The conjecture should be: "blah blah always reaches 4" but this is less sexy than 1. And 3n-1 ends-up in cycles as well but those cycles vary depending on the starting number.
I would like to see more about backwards constructive approaches to this. Like, multiply by 2 and/or subtract one and divide by three (if possible) and from there on form the tree. And then analyse this. I think somewhere there lies the proof in some way like that you can prove that every integer can be constructed out of a sequence of these steps.
I think the availability of PCs gave people the idea that they could crank through the integers at high speed, and be the first to identify the counter-example that disproved the conjecture. We got some clever programming out of the effort, but it wasn't really aimed at *proving* the conjecture. Nobody's doing this today, since supercomputers have run the numbers vastly beyond what anybody can do with a personal rig. (I think it's been tested up to ~2^60.)
The "modified Collatz" C' (with these operations {3n-1; n/2}) is Collatz C mirrored at 0. ( C(k) = -C'(-k) for every k ) e.g. C'(5) -> {5, 14, 7, 20, 10, 5, ...} C(-5) -> {-5, -14, -7, -20, -10, -5, ...} So instead of asking "Why are there loops when I replace + by -?" you could ask "Why are there loops for n < 0?".
this is the simplest thing to solve, in that (N/2) if a is not a factor of 2 will become odd and therefore continue looping.but when you introduce (3n+1) essentially from simple math(odd number * odd number = odd,,but if you add 1, you make it even again and therefore (N/2) checks if its a factor of two again else it keeps going. The rule is that its only factors of two that lead you straight to one with the least steps
Okay I think I got this but I could be worng. This is just another "well-formed" numbering system. Treat every integer as a series of ups (3x+1) and downs (x/2). Downs will always move you more down than ups, and you will never find a loop (i.e. x/2=/=3x+1) All you done is essentially rename every number with a non-integer base. This is a binary function base.
I have a... kind of... stupidly sounding question, but give me the benefit of the doubt and believe I've spent months and maybe years thinking about it, and writing some programs trying to explore it... And try to answer from position of assuming this, thanks: What is it, that makes humans able to not infinite-loop themselves on evaluating the halting problem, but the computers and algorithms do? I mean, yes, you had video about that, but... fuzzy static evaluation? we had experiments with fuzzy AI (in games) back in 2000, where's experiments with fuzzy mathematics frameworks? which simulate the way people look at and estimate equations, etc?
Because a person will give up and get bored. If a person really wanted to solve the halting problem for any given Turing machine, they might have to simulate the TM for the longest finite time imaginable before saying the TM halts. There is no way to predict the outcome of every TM without running it. And if the program never halts? Then you could be stuck there until the end of time still calculating and never finish.
It's pretty obvious that this will go down to one. Because: A. Multiple by 3 and adding 1 is the same as multiple by 1.5, because that makes it even. So it goes down faster than it'll go up, 1.5 up vs 2 down. B. multiple by 1.5 and rounding up will make it divisible by four every second time, so for every up you'll have at least one down, and some times more than one down. So it's pretty obvious that it'll go down fast. We could improve it by giving a similar factor for up and down, and a similar chance for up or down. An example: a=6,b=5,m=23 point=x if x modulus 23 < (m-1)*(b/(a+b)) point / b else point * a I've started it with x = 526 for a few thousands iterations and it doesn't seem to have any direction. Up and down from zero to a billion without any order.
Premise A. is patently FALSE. 3n+1 is **not,** in any sense, the same as (1.5)*n or (3/2)*n What kind of wonky bad math are you doing?? For 1: 3n+1=4, (3/2)*n=(1.5)*n=1.5 4 =/= 1.5. For 3: 3n+1=10, (3/2)*n=(1.5)*n=4.5 10 =/= 4.5 for 5: 16 =/= 7.5 for 7: 22 =/= 10.5 for 9: 28 =/= 13.5 You are patently incorrect.
Even if you combined the two steps: 3n+1 (resulting in an even number) and then n/2 (because the result was even), it's still not the same number (off by 1/2 or 0.5): For 1: 2 =/= 1.5 For 3: 5 =/= 4.5 For 5: 8 =/= 7.5 For 7: 11 =/= 10.5 For 9: 14 =/= 13.5
Collatz have a connection to a Pillali Conjecture. Generally in 3x+b problem there is at most one cycle for selected b. We know this from 2^(x+y)-3^y=d problem (how many solutions are there, if we selected some d) and that problem is solved here: "On the generalized Pillai equation ±ax±by=c". Connetction between 2^(x+y)-3^y=d problem we can find here: "On the existence of cycles of given length in integer sequences like 𝑥_{𝑛+1}=𝑥_{𝑛}/2 if 𝑥_{𝑛} even, and 𝑥_{𝑛+1}=3𝑥_{𝑛}+1 otherwise" (I personally extended their proof for ax+b problem and it's easy to do). There is also connetction between Catalan's conjecture (or Mihăilescu's theorem) and Collatz problem. Since we knew that Catalan's conjecture is true we knew that there is no some special types of cycles in Collatz sequences (cause there are no more solutions of this problem: 2^(x+y)-3^y=1). Furthermore they are many more interesting connettions between Collataz Problem and some hard problems in math (for example Crandall Conjecture and Wieferich numbers - "On a conjecture of Crandall concerning the qx + 1 problem" or connection with a Mersenne Primes - "A Conjecture on the Collatz-Kakutani Path Length for the Mersenne Primes"). I have been analyzed this problem over the years and I love this.
People talk about arbitrary patterns, how about this/these ones: 1) Every number has one and only one thing it can become, but a number has either one or two ways to reach it (either half a number or (n-1)/3 of a number) 2) Every time you hit an even number, you eventually end up with a number whose prime factors exclude 2 - I know this is the definition of an odd number but if one could show you can get every prime combination by building the tree in reverse thats the problem (starting with one and building outward)
Think of the implication if there exists no classical logic mapping of naturals with collatz. That makes in interesting statement about nature. It may mean we will not have a unifying set of axioms, and will just have to assume or hope that different foundations map to each other.
Easy solve in 2atic space, every operation removes 1/4 of the area of the space. 0.75*0.75*0.75*0.75 etc converges at zero. Eventually all numbers will eventually land on a power of 2 and end.
When he says that the an+b version of the problem is undecidable, does he mean that it cannot be proven or disproven without extra axioms? (Like the continuum hypothesis?)
I think he means that, like the Halting problem, there's no single algorithm that allows us to determine whether the conjecture for an+b is true given any a and b - that is, for any algorithm we have, there's at least one pair (a, b) that the algorithm cannot give the correct answer to. Similarly, in the Halting problem, we can't find a single algorithm that tells us whether a machine will halt given its blueprints and its input.
I think the reason this problem has been so famous in because it is so simple yet unsolved. Most simple unsolvable problems have been proven to be impossible to solve, such as the 5+ color map, Fermat's last theorem, the utility problem, etc. The problem is so simple a 4th grader can understand it, yet nobody has found an exception nor proven there is not an exception.
Well, Fermat's Last Theorem _wasn't_ impossible to prove, since Andrew Wiles proved it. It's just that the only known proof requires some seriously high powered mathematical machinery.
That's what I was saying, it has been proven that there is no solution in whole numbers to x^n+y^n=z^n when n>2 it has also been proven that there is no minimal 5 color map and there is no 2 dimensional solution to the utility problem. But, though nobody has found a number that does not reduce to 4, 2, 1 nobody has proven that no such number exists either.
there's a relation for finding the higher number, 'N', that needs 'steps' number of operations: N = 2^^steps Ex: the biggest number that take 21 operations to reach 1 is 2097152 There are no bigger numbers than that with 21 steps. Every number bigger than 2097152 has steps bigger than 21
The collatz conjecture, only powers of two get to 1 and the conjecture's operators never get to 0. Therefore, only positive integers that are powers of 2 get to 1. So, there are positive integers that do not get to 1.
I always leave the extras unlisted for at least a few hours so the main video hits subscribers first... that way I hope people are less likely to click on the supplementary stuff before the main event.
+Numberphile2You could do a 'Numberphileπ' or something for extra footage, so that it is easy to access (I had to look for a couple of minutes to find the URL) and people know what they are getting into.
I have something advanced, "Collatz's conjecture is true if only if it is shown for the odd numbers of the form 12n-1 and the form 12n-5."; I can prove it. Also I have another little gem that is easy to demonstrate "If there were another loop other than 1-4-2-1 then there are infinite numbers that lead to this loop" (to date no number of these has been found if they existed are infinite).
Here is the solution. The method to be applied has only two rules: - 1. For odd numbers multiply it by 3 and add 1 2. For even numbers, we keep on dividing till we get an odd number (if it's not 1 we apply rule 1 again) Now, for all powers of 2, we keep applying rule 2 we will eventually get to 1, which is 2^0. (So it has to be true for all powers of 2). All numbers which are not powers of 2, are either odd or some even number which is the product of some power of 2 and an odd number (other than 1). Now, if it's an even number we keep applying rule 2, to get to that odd number (other than 1). So, in both cases we will hit an odd number other than 1. Now, all odd numbers can be written in the form 2x + 1, where x is any whole number. So, when we apply rule 1 to it, we are actually converting it to an even number of the form 6x + 4. (3 multiplied to an odd must give an odd number, since 3 is odd. 1 added to an odd number is even. Since the number we started with was having the form 2x + 1, the even number formed by applying rule 1 will have the form 6x + 4.) But, when we apply rule 2 to this even number, the algebra tells we will never get the earlier odd number back again. This is because 3x + 2 > 2x + 1(unless x is 0, in which case 2x + 1 would have been 1). Even if, 3x + 2 is an even number when we divide it by two all the numbers that we get will be less than 2x + 1. Which means we will get different odd numbers every time. All these odd numbers, will have the form 2x + 1, but the x must have a different value for each one of them. This in turn means, the even numbers that we will get by applying rule 1 will be a different number each time. This process will continue until we hit an even number which is a power of 2, which will take us back to 1. Therefore, all numbers on which the method is applied following the rules will eventually take us back to 1. Hence proved 🙂🙂🙂
I was playing around with the numbers and I did couple, small and big ones, and found something interesting... Every number above 10 follows almost the same sequence as the the first 10 numbers I call "base" numbers. What do I mean? I mean that an arbitrary number, say 1238, will follow a pattern, as it makes it's way down to one (we know this number reaches one at some point) that almost resembles the pattern of 8. But then the larger the number, I found that it is not only the pattern of the last digit that is Incorporated into this arbitrary number's pattern, but it is a combination of the first ten. For example, the number, as it makes it's way down to one, will have a sequence that resembles the pattern taken by 5, then a pattern taken by 8 and so on. So every number, from what I saw as I did this, will follow a pattern as it tries to get to one that is a combination of the first base numbers. It's like a collage. It was interesting for sure. I'm sure other mathematicians have noticed this too.
When N is even, there are two results in the next number: either it is even or it is odd. When N is odd, the next number is guaranteed to be even. When it is even, the number is reduced. When it is odd, the number is increased. So in two out of three instances, the number is reduced, and in the third instance, the number is guaranteed to be reduced in the next. The frequency of "reductions" (halving) is guaranteed to occur more often then increasing (multiplying by three, and adding one). But then again, making the odds follow 3n-1 also guarantees an even in the next. Here the number is being both increased and reduced. Does the pattern have something to do with the combination of increasing and decreasing? Who knows.
I think you may be off. If you're looking at three steps then here are the possibilities Even -> even, in which case, we get, n/4, so it decreases Even -> odd, in which case, we get 3(n/2) + 1, so it increases. Odd -> even, in which case, we get (3n+1)/2, so it increases So w.r.t. to the initial n, in two out of three cases, when you apply the rules twice, the number increases. I wonder what would happen if you look at three steps out, four etc.
You've got the insight. The "4-2-1" loop is the key. If you look at it in binary representations, the 'divide' (shift right) happens twice as often as the increase (odd value) operation... Play with 4, 5, and 6 bits and you'll see that the 3 LSBs will not 'support' higher values for long. Eventually, any bits higher than 0x01 and 0x02 dissolve away to the right... Nothing "up there" can sustain itself, so all bit patterns are fated to fade to that 4-2-1 loop eventually. (That "3rd rail" elevator to the basement (the powers of two line) awaits all who venture into the unknown...)
There is an astonishing amount of complexity bias surrounding this conjecture. The Collatz Conjecture is true because the Collatz Function is a bijection between {N} and {1,1,1,…}. It’s very simple.
Why is there no video on Numberphile about Aliquot sequences? They too form graphs similar to the ones obtained from Collatz conjecture, and there's a conjecture (made by Catalan) that any sequence ends in a cycle (a perfect number, an amicable pair, or cycle of social numbers) or in 1. Several numbers though still have an undetermined sequence (like 276).
Prof Charles Cadogan of the university of the west Indies, Cavehill campus, has proved the the Collatz conjecture. You should be able to obtain a cpy of the proof by contacting the department of mathematics at Cavehill , st. Michael , Barbados.
Just for fun, here is what I am thinking... If n=1, stop If n is even, divide by 2 If n is odd, multiply by 3 and then add 1 So far that's the rule.. We can prove that all even numbers will eventually end up as an odd number by dividing 2. We can prove that all odd numbers multiplied by 3 will be odd, therefore all 3n+1 must result in an even number. When an even number is divided by 2, there are only two possibilities: I. Divide by 2 again. II. Ends up in an odd number. As one even number only gets divided once by 2, the next even number must get divided by 2 more than once (4, 8,16, 32...) It seems to me that the smallest set of numbers ad dividers for even numbers follow the pattern of: 2, 4, 2, 8, 2, 4, 2, 16 and grows larger as n grows. The average of this divider is 5 so since n/5 will always be less than 3n+1 for all natural numbers, doesn't that mean these rules will make any n move toward 1, the smallest number allowed based on the rules?
For what it's worth, I think that the cash prizes offered for problems like this are really quite pointless as an incentive. For one thing, many studies have found that providing a cash prize for a problem requiring even rudimentary cognitive thought usually hinders people from a solution rather than encouraging them. Secondly, anyone capable of solving a problem like this isn't doing it for the money anyway. They're doing it because they are interested in mathematics and want to know what the answer is, for themselves and for the future of mathematics. Granted, these people who make these breakthroughs to find the answers are deserving of recognition and a fitting reward for their contribution, but we shouldn't act like dangling that reward in front of them like a carrot on a stick is going to get them there any faster. If anything, it will distract them.
So if the problem of whether such a machine can exist is undecidable, does that imply that for at least one ordered pair (a, b) it's impossible to prove whether or not the associated conjecture of whether every integer eventually reaches 1 via the sequential transformations is true? I think I've heard that some people believe the Collatz conjecture to be undecidable, but I could be thinking of the Goldbach conjecture.
I don't think so. I cannot explain why it isn't true for a set of pairs, but individually, in an infinite set of numbers, f(n) does go to a pre-defined result or not. For example, with Fermat's Last Theorem, if this was undecidable, there were be obviously no triples in the theorem's parameters (else you could work it out), therefore, it would have been proven correct.
This is rather subtle. The following problem is undecidable: given a and b, does the generalized Collatz conjecture hold for that pair (a,b)? What this means is that there is no algorithm that will allow you to compute for all (a,b), whether Collatz(a,b) is true. In other words, if you think you have a method that works for all (a,b), the method must be flawed. However, what it doesn't rule out is the possibility that one method works for some values of (a,b), and another method works for some other values and so on. Indeed, it's possible that, for every pair (a,b), there's some method that will correctly tell you whether Collatz(a,b) is true. But, in that case, there's no method that tells you which method to use for each case (since that, combined with the methods for the cases, would give you a method for all (a,b)). For example, a method that can tell you very quickly that a pair (a,b) doesn't take every number to 1 is to ask if there is any odd number x>1 such that (ax+b)/2=x. If there is such an x, then the sequence for x goes x, (ax+b), x, (ax+b), ... and never reaches 1. But, because of the undecidability result, there must be values of a and b for which (ax+b)!=x for all odd x but yet there is still some y such that the sequence from y doesn't reach 1.
+beeble2003 ahh okay, I did a little more research after I made my comment so I knew that no single algorithm existed but I wasn't sure of the bit after that, thanks for the clarification :)
Yes, Perelman solved the Poincare conjecture, but refused the million dollar Clay Millennium prize. The money was instead used to support a mathematics department in a university in France I believe. The Clay institute ultimately decided to donate the money though, not Perelman. For the record, Perelman considered the prize amount to be 'unfair' and downplayed his own contribution saying it wasn't worth a million dollars. It just goes to show you the mentality of a world class mathematician.
Interesting… I never realized that the generalized problem was undecidable That’s kind of insane, if you think about it… Even if we can prove the original conjecture, there will always be combinations of A/B that we will never be able to solve one way or the other I mean, given the existence of Gödel’s Incompleteness Theorems, I suppose these sorts of situations are inevitable… But even so, there’s something about the an + b situation that makes it seem like it should always be solvable, in theory
seems like all u need to prove is that every multiple of 3 plus 1 will eventually wind up on an even number after x number of iterations, and perhaps x is somewhat proportional to the log of the number or something.
Umm no... Every iteration of "3n+1" leads to an "even" number. One would have to prove that all integers eventually random walk (via some combination of "3n+1" and/or "n/2") to a "power of 2" (not just an "even" number), which then collapses to 1 via n/2 transformations. ONLY powers of 2 directly collapse to 1. Other even numbers eventually collapse to an odd number, and then hit the "3n+1" function and go back up again (though, given the result is even, it will then go back down via n/2, until it either collapses to an odd number and goes back up again, or is a power of 2, and collapses directly down to 1).
Lo tengo algo avanzada," La conjetura de Collatz es verdad si solo si se demuestra para los números impares de la forma 12n-1 y de la forma 12n-5."; lo puedo demostrar. Ademas tengo otra joyita fácil de demostrar " Si existiese otro bucle distinto al 1-4-2-1 entonces existen infinitos números que llevan a este bucle" ( a la fecha no se ha encontrado ningún numero de estos si existiesen son infinitos).
What if you plot the result of "(n mod a = 0)? then (n / (a+1)), else (an+b)" repeatedly. The colour (shade) at each point being the smallest starting natural number (for "n") greater than 1 that returns to 1? The whole thing kinda reminds me on the Mandelbrot set now.
The secret to the Collatz conjecture is that you are adding halfs not integers. The Collatz conjecture is simple a geometric series where 1/2+1/4+1/8...=1.
So, if a*n+b is in general undecidable then it would seem that this could imply that there does exist some choice of the pair (a,b) so that the particular example using those values is undecidable. If this is the case then the pair (3,1) may well be the smallest (in some sense) pair that is undecidable.
Here are some exceptions to the Collatz conjecture that I found: -5, -7, -9, -10, -13, -14, -17, -18, -19, -20, -21... I assume there are infinitely many.
Still conjecturing on the binary approach ....11111 + 1 = 100000 (a power of 2). Any x * 3 that leads to some pow(n, 2) - 1 (a binary number with all 1's) will resolve. Backing up one step, any even number that is not a power of 2 will always fall to an odd number. So it remains only to prove odd numbers, and in fact, only odd multiples of 3, that they will inevitably lead to a string of 1's. Can we prove that this is true for all (x
Considering the even case, where we divide by 2, in binary x/2 == x>>1 (a shift to the right). The low digit will always be "0" for even numbers. Only even numbers that have their 2 ^ 1 place filled will become odd. All others become even. It's clear how powers of 2 can shift to the right all the way down to 1 (10000->1000->100->10->1), whereas all others will be halted when the other "1" reaches the least-significant digit (11000->1100->110->11). So a further optimization is to treat all numbers with "0" in their low digits as if they were already shifted right to their odd low factor. That is, always some odd number raised to some power of 2.
Clearly I need to read more about all the avenues already explored. To me it does intuitively seem that it probably always resolves, just because there are always more reductions on average than increases. But making a formal proof is a whole other thing!
You have it too ? DO you know who or how you would release it ? Not especially competing it's a simple solution and the prize like you say is not huge. For me it would be about getting 'in' so to speak, to discuss other problems. Be cool if you messaged back. Thanks
So, for "3n-1," it looks like it definitely loops if it hits 7 or any of its looping numbers (7, 20, 10, 5, 4, 7) or 17 or any of its looping numbers (17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, 17). Just running some equations through LibreOffice/Excel. Picked up on two distinct "loops" for numbers up through 15000. Most of the rest trended to 1... Not sure if it loops for any other (higher) number sets, or not? Seemed like all the loops I was seeing through 15,000 were of the 7 or 17 loop variety.
Idea: look into obscure properties of even and odd numbers? Probably won’t work. This is one of those problems that seems like it should be simple and easy but isn’t
3x+3 is ... well... weird. Despite 3x+3 having a relatively simple looking 12-6-3 loop, 6 connects to its own plethora of numbers, unlike 2 from 3x+1. It's certainty interesting, however.
So, you're ensuring that the number will always be a multiple of 3? 3n+3 will ALWAYS be a multiple of 3. You're starting at a multiple of 3 (that is to say, 3n) and then adding 3 to it. Quite literally, you're simply doing 3*(n+1). So, if your input was 7, you're just doing 3*8. What has this to tell us about Collatz? :P I'd say ... not much.
I can only find a number which is equal to the number of operations he takes to reach 1. That number is 5. 5-16-8-4-2-1 Is there any other number such Col(n) = n ; Col(n) represents the number of steps that n take to reach 1)?
GPC™ as far as I know, there is none. I just checked every number up to 100 and n =/=Coll(n) for all cases except 5. 91 came very close as it takes 92 steps to reach 1.
Any number ends in 1, but also in 16 for all the numbers above 16 ? This number 16 can be related to time squared (4^2) right? All iterations are related to the number 4 in math, right? It's the circumference factor of the radius of a cardioid ':)
So, what is the maximum number of steps record? How many steps for PI (decimal expansion)? Allow me: 141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006 took 1316 steps to reach 1
Its been a while since I have actually practiced any kind of college level mathematics but I was wondering if this problem might have any connection to attractive fixed points? The reason I ask is because I feel like there are some similarities.
U tried 3x-1. That ennded up making a loop similiar to 3x+1.But here it 7,20,20,5,14,7,20.... and for 3x+1 it was 4,2,1.Hence both of them made loops but different ones. I tried other numbers for 3x-1 as well (for odd ones and then x÷2). They also ended up making the same loops i.e 7,20,5,... Therefore 3x+1 might not be a special case. 5x+1 also makes a loop but a real big one.therefore we might also ask why does 3x-1 also reach that loop
One thing we know for certain, if there is a solution where n doesn't reduce to 1 then there is both an odd and even numbered solutions and therefore there would be an infinite number of solutions.
"One thing we know for certain, if there is a solution where n doesn't reduce to 1 then there is both an odd and even numbered solutions" How do we know this?
At least Collatz didn't write down that he had a "magnificent solution" and then died. No one can be as great a troll as Fermat.
Fermat may well have had a solution. There is no proof there there isn't an elementary solution.
hgfuhgvg yet It is very unlikely that he had
Lol only 10% of math experts can understand this *OMG not clickbait*
Unlikely
it's very likely he had a case proof..
this dude has the most soothing voice
yea man, like if u high and watch this, it'll take you to another world literally
Like Bob Ross
try keith from objectivity
I'm sure this man reading game of thrones would be the most confusing experience you'll ever have.
It makes me want to go to that field he mentioned
3:54 he turns into Bob Ross
A nice lake with happy little trees.
That is just the most cool professor! Love his voice!
Very soothing. I would fall asleep within 5 minutes when I attended his college, I think.
Of course Brady thinks we should climb the mountain. That's Brady 101.
That's because he's not going to climb it himself. You're not going to climb it either, so "we" in your statement is kinda cheeky.
As a long time reader of computerphile i certainly know about the halting problem.
a computer does and without information you can't have an image so you can say you read the individual frames or the closed captioning or that the information that's talked about has sound involved which is another source of information read can mean to a storage medium ( aka the brain).
at 1:37 he say "your READERS ..." that's why I read videos
@@htmlguy88 you cant read by your ears only by your eyes also the brain isn't a computer storage it's a piece of meat thats made for us to move
It is always nice to start the day with a numberphile video and learn about a new undecidable problem.
I'm pretty sure the primary Collatz problem will be found to be decidable, and will eventually be proven true.
this man is my absolute favourite on any channel. he oozes intellect yet retains symmetrical humility.
Trying to solve the Collatz conjecture simplifies to answering the question, "Can you get to 1 if we start from any odd number?", simply because that if we start with an even number, it will go to 1 if it is a power of 2, and it will go to an odd number otherwise. Furthermore, we know odd numbers are of the form m = 2n - 1 for all natural n. Hence 3(2n - 1) + 1 = 6n - 2 is always an even number, so we can divide by 2, obtaining 3n - 1 for all n. Then, every odd number of the form 2m - 1 = (2^p + 1)/3 is guaranteed to be go to 1 eventually since 3m - 1 = 2^p, and powers of 2 are guaranteed to go to 1. Thus, now we are interested in the question, "Starting from any odd number, can we always get to a number of the form 2(2^n + 1)/3 - 1 = 2^(n + 1)/3 + 2/3 - 1 = (2^(n + 1) - 1)/3 for some n?" An affirmative answer would prove the Collatz conjecture. Now, is this not beautiful?
1:27 he suggests getting a computer to solve the general case of:
even n ---> n/2
Odd n ---> an + b.
I can solve one class of cases:
If a is odd and b is 0, the values diverge for almost all starting n.
You’re welcome.
Well yeah, cuz an odd times 3 (another odd) will always be odd, so if your b term is 0, you just reach odd numbers and then zoom off to infinity.
Edit 2 years later: I'm a fool in a man's shoes
@@drakep271 r/woooosh lol
@@drakep271 John smith was joking make, he wasn’t being serious. The “you’re welcome” was meant to be sarcastic.
Actually it diverges for all starting n, because even if n is a power of 2, it will reach 1 and then increase in powers of a.
too bad we cant get ol' Gauss on this...
5:40 I think it was Erdos who said that to receive the mathematical prizes he set, you would have to work below minimum wage.
That seems unlikely. Most people who won Erdos's prizes were professional mathematicians so were earning above the minimum wage pretty much by definition. Perhaps he said that if your only source of income was winning his prizes, you'd be working for less than the minimum wage? That seems much more plausible, since Erdos's prizes were typically somewhere between a few tens and a few hundred dollars, but most people would have to work for several hundred hours to win any of them.
depends on if he meant before tax or after or where he meant because $500 for me here would take over 60 hours of minimum wage to net after taxes.
Yes, that's what I imagine he meant.
I'm pretty sure it was a figurative exaggeration guys
This is so simple yet so hard, interest levels are going up with the passage of time!
I think you could find more about mathematics by taking the problem backwards rather than forwards.
Instead of starting at a number and using the x/2 and 3x+1 rules, you could start at 1 and use a 2n and (n-1)/3 ruleset for all whole numbers.
You then have a tree starting with n=1 which includes n=2 and eventually splits when the (n-1)/3 rule is available to use.
Instead of checking every single number and then drawing a line to the original tree, you could create the tree from the ground up and know that you have gotten every single possible branch.
This would take up as much processing power as the original way due to branches "annihilating" when they become a number that already exists in the line therefor meaning you no longer have to calculate that branch.
When would you use each rule?
if you still want to keep the even/odd distinction, you have to use 2n when n is odd, and (n-1)/3 when it is even, otherwise you will immediately get zero from one which will cycle through 2n repeatedly.
Even if you do this, though, you get the sequence of 1, 2, 1/3... you can already see the issue. It doesn't recreate any original branches.
But let's assume you just stop when you get a fraction, and use the next whole number you haven't already produced. So, 3, for us. 3 is odd, so 2n is 6... which immediately becomes 5/3. We haven't got 4 yet, which... becomes 7/3. Not only is it not recreating the branches we've seen before, it falls apart very quickly.
If we just try the other way around, 2n for even numbers and (n-1)/3 for odds, despite the fact that it falls apart with one, we can try 2. 2 becomes 4, which becomes 8... so the even numbers grow to infinity. 3 becomes 1, which becomes zero. 5 becomes 4/3, 7 becomes 2 which grows to infinity as we said before, 9 becomes 8/3... it's just not a useful way of recreating the tree. Perhaps there is a way, but not by inverting the steps of the original problem.
GelidGanef You kept using "can". It's supposed to be an algorithm, so we have to know when we must use a rule. Each step has to be forced.
Say we use rule 1 whenever we can and rule 2 when rule 1 does not work.
Starting with 1, the sequence will be 1, 2, 4, 1, repeat. That didn't get us very far.
New rule: rule 1 applies to any integer at most once. The second time, we use rule 2.
1, 2, 4, 1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, ...
That gets us all the integers of the form 3*2^n, which is something. But it is trivial that if the 3x+1 algorithm sends k to 1, then it will also send k*2^n to 1.
What if we run the algorithm multiple times, ignoring the 1st chance to use rule 1 in the 1st run, the 1st and 2nd chances to use rule 1 in the 2nd run, etc.
1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, ...3*2^(n-8) ...
1, 2, 4, 8, 16, 32, 64, 21, 42, 84, ... 3*7*2(n-8) ...
1, 2, 7, 8, 16, 32, 64, 128, 256, 85, 170, 340, 113, 226, 75, 150, 300, ... 3 * 5^2 * 2^(n-15)
Interesting, but I'm skipping over a lot of integers.
One research question occurred to me when looking at the results above. If 3x+1 sends both x and y to 1, does it follow that x*y is also sent to 1? That is, can the result of run 2, that 3x+1 sends 3*7*2^k for k = 0, 1, ... be derived independetly from knowing that 3x+1 works for 3 and 7?
DrGerbils If you run the algorithm forwards, it is theorized to force all n integers down to 1, and typically through a path shorter than log(n) it seems, or something like that.
So when you run it backwards, the path has to split. Your output should be a tree, where you move from 1, and branch out into different paths that eventually cover all integers.
Here's an example. My rules would start with 1, which means you can generate 2,4,8,16, and 32. Out of these, only 4 and 16 qualify for the other rule. (4-1)/3 just yields 1 again, which is already on our list. (16-1)/3 yields 5 which is a new number. We can see that this is also a consistent result. 5 is odd, so it would've normally been "forced" to follow the 3n+1 rule, giving 16. 32 is even, so it would've also been "forced" to follow the other rule, also giving 16.
So clearly, any algorithm that worked "backwards", but exhaustively gives all the same results as the forward algorithm, winds up looking like a tree, where splitting is sometimes possible. You wish to make your method an "algorithm" in the strictest sense, which is linear. Your method accomplishes this in an equivalent way. But it throws out the efficiency that OP was hoping for, where you only have to traverse each branch one time, so you can exhaustively traverse the tree in one go, without repeating calculations. Any real world implementation would require you to linearize in some way, but hopefully not be restarting the whole computation from 1.
As for whether number lengths are related to their factors, no, I don't think so. That +1 part is the devil. From the perspective of n's factors, it makes the problem almost impossible to compute. If you could work out how the +1 affects every number in its factor-form, you wouldn't just have the solution to this problem, and a very general class of this problem too, you'd have a perfect prime number generator.
GelidGanef i see what you mean. Rule 2 generates the tree 1, 2, 4, 8, 16, 32, 64, ...
Some nodes of that tree are 6k+4, so rule 1 can be applied. From 16, a new branch is created: 16, 5, 10, 20, 40, 80, ...
From 10 another branch is created 10, 3, 6, 12, 24, 48 ... That branch does not branch further, but we can look at the 40 node on the branch rooted at 16, etc.
You're right. That seems to generate the same tree you would get by running the 3x+1 algorithm on each successive integer.
"As for whether number lengths are related to their factors, no, I don't think so. "
I'm not sure where that came from, but I understand from the rest of the paragraph that you are skeptical about my conjecture that if 3x+1 works for x and y, then it works for xy.
3:55 close your eyes - Bob Ross is alive.
It's interesting that the general an+b problem is undecidable, but I was wondering if there is some list of (a; b) pairs that are known to cycle, another list for those conjectured to go at 1 and another for those conjectured to go to infinity. That's something I've been looking for a while, though it's not too hard to generate them with some code.
then plot them as black and white dots and get a picture of...
Well, I'm pretty sure any positive values of a and b where one of them is odd and the other is even, will approach infinity.
Yes, there are some obvious pairs. If the parity is different it obviously approaches infinity, and if they're both even then you can reduce it - (6,2) is the same as (3,1). So it's sufficient to examine only two odds, but it's still interesting. Also, a further extension would be to replace the divison by 2 to division by c and examine "collatz triples" (a,b,c), which was my initial idea, but it might turn out that c>2 is not interesting.
Anyway, I'm a decent programmer so I will code it up sometime and see for myself if there's some other interesting pair/triple.
I've given it a brief try and quite a lot of a/b pairs have small numbers go big very fast. That in itself doesn't mean anything of course.
Yes, that is why I haven't written the code yet - too lazy to code big integers (C++ user here), since most pairs blow up quickly.
I have proven the Collatz Conjecture to be false. But alas, the character limit of this comment section is too small to contain the proof and counter example.
Post it on a blog or something and link it here
Ah, Fermat
If you have proven it you should be able to provide a single number that does not go to 1
@Gus Thomas Not necessarily true. To disprove Collatz you would have to show that such a number exists, but not necessarily find the value of the number.
What if you do 1.5....... it will never get to one.
The content on this channel is so great, thanks for all these videos!
Thanks, really cool and insightful part 2. Really appreciate numphile2.
This guy's like the Bob Ross of mathematics
The beauty of 3n+1 is that it ends with always the same cycle: [4 → 2 → 1]... meaning that it always reaches 4. 1 is just part of the cycle that brings back to 4.
The conjecture should be: "blah blah always reaches 4" but this is less sexy than 1.
And 3n-1 ends-up in cycles as well but those cycles vary depending on the starting number.
not only that, but they all end in
40
20
10
5
16
8
4
2
1
@@raresaturn Well no, it does not necessarily have to go through 40, 20, 10, and 5. Just a power of 2
I would like to see more about backwards constructive approaches to this. Like, multiply by 2 and/or subtract one and divide by three (if possible) and from there on form the tree. And then analyse this. I think somewhere there lies the proof in some way like that you can prove that every integer can be constructed out of a sequence of these steps.
Pah, formulas are for wimps! Hard graft is whats needed, so I'm going through ALL the numbers.
Up to 19 so far....wish me luck :P
Any luck buddy?
Engineers
*" Don't Judge a b̶o̶o̶k̶ problem by its c̶o̶v̶e̶r̶ statement "*
*- Collatz Conjecture*
Last night after the main video I tried 5n+1 by amending a python script and got some amazing chaotic behaviour.
gsurfer04 what kind of behaviour? do you know any sites or programs i can use to test it? my professor left 5n+1 as an exercise and im curious
@@maki6203 No one is doing your exercise for you, lol.
I think the availability of PCs gave people the idea that they could crank through the integers at high speed, and be the first to identify the counter-example that disproved the conjecture. We got some clever programming out of the effort, but it wasn't really aimed at *proving* the conjecture. Nobody's doing this today, since supercomputers have run the numbers vastly beyond what anybody can do with a personal rig. (I think it's been tested up to ~2^60.)
Love his style of teaching.
The "modified Collatz" C' (with these operations {3n-1; n/2}) is Collatz C mirrored at 0. ( C(k) = -C'(-k) for every k )
e.g.
C'(5) -> {5, 14, 7, 20, 10, 5, ...}
C(-5) -> {-5, -14, -7, -20, -10, -5, ...}
So instead of asking "Why are there loops when I replace + by -?" you could ask "Why are there loops for n < 0?".
this is the simplest thing to solve, in that (N/2) if a is not a factor of 2 will become odd and therefore continue looping.but when you introduce (3n+1) essentially from simple math(odd number * odd number = odd,,but if you add 1, you make it even again and therefore (N/2) checks if its a factor of two again else it keeps going.
The rule is that its only factors of two that lead you straight to one with the least steps
Okay I think I got this but I could be worng.
This is just another "well-formed" numbering system. Treat every integer as a series of ups (3x+1) and downs (x/2). Downs will always move you more down than ups, and you will never find a loop (i.e. x/2=/=3x+1) All you done is essentially rename every number with a non-integer base. This is a binary function base.
What there is a 2nd channel?!? Nice!
Welcome to the Internet's attic.
there's also computerphile, sixty symbols etc.
I have a... kind of... stupidly sounding question, but give me the benefit of the doubt and believe I've spent months and maybe years thinking about it, and writing some programs trying to explore it...
And try to answer from position of assuming this, thanks:
What is it, that makes humans able to not infinite-loop themselves on evaluating the halting problem, but the computers and algorithms do?
I mean, yes, you had video about that, but... fuzzy static evaluation? we had experiments with fuzzy AI (in games) back in 2000, where's experiments with fuzzy mathematics frameworks? which simulate the way people look at and estimate equations, etc?
Because a person will give up and get bored. If a person really wanted to solve the halting problem for any given Turing machine, they might have to simulate the TM for the longest finite time imaginable before saying the TM halts. There is no way to predict the outcome of every TM without running it. And if the program never halts? Then you could be stuck there until the end of time still calculating and never finish.
It's pretty obvious that this will go down to one.
Because:
A. Multiple by 3 and adding 1 is the same as multiple by 1.5, because that makes it even. So it goes down faster than it'll go up, 1.5 up vs 2 down.
B. multiple by 1.5 and rounding up will make it divisible by four every second time, so for every up you'll have at least one down, and some times more than one down.
So it's pretty obvious that it'll go down fast.
We could improve it by giving a similar factor for up and down, and a similar chance for up or down.
An example:
a=6,b=5,m=23
point=x
if x modulus 23 < (m-1)*(b/(a+b))
point / b
else
point * a
I've started it with x = 526 for a few thousands iterations and it doesn't seem to have any direction. Up and down from zero to a billion without any order.
Premise A. is patently FALSE.
3n+1 is **not,** in any sense, the same as (1.5)*n or (3/2)*n
What kind of wonky bad math are you doing??
For 1: 3n+1=4, (3/2)*n=(1.5)*n=1.5
4 =/= 1.5.
For 3: 3n+1=10, (3/2)*n=(1.5)*n=4.5
10 =/= 4.5
for 5: 16 =/= 7.5
for 7: 22 =/= 10.5
for 9: 28 =/= 13.5
You are patently incorrect.
Even if you combined the two steps: 3n+1 (resulting in an even number) and then n/2 (because the result was even), it's still not the same number (off by 1/2 or 0.5):
For 1: 2 =/= 1.5
For 3: 5 =/= 4.5
For 5: 8 =/= 7.5
For 7: 11 =/= 10.5
For 9: 14 =/= 13.5
Collatz have a connection to a Pillali Conjecture. Generally in 3x+b problem there is at most one cycle for selected b. We know this from 2^(x+y)-3^y=d problem (how many solutions are there, if we selected some d) and that problem is solved here: "On the generalized Pillai equation ±ax±by=c". Connetction between 2^(x+y)-3^y=d problem we can find here: "On the existence of cycles of given length in integer sequences like 𝑥_{𝑛+1}=𝑥_{𝑛}/2 if 𝑥_{𝑛} even, and 𝑥_{𝑛+1}=3𝑥_{𝑛}+1 otherwise" (I personally extended their proof for ax+b problem and it's easy to do). There is also connetction between Catalan's conjecture (or Mihăilescu's theorem) and Collatz problem. Since we knew that Catalan's conjecture is true we knew that there is no some special types of cycles in Collatz sequences (cause there are no more solutions of this problem: 2^(x+y)-3^y=1). Furthermore they are many more interesting connettions between Collataz Problem and some hard problems in math (for example Crandall Conjecture and Wieferich numbers - "On a conjecture of Crandall concerning the qx + 1 problem" or connection with a Mersenne Primes - "A Conjecture on the Collatz-Kakutani Path Length for the Mersenne Primes"). I have been analyzed this problem over the years and I love this.
People talk about arbitrary patterns, how about this/these ones:
1) Every number has one and only one thing it can become, but a number has either one or two ways to reach it (either half a number or (n-1)/3 of a number)
2) Every time you hit an even number, you eventually end up with a number whose prime factors exclude 2 - I know this is the definition of an odd number but if one could show you can get every prime combination by building the tree in reverse thats the problem (starting with one and building outward)
Think of the implication if there exists no classical logic mapping of naturals with collatz. That makes in interesting statement about nature. It may mean we will not have a unifying set of axioms, and will just have to assume or hope that different foundations map to each other.
Maybe. I think the Collatz Conjecture is mostly exponents and powers of 2.
Easy solve in 2atic space, every operation removes 1/4 of the area of the space. 0.75*0.75*0.75*0.75 etc converges at zero. Eventually all numbers will eventually land on a power of 2 and end.
When he says that the an+b version of the problem is undecidable, does he mean that it cannot be proven or disproven without extra axioms? (Like the continuum hypothesis?)
I think he means that, like the Halting problem, there's no single algorithm that allows us to determine whether the conjecture for an+b is true given any a and b - that is, for any algorithm we have, there's at least one pair (a, b) that the algorithm cannot give the correct answer to. Similarly, in the Halting problem, we can't find a single algorithm that tells us whether a machine will halt given its blueprints and its input.
Yes, it means exactly that.
3n -1 is only the symetrics of what happens in negatives numbers on 3n+1 problem
I think you are wrong. I found another solution 6.
The thing is: you never know whether a problem like this can discover a field of mathematics that will easily help to solve million $ problems
I think the reason this problem has been so famous in because it is so simple yet unsolved. Most simple unsolvable problems have been proven to be impossible to solve, such as the 5+ color map, Fermat's last theorem, the utility problem, etc.
The problem is so simple a 4th grader can understand it, yet nobody has found an exception nor proven there is not an exception.
Well, Fermat's Last Theorem _wasn't_ impossible to prove, since Andrew Wiles proved it. It's just that the only known proof requires some seriously high powered mathematical machinery.
That's what I was saying, it has been proven that there is no solution in whole numbers to x^n+y^n=z^n when n>2 it has also been proven that there is no minimal 5 color map and there is no 2 dimensional solution to the utility problem. But, though nobody has found a number that does not reduce to 4, 2, 1 nobody has proven that no such number exists either.
Ah, I see what you're saying. Sorry about the misunderstanding.
The video began with the part I was interested in (potential intractability).
there's a relation for finding the higher number, 'N', that needs 'steps' number of operations:
N = 2^^steps
Ex: the biggest number that take 21 operations to reach 1 is 2097152
There are no bigger numbers than that with 21 steps.
Every number bigger than 2097152 has
steps bigger than 21
Math is really fun and this just proves why!!!!!!!!!
The collatz conjecture, only powers of two get to 1 and
the conjecture's operators never get to 0. Therefore,
only positive integers that are powers of 2 get to 1. So,
there are positive integers that do not get to 1.
Fun fact: the cover of Lagaria's book has an (most probably intential) error: 133 does not give 170
The 3n+1 three is build of streath lines like the powers of 2 and staircases like how 7 goes around
this video is unlisted
Soon it won't be
I always leave the extras unlisted for at least a few hours so the main video hits subscribers first... that way I hope people are less likely to click on the supplementary stuff before the main event.
exactly.
+Numberphile2You could do a 'Numberphileπ' or something for extra footage, so that it is easy to access (I had to look for a couple of minutes to find the URL) and people know what they are getting into.
That makes more sense than it should...
Please upload a video about this if something happens!
It would be nice to have a video on the halting problem, I'm not aware that Brady has done one on that.
check out computerphile ( a brady channel at last check) they have one's about it.
I have something advanced, "Collatz's conjecture is true if only if it is shown for the odd numbers of the form 12n-1 and the form 12n-5."; I can prove it. Also I have another little gem that is easy to demonstrate "If there were another loop other than 1-4-2-1 then there are infinite numbers that lead to this loop" (to date no number of these has been found if they existed are infinite).
Here is the solution.
The method to be applied has only two rules: -
1. For odd numbers multiply it by 3 and add 1
2. For even numbers, we keep on dividing till we get an odd number (if it's not 1 we apply rule 1 again)
Now, for all powers of 2, we keep applying rule 2 we will eventually get to 1, which is 2^0.
(So it has to be true for all powers of 2).
All numbers which are not powers of 2, are either odd or some even number which is the product of some power of 2 and an odd number (other than 1). Now, if it's an even number we keep applying rule 2, to get to that odd number (other than 1). So, in both cases we will hit an odd number other than 1.
Now, all odd numbers can be written in the form 2x + 1, where x is any whole number. So, when we apply rule 1 to it, we are actually converting it to an even number of the form 6x + 4. (3 multiplied to an odd must give an odd number, since 3 is odd. 1 added to an odd number is even. Since the number we started with was having the form 2x + 1, the even number formed by applying rule 1 will have the form 6x + 4.)
But, when we apply rule 2 to this even number, the algebra tells we will never get the earlier odd number back again. This is because 3x + 2 > 2x + 1(unless x is 0, in which case 2x + 1 would have been 1). Even if, 3x + 2 is an even number when we divide it by two all the numbers that we get will be less than 2x + 1. Which means we will get different odd numbers every time. All these odd numbers, will have the form 2x + 1, but the x must have a different value for each one of them.
This in turn means, the even numbers that we will get by applying rule 1 will be a different number each time. This process will continue until we hit an even number which is a power of 2, which will take us back to 1.
Therefore, all numbers on which the method is applied following the rules will eventually take us back to 1.
Hence proved 🙂🙂🙂
Two problems: forward it can come back to the first number, second it can go to infinite.
I was playing around with the numbers and I did couple, small and big ones, and found something interesting... Every number above 10 follows almost the same sequence as the the first 10 numbers I call "base" numbers. What do I mean? I mean that an arbitrary number, say 1238, will follow a pattern, as it makes it's way down to one (we know this number reaches one at some point) that almost resembles the pattern of 8. But then the larger the number, I found that it is not only the pattern of the last digit that is Incorporated into this arbitrary number's pattern, but it is a combination of the first ten. For example, the number, as it makes it's way down to one, will have a sequence that resembles the pattern taken by 5, then a pattern taken by 8 and so on. So every number, from what I saw as I did this, will follow a pattern as it tries to get to one that is a combination of the first base numbers. It's like a collage. It was interesting for sure. I'm sure other mathematicians have noticed this too.
The greater conjecture is that one can always find a portable hole or singularity using the collatz ( even | odd ) snakes and ladders algorithm.
Anyone else notice the (seemingly) unrelated stuff on the board?
Here's a nice function that gives the next number (y) from x :)
y = (1/4)*(2+(7*x)-(2+5*x)*cos(pi*x))
You can simplify :
Un+1=(2Un+.5 + (Un+0.5)(-1)^Un)/2
When N is even, there are two results in the next number: either it is even or it is odd.
When N is odd, the next number is guaranteed to be even.
When it is even, the number is reduced. When it is odd, the number is increased.
So in two out of three instances, the number is reduced, and in the third instance, the number is guaranteed to be reduced in the next.
The frequency of "reductions" (halving) is guaranteed to occur more often then increasing (multiplying by three, and adding one).
But then again, making the odds follow 3n-1 also guarantees an even in the next. Here the number is being both increased and reduced. Does the pattern have something to do with the combination of increasing and decreasing? Who knows.
Ah but when they are increased they increase by a factor of 3 and so at some stages grow faster by than they decline
I think you may be off.
If you're looking at three steps then here are the possibilities
Even -> even, in which case, we get, n/4, so it decreases
Even -> odd, in which case, we get 3(n/2) + 1, so it increases.
Odd -> even, in which case, we get (3n+1)/2, so it increases
So w.r.t. to the initial n, in two out of three cases, when you apply the rules twice, the number increases.
I wonder what would happen if you look at three steps out, four etc.
You've got the insight. The "4-2-1" loop is the key. If you look at it in binary representations, the 'divide' (shift right) happens twice as often as the increase (odd value) operation... Play with 4, 5, and 6 bits and you'll see that the 3 LSBs will not 'support' higher values for long. Eventually, any bits higher than 0x01 and 0x02 dissolve away to the right... Nothing "up there" can sustain itself, so all bit patterns are fated to fade to that 4-2-1 loop eventually.
(That "3rd rail" elevator to the basement (the powers of two line) awaits all who venture into the unknown...)
the answer lies in the quantum of odd and even numbers in the string. And the tree can be based on prime numbers.
There is an astonishing amount of complexity bias surrounding this conjecture.
The Collatz Conjecture is true because the Collatz Function is a bijection between {N} and {1,1,1,…}. It’s very simple.
2²-3=1, 2-3=-1, 3²-2³=1, 2⁴-3²=7, 2^6-3⁴=-17 etc.
What is the general pattern you are alluding to?
What makes something provable? Aren't lot's of things that we can't verify every input for?
Why is there no video on Numberphile about Aliquot sequences? They too form graphs similar to the ones obtained from Collatz conjecture, and there's a conjecture (made by Catalan) that any sequence ends in a cycle (a perfect number, an amicable pair, or cycle of social numbers) or in 1. Several numbers though still have an undetermined sequence (like 276).
Prof Charles Cadogan of the university of the west Indies, Cavehill campus, has proved the the Collatz conjecture. You should be able to obtain a cpy of the proof by contacting the department of mathematics at Cavehill , st. Michael , Barbados.
Just for fun, here is what I am thinking...
If n=1, stop
If n is even, divide by 2
If n is odd, multiply by 3 and then add 1
So far that's the rule..
We can prove that all even numbers will eventually end up as an odd number by dividing 2.
We can prove that all odd numbers multiplied by 3 will be odd, therefore all 3n+1 must result in an even number.
When an even number is divided by 2, there are only two possibilities: I. Divide by 2 again. II. Ends up in an odd number.
As one even number only gets divided once by 2, the next even number must get divided by 2 more than once (4, 8,16, 32...)
It seems to me that the smallest set of numbers ad dividers for even numbers follow the pattern of: 2, 4, 2, 8, 2, 4, 2, 16 and grows larger as n grows.
The average of this divider is 5 so since n/5 will always be less than 3n+1 for all natural numbers, doesn't that mean these rules will make any n move toward 1, the smallest number allowed based on the rules?
This is another unintentional asmr video
a little fact would also be if n = a power of 2.. then it will inevitably go down to 1
For what it's worth, I think that the cash prizes offered for problems like this are really quite pointless as an incentive.
For one thing, many studies have found that providing a cash prize for a problem requiring even rudimentary cognitive thought usually hinders people from a solution rather than encouraging them.
Secondly, anyone capable of solving a problem like this isn't doing it for the money anyway. They're doing it because they are interested in mathematics and want to know what the answer is, for themselves and for the future of mathematics.
Granted, these people who make these breakthroughs to find the answers are deserving of recognition and a fitting reward for their contribution, but we shouldn't act like dangling that reward in front of them like a carrot on a stick is going to get them there any faster. If anything, it will distract them.
Do we know that solving this would be of benefit?
So if the problem of whether such a machine can exist is undecidable, does that imply that for at least one ordered pair (a, b) it's impossible to prove whether or not the associated conjecture of whether every integer eventually reaches 1 via the sequential transformations is true? I think I've heard that some people believe the Collatz conjecture to be undecidable, but I could be thinking of the Goldbach conjecture.
I don't think so. I cannot explain why it isn't true for a set of pairs, but individually, in an infinite set of numbers, f(n) does go to a pre-defined result or not. For example, with Fermat's Last Theorem, if this was undecidable, there were be obviously no triples in the theorem's parameters (else you could work it out), therefore, it would have been proven correct.
This is rather subtle. The following problem is undecidable: given a and b, does the generalized Collatz conjecture hold for that pair (a,b)?
What this means is that there is no algorithm that will allow you to compute for all (a,b), whether Collatz(a,b) is true. In other words, if you think you have a method that works for all (a,b), the method must be flawed. However, what it doesn't rule out is the possibility that one method works for some values of (a,b), and another method works for some other values and so on. Indeed, it's possible that, for every pair (a,b), there's some method that will correctly tell you whether Collatz(a,b) is true. But, in that case, there's no method that tells you which method to use for each case (since that, combined with the methods for the cases, would give you a method for all (a,b)).
For example, a method that can tell you very quickly that a pair (a,b) doesn't take every number to 1 is to ask if there is any odd number x>1 such that (ax+b)/2=x. If there is such an x, then the sequence for x goes x, (ax+b), x, (ax+b), ... and never reaches 1. But, because of the undecidability result, there must be values of a and b for which (ax+b)!=x for all odd x but yet there is still some y such that the sequence from y doesn't reach 1.
+beeble2003 ahh okay, I did a little more research after I made my comment so I knew that no single algorithm existed but I wasn't sure of the bit after that, thanks for the clarification :)
One guy crack on the million pound problems but didn't take the money. Madness, give it to a school or hospital or university.
+ZERO Or to another mathematician (like Erdos did).
ZER0 can u repeat that in english please
ZER0 He did this, kind of, by refusing. By that he "donated" 1 million to the CMI.
Yes, Perelman solved the Poincare conjecture, but refused the million dollar Clay Millennium prize. The money was instead used to support a mathematics department in a university in France I believe. The Clay institute ultimately decided to donate the money though, not Perelman.
For the record, Perelman considered the prize amount to be 'unfair' and downplayed his own contribution saying it wasn't worth a million dollars. It just goes to show you the mentality of a world class mathematician.
It's their money.
Which pen you use please tell me
Could we have an update with Terry Tao's almost all collatz get to almost bounded values discovery?
I wonder if anyone has made a serious attempt to analyze this through Matiyasevich's theorem?
EDIT: Apparently Matiyasevich. Of course.
Wait, what is that?
@@alexandertownsend3291 Every algorithm can be represented as a Diophantine equation that has a solution iff the algorithm halts.
If its domain is taken to be the integers, the range will be the integers modulo 2.
Interesting… I never realized that the generalized problem was undecidable
That’s kind of insane, if you think about it… Even if we can prove the original conjecture, there will always be combinations of A/B that we will never be able to solve one way or the other
I mean, given the existence of Gödel’s Incompleteness Theorems, I suppose these sorts of situations are inevitable… But even so, there’s something about the an + b situation that makes it seem like it should always be solvable, in theory
seems like all u need to prove is that every multiple of 3 plus 1 will eventually wind up on an even number after x number of iterations, and perhaps x is somewhat proportional to the log of the number or something.
Umm no... Every iteration of "3n+1" leads to an "even" number.
One would have to prove that all integers eventually random walk (via some combination of "3n+1" and/or "n/2") to a "power of 2" (not just an "even" number), which then collapses to 1 via n/2 transformations. ONLY powers of 2 directly collapse to 1. Other even numbers eventually collapse to an odd number, and then hit the "3n+1" function and go back up again (though, given the result is even, it will then go back down via n/2, until it either collapses to an odd number and goes back up again, or is a power of 2, and collapses directly down to 1).
Lo tengo algo avanzada," La conjetura de Collatz es verdad si solo si se demuestra para los números impares de la forma 12n-1 y de la forma 12n-5."; lo puedo demostrar. Ademas tengo otra joyita fácil de demostrar " Si existiese otro bucle distinto al 1-4-2-1 entonces existen infinitos números que llevan a este bucle" ( a la fecha no se ha encontrado ningún numero de estos si existiesen son infinitos).
Try 17 in 3n-1. Applying 3n+1 for +ive values = 3n-1 for -ive values, with opp. Sign
What if you plot the result of "(n mod a = 0)? then (n / (a+1)), else (an+b)" repeatedly. The colour (shade) at each point being the smallest starting natural number (for "n") greater than 1 that returns to 1?
The whole thing kinda reminds me on the Mandelbrot set now.
The secret to the Collatz conjecture is that you are adding halfs not integers. The Collatz conjecture is simple a geometric series where 1/2+1/4+1/8...=1.
So, if a*n+b is in general undecidable then it would seem that this could imply that there does exist some choice of the pair (a,b) so that the particular example using those values is undecidable.
If this is the case then the pair (3,1) may well be the smallest (in some sense) pair that is undecidable.
Here are some exceptions to the Collatz conjecture that I found: -5, -7, -9, -10, -13, -14, -17, -18, -19, -20, -21... I assume there are infinitely many.
“positive integer”
Instead of working brute force from 1 to 2^60, is there a definition of infinity regarding its even/odd-ness?
What is this wholething-problem is talking of, at 1:35. Or did't I get this right?
He is a bit difficult to understand for a foreign listener, sorry.
strike997 Its called the Halting Problem, i was looking in the comments as well
its whether a computer can determine if a series terminates or not
Still conjecturing on the binary approach ....11111 + 1 = 100000 (a power of 2). Any x * 3 that leads to some pow(n, 2) - 1 (a binary number with all 1's) will resolve. Backing up one step, any even number that is not a power of 2 will always fall to an odd number. So it remains only to prove odd numbers, and in fact, only odd multiples of 3, that they will inevitably lead to a string of 1's. Can we prove that this is true for all (x
Considering the even case, where we divide by 2, in binary x/2 == x>>1 (a shift to the right). The low digit will always be "0" for even numbers. Only even numbers that have their 2 ^ 1 place filled will become odd. All others become even. It's clear how powers of 2 can shift to the right all the way down to 1 (10000->1000->100->10->1), whereas all others will be halted when the other "1" reaches the least-significant digit (11000->1100->110->11). So a further optimization is to treat all numbers with "0" in their low digits as if they were already shifted right to their odd low factor. That is, always some odd number raised to some power of 2.
Clearly I need to read more about all the avenues already explored. To me it does intuitively seem that it probably always resolves, just because there are always more reductions on average than increases. But making a formal proof is a whole other thing!
I really like this guy
I was absent when my HS math class went into all this.
I have the solution but... 500 dollars? Not enough bro.
*holds up wads of cash*
Maybe if I... triple it and add a dollar?
You have it too ? DO you know who or how you would release it ? Not especially competing it's a simple solution and the prize like you say is not huge. For me it would be about getting 'in' so to speak, to discuss other problems. Be cool if you messaged back. Thanks
?
Kris Church, I think we need to have a talk about "jokes"
Lol.... lots of scope on that comment ... by all means converse
So, for "3n-1," it looks like it definitely loops if it hits 7 or any of its looping numbers (7, 20, 10, 5, 4, 7) or 17 or any of its looping numbers (17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, 17).
Just running some equations through LibreOffice/Excel. Picked up on two distinct "loops" for numbers up through 15000. Most of the rest trended to 1...
Not sure if it loops for any other (higher) number sets, or not? Seemed like all the loops I was seeing through 15,000 were of the 7 or 17 loop variety.
Idea: look into obscure properties of even and odd numbers?
Probably won’t work. This is one of those problems that seems like it should be simple and easy but isn’t
I just figured this out but there is n/2 for even and 3n+3 for uneven numbers and you always get 12 - 6 - 3 sequence at the end after x steps
3x+3 is ... well... weird. Despite 3x+3 having a relatively simple looking 12-6-3 loop, 6 connects to its own plethora of numbers, unlike 2 from 3x+1. It's certainty interesting, however.
So, you're ensuring that the number will always be a multiple of 3? 3n+3 will ALWAYS be a multiple of 3. You're starting at a multiple of 3 (that is to say, 3n) and then adding 3 to it. Quite literally, you're simply doing 3*(n+1). So, if your input was 7, you're just doing 3*8.
What has this to tell us about Collatz? :P I'd say ... not much.
I can only find a number which is equal to the number of operations he takes to reach 1. That number is 5.
5-16-8-4-2-1
Is there any other number such Col(n) = n ; Col(n) represents the number of steps that n take to reach 1)?
GPC™ as far as I know, there is none. I just checked every number up to 100 and n =/=Coll(n) for all cases except 5. 91 came very close as it takes 92 steps to reach 1.
If so I think you will find just 1 per distance away from the powers of 2.
this man is just so likeable
Any number ends in 1, but also in 16 for all the numbers above 16 ? This number 16 can be related to time squared (4^2) right? All iterations are related to the number 4 in math, right? It's the circumference factor of the radius of a cardioid ':)
So, what is the maximum number of steps record?
How many steps for PI (decimal expansion)?
Allow me:
141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006 took 1316 steps to reach 1
1 000 000! (which is 5 565 709 digits long) reaches 1 after 127 487 285 iterations. That's the longest series I tried.
Its been a while since I have actually practiced any kind of college level mathematics but I was wondering if this problem might have any connection to attractive fixed points? The reason I ask is because I feel like there are some similarities.
1:30 the what problem from computer science?
The Halting Problem.
halting problem
Pleasant man
still holding the division rule at 'if n%2 = 0 then n
U tried 3x-1. That ennded up making a loop similiar to 3x+1.But here it 7,20,20,5,14,7,20.... and for 3x+1 it was 4,2,1.Hence both of them made loops but different ones. I tried other numbers for 3x-1 as well (for odd ones and then x÷2). They also ended up making the same loops i.e 7,20,5,... Therefore 3x+1 might not be a special case. 5x+1 also makes a loop but a real big one.therefore we might also ask why does 3x-1 also reach that loop
3x+1 for negative numbers also produces multiple loops that are surprisingly small i believe
One thing we know for certain, if there is a solution where n doesn't reduce to 1 then there is both an odd and even numbered solutions and therefore there would be an infinite number of solutions.
And secondly, I would predict if there were a solution, it would not end in a loop but would continue to increase.
"One thing we know for certain, if there is a solution where n doesn't reduce to 1 then there is both an odd and even numbered solutions"
How do we know this?
@@MuffinsAPlenty Say N doesn't reduce. Then 2^a*N for all natural numbers a reduce to N, which doesn't reduce to 1.