Rewrite the sequence steps as follows: - Dvivide n by 2^k for k=0,1,.. where k is the largest number for which the result is still an intege. That will be an odd number - Multiply n by 3 and add 1 In binary the procedure is even simpler: - Remove all trailing 0's. - Shift left 1 and add the orgininal number and add 1. Now remark that the number of times we divide by 2 (or the number of trailing 0's we remove) is (except for the first iteration in which it is 50%) 1 in 100% of cases, 2 in 50% of cases, 3 in 25% of cases, etc. The weighted average is: 1 + 1/2 + 1/4 + 1/8 + ... = 2. So on average each step (as defined above) will yield a result of multiplication by 3 and division by 4, which is 3/4 and smaller then 1. That is why we can see that in (almost all) cases, the sequence must come down. However, for the 5n+1 sequence, we multiply by 5 and divide by 4 which is 5/4 which is larger then 1. So that sequence should diverge to infinity in almost all cases.
You might disagree with Mr Feinstein, but honestly you *have* to admit that his arguments are *always* interesting. And you must read *all* his papers to fairly and properly judge his assertions. He has much more than just brief YT videos. ... Though he should be publishing more and more!
What part of it is it that they are trying to prove? Is it the equation for the number of times a number will bounce around before it goes down to the loop? Is it whether or not all numbers used will go down to the loop?
You have presented no proof that every polynomial time algorithm deciding subset sum requires that there exists a polynomial number of expressions on both sides. Merely claimed it. Your statement at 3:11 is merely stated and not proven.
Suppose you cannot reduce the subset sum equation to an equation with only a polynomial number of expressions on each side. Then you are stuck with an equation with a super polynomial number of possible expressions on at least one of the sides. Then deciding whether such an equation is true for some possible expressions on each side must take a super polynomial amount of time, since in the worst case scenario one cannot do any better than examining all of the expressions, which must take a super polynomial amount of time. QED
@@cafeinst Once again, you have presented no proof that there must exist a polynomial number of expressions on both sides primarily because you have not established that the algorithm must examine all of the possibilities on both sides. Also you are obviously wrong since there are algorithms which are better than pure brute force 2^n for SS. Namely O(2^(n/2)) birthday algorithm of H-S, S-S, 74 and 81 resp. then O(1.22^n) randomized Alg from 2011 which also ultimately reduces to the birthday algorithm. “In the worst case scenario, one cannot do any better than examining all of the expressions”. Proof?
@@cafeinst Moreover, consider a version of SUBSET SUM with XORing. I can represent this problem as a subset sum type of problem. A problem (encoding of a set of strings) is in the language XORSUBSETSUM if and only if there exists a subset of strings which bitwise XOR to a particular string m; let us represent this as <a_1,...,a_n,m>. For this problem, there exists exponentially many expressions by the same argument you made. By the same argument there is no simpler expression. However, this reduces to XORSAT, which by Schafer’s Dichotomy Theorem has a polynomial time algorithm, namely, Gaussian elimination of a system of linear equations over Z|2 which is O(n^5). Thus, your criterion does not imply that there does not exist any polynomial time algorithm. Π
@@John-lf3xf my paper on arxiv.org entitled “Dialogue concerning the two chief world views” addresses your comment about subset sum with xor, as far as I am understanding it. Also my claim is that there is no deterministic and exact algorithm which solves subset sum in o(2^{n/2}) time. My claim has never been contradicted. If it has, then I would admit I am wrong. The famous 2011 algorithm is irrelevant for the purposes of a P /= NP proof, since it is randomized. It also does not decide subset sum. I talk about this in my paper. As for your asking proof for “in the worst case scenario, one cannot do any better than examining all of the expressions”, it is simple - If you have an equation with a super polynomial number of possible values on at least one of the sides and you want to know whether there is a value on the left side equal to a value on the right side and you cannot mathematically reduce the equation to anything simpler, it would be magic if you could solve it in the worst case scenario in polynomial time. Since magical algorithms do not exist, you need super polynomial time.
@@cafeinst We do not even need to discuss the algorithms existent (and I also do not see how you would even adjust this argument to account for the randomized cases, but this is clearly wrong so I will not bother). Independently of that, you have then essentially stated that your paper, the so called “Dialogue concerning the two chief world views” contradicts your own argument as to the need to reduce your expression to something simpler. Since in fact for XOR SubsetSum, we can bound the string size by an arbitrary polynomial and can obtain exponentially in n (superpolynomially) many strings as a result of XOR summing. Hence this contradicts that there can exist no polynomial time algorithm since it is solvable by Gaussian elimination over Z mod 2. (Notice that the ability to produce exponentially in n many strings on a side of the equation is closely related to Shannon’s Perfect Secrecy Theorem.) It is not my job to determine your intellectual honesty, whether you would admit if you were wrong, (and it is clear that you are just by what I have showed above). “Magic” is not mathematically well-defined and something which is not well-defined obviously cannot exist as something well-defined. But if you were to define “magical algorithm” in a well-defined way, you would still have to prove and not simply state that such a thing could not exist. (It is not a surprise that Professor Sipser says he receives proofs where at some point it is said that “obviously this takes exponential time”.) Your argument has been ended thus far. You should stop pulling this forward unless you obtain something new. Π
If f is equal to 0 then the problem is trivial (xi = 0) and cleary is in P. But your proof doesn't use variability of f at all, which means it still has to be not in P.
I didn’t explicitly mention the variability of t in order to make my conclusion that P is not NP, but as you pointed out it is necessary for the proof to work. So I am implicitly assuming that t is not zero.
To prove Collatz it needs three conditions: Don't go to infinite; don't has cycles and it must converge to one. See this proof on ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-O00DSbTwJhc.html.
Well, even if using 5n+1 would go to infinite for some numbers - what you would have to prove first - it does not prove anything for 3n+1. While 2(a)n+1 goes to infinite for example - for obvious reasons - 1n+1 goes to 1 instead - for obvious reasons, too. You explain, why you *think* it goes to infinity, but deliver *no prove* at all.
That something is improbable for you or you cannot prove it is not enough to assume that it is unlikely for everyone. That was Paul Erdös' big mistake in 1982. He assumed that if he couldn't, no one would do it and that is pride and believing himself more than all other people. In conclusion a big mistake.
ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-b8VJVvIWeMo.html follow me on my channel, I will present the demonstration of the collatz conjecture that was raised in 1937 and no one has yet been able to prove it. There I present a complete work on how to understand how all numbers go down to 1 explaining in great detail what happens and without using only samples. With my explanation you can understand how the numbers behave regardless of their number of digits and it is very easy to understand, both for mathematicians and for those who are not. I invite you to see my work. regards
Please do not waste your life trying to prove me wrong. Read my paper in the video description, try to understand it. Read Conway's 2013 paper on this subject. Erdos did not say math wasn't ready for these types of problems for no reason.
I proved very cool things in it like there is no any cycles except 1.2.4 and there are infinite number of odds can reach any number How i can stop now i am working like from 2 years in this and now stop
My theory is saying that all number have infinite numbers of odds if i know how pattern is this, i can prove that all number can came from the number 1 and then all number go to the 1 I hope i can or any one can!
I only want to prove that (3^x - 1)/(2^x - 1)=(a hole number) Have only one answer for x and it is (1) And i know that when x even it will never be hole but odds i dont know if you can help me in this you will help me so much!
I beg to disagree. I firmly do believe that it will eventually been proven; just because we have not yet observed a counter example within a couple trillion iterations does not speak anything of its likeliness. That is an inconceivably small fraction of the infinite numbers that exist. So, we have only solved a couple trillion over infinity. This fraction is relatively close to zero, meaning we have not proved anything. Not even probabilistically. Here is a non-mathematical counter to your theory. If in a couple trillion numbers we find a point where all sequences diverge, then there would be infinitely more solutions to this problem then there would be counters. For all we know, it very well could have an inflection point trillions of zeros away
@@cafeinst sigueme en mi canal para que veas la demostración de esta conjetura. Te adelanto esto: es más facil de lo que te imaginas. Los matemáticos han caido en divagaciones, mitos y utopías imaginativas sobre la conjetura que los han distraido por años. Pero la explicaré en palabras sencillas para que no quede ninguna duda a ningun ser humano, es decir, todos van a entender dicha conjetura. sigueme en mi canal y lo veras. saludos.
The mistake is (referring to your latest version of the proof on archive org) in the sentence “there is nothing that can be done to make this equation simpler”. You can have a more complicated expression that can (Maybe? You never know...) be solved in polynomial time. As a true mathematician I stopped reading after the first false statement ;)
cafeinst there can be infinitely many expressions that are equivalent to yours. The fact that you “simplified” yours and calculated that it does not give a polynomial time does not mean that there is no some other expression (which may have a different form and be more “complicated”) that may lead to an algorithm with a polynomial time. One can have exactly the same logic as you do (which will be wrong of course) to prove that testing for primality can not be done in polynomial time, yet it can. Besides, your expression can be made “simpler” at least for some trivial cases - s are even and t is odd for example. How do you prove there are no such shortcuts for each and any t and s?
"Dialogue concerning the chief world views" is in the description for the video. If you agree with it, then great. If not, then I will probably never convince you.
@@zholud to address your comment, while it is true that there are infinitely many equations equivalent to the equation in my paper, all of these equations still have an exponential number of possible values on at least one of the sides, implying that there can be no poly time algorithm solving subset sum.
A similar construction can be done for some instances of the 2SATn problem which has a polynomial time solution. For suitable instances of the 2SAT problem we can divide the problem into a conjunction of 2 parts which I will name as 2SATk and 2SAT(n-k). While the solution space of the main problem(SATn) has 2^n canditates, the first part(2SATk) has 2^k and the second part (2SAT(n-k)) has 2^(n-k) candidates. And surprise. The k value which minimizes the partitioned problem's number of total candidate solutions gives the number sqrt(2^n) again as the minimum number of solutions for the partitioned problem. So, according to the author's deduction style, these instances of the 2SATn problem have no polynomial time solution. But we know that all instances of the 2SATn problem have a polynomial time solution because the general 2SAT problem has a polynomial time algorithm.
I essentially address your argument in the paper that I linked to entitled "Dialogue concerning the two chief world views" when the members of the set are bounded by a polynomial.
To be brief, you are misunderstanding my argument. It is not really because there are 2^{n/2} possible expressions on both sides of the equation that makes the argument work. It is the fact that there are instances of the subset sum problem which have the order of 2^{n/2} possible values on each side of the equation which makes any algorithm which solves it have super poly time. With respect to 2SAT, there are only 2 possible values 0 and 1, which makes your argument fail.
jajaja. De acuerdo contigo hay personas que se rinden y quieren que los demas hagan lo mismo. esta conjetura es demostrable eso lo presentaré en mi canal.
Please take this down - it is complete and utter nonsense and will have a negative impact on people trying to learn about Collatz. I'm not trolling you, this is genuinely very, very bad.
Rob, on the contrary. I am trying to warn people not to try to prove this conjecture. Lots of people have already wasted lots of time on this conjecture, with nothing to show for it. Proving this conjecture is the modern version of angle trisection.
Here's my take on it, and I haven't really seen it approached from this angle. I don't think it should EVER diverge to infinity, as long as it's in the format an + 1 where a is odd. At some point it is bound to land on a power of 2. That is literally all that's needed to that it will divide and divide until you get down to 1. So it might be something insanely large like 2^500000, but it would appear that probability dictates that at some point a power of 2 must be reached. So in my mind there is not really the need to show that it doesn't diverge to infinity but rather to show that a) the numbers generated in the sequence are random or at least that every real number can be a value in the sequence for some starting number (which would guarantee via probability that it must reach a power of 2), and b) that there are no closed loops that just spit out the same string of numbers over and over again.
lo que dices sobre potencias de 2 siempre no es del todo cierto ahora que sea un multiplo de una de esas potencias es la segunda opción. En mi canal presento la demostración de la conjetura de collatz. pensar en complicar el problema pensando en ciclos infinitos es un mito por el hecho de que impar conduce a par y hay mas posibilidades de dividir que de multiplicar. igual es pensar en problemas 5x+1, 7x+1 y px+1. primero se debe resolver collatz sin evadir el tema. eso ha distraido el trabajo eficiente en relación a la demostración. saludos
It is provable Is this serious ? I’m not a math genius but you don’t need to be one to solve this shit. It’s clear that it will always end with the 421 because of the 1 you add, do the same thing with n*3+3 and you will always get a 3 at the end, I say that without trying but it’s so safe like me living. It’s obvious that every odd number multiplied by 3 makes an odd number too, then you add a 1 to make it even but because you have only 1 time to do the n*3+1 in a row, you will always end up to divide by 2 more times, isn’t that obvious? Now I know why I hate mathematicians. They are all idiots trying to use every number to solve this problem and a dumb ass like me solves this in 2 minutes
Uhh... Probability can prove things. For example: Imagine an algorithm r where you start with a value being 1. There is a 2^n chance that it will stop there, but otherwise it will keep growing, adding one and doing it again. Once it stops, that is the output. The function will ALWAYS terminate because there is ALWAYS SOME chance that it will. For the Collatz sequence, it will always go down because for an odd number and the sequence is OEO where O is odd and E is even, the number is multiplied by 1.5. That isn't 2, but there is a 50% chance that it will actually be OEE. Then there is a 25% chance of EEE. There is NO chance that OOE exists, or OOO, because in this sequence two odd numbers cannot exist together. The number is always decreasing.
Katakana! This is untrue, probability will tell you that it is almost guaranteed to terminate, but there will always be a situation where it’s possible that it can go on infinitely. Much like in this conjecture, where we only need one value to disprove , they’re only needs to be a single situation in your case where the program doesn’t terminate, then nothing is guaranteed
As is you understand it, do not do mistake what our ancestors did. Give researchers benefit of doubt if you do not clearly understand the problem and stop just blindly refusing ideas. He might be wrong, but let these people think.
Prove it wrong and you can say that a number may diverge to the infinite. Changing values that aren't variables in an expression changes the outcome for an equation
Seriously? Thats the reason you think its unprovable? You know mathematicians could have thought Fermats last theorem is unprovable and gave up on it but they didnt and you can see after almost 350 years it was proven so its better not to discourage young mathematicians instead of encouraging them to prove the conjecture.
Vivek Veer, I see myself as doing a public service discouraging anyone from even attempting to prove the conjecture. Proving the Collatz conjecture is like trisecting an angle with only a straightedge and compass. Better to work on other math problems.
Lmao, wrong. If you were right the world would have heard of you by now and you would go down in the history books as solving one of the hardest problems in mathematics. The actual proof of this could not be so casually explained in a 4 minute video. TL;DR? Your proof absolutely wrong
You are basically saying "oh this is not right as it's not popular" and I feel like that's the worst argument you can think of. Your comment was unnecessarily mean and why don't you prove it wrong if you say it's not correct?
would not be more truthful to say "it can't be denied"? people tried using computers to find number that will disprove this, they failed. how then anyone can claim this is not provable? so weird... it's almost like religion. You lack proof and you are not able to deny it but still you claim it's unprovable.
Hello! I have independently studied the Conjecture for the past 7 months or so, including similar functions such as 3x+5 and 5x+1. I have a few explanations for what's going on, however I would like to keep studying, double check my work, and then have it peer reviewed before I release it by sometime next year. Ironically enough, I may have to default to using probability as one of the supporting reasons for why the Collatz Conjecture does not go to infinity. However, this is not because of the popular "every odd number becomes even" argument. I would like to keep studying because I am not sure if I can explain all of the problems with the function possibly diverging to infinity. Aside from infinity, I still struggle to understand how loops form the way they do. The best thing I found about loop formation is all of the loops of 3x+5 must have a multiple of 4 steps. While interesting, I can not use this for 3x+1. I do believe the Conjecture is provable, however this video does do a good job of pointing out some specific problems that the proof for the Conjecture would need an explanation for. If I am fortunate enough to have a good working proof, I will refer to this video to make sure I addressed all of the mentioned concerns. Good luck and stay curious!
