Collatz 3n + 1 conjecture possibly solved

Gerhard Opfer has posted a paper that claims to resolve the famous Collatz conjecture.

Start with a positive number n and repeatedly apply these simple rules:

  1. If n = 1, stop.
  2. If n is even, divide n by 2.
  3. If n is odd, multiply n by 3 and add 1.

In 1937, Lothar Collatz asked whether this procedure always stops for every positive starting value of n. If Gerhard Opfer is correct, we can finally say that indeed it always stops.

Update: It appears there’s a flaw in the proof. See discussion here. Perhaps the gap can be filled in, or perhaps an idea in the paper can be of use somewhere else.

Related post: Easy to guess, hard to prove

26 thoughts on “Collatz 3n + 1 conjecture possibly solved

  1. Wow!

    Have you tried to read the paper yet? It looks like it’s a little bit above my head. But nowadays I can ask around for help understanding something like this.

    I’m sad in a way. It was pretty cool to have a problem kids like playing around with and to know it had no solution.

  2. I haven’t read that kind of math for 5+ years so like Sue I can’t get through the paper… but it seems that it’s reasonable to expect it to stop if, in the long run, the 3n+1 operation mostly gives you numbers that can be divided twice in a row. Since you’re dividing by 4 then, it goes down faster than it goes up. In fact if that happens just over 75% of the time I think it would eventually end.

    Any odd number can be expressed at 2x+1, so if you multiply that by 3 and add 1 you end up with 6x + 4. The 4 can be divided by 4, so you need to know if the 6x can be divided by 4 most of the time – in other words if 3x is even. The series of odd numbers alternates between 2*+1 and 2* + 1 so half the x values will be even.

    That doesn’t seem sufficient, so I think you would need to either prove that it is or show that doing 3n+1 a few times tends to lead to more even numbers (maybe you do it 10 times and then you can divide by 2 20 times, or you do it 100 times than divide by 2 200 times). If it does work it’s probably by a very small margin.

    Alternately you could take the sequence of numbers that go straight to 1 because they’re the product of even numbers only, and then show that multiplying by 3n+1 enough times will eventually get you to one of those numbers. Then the question is how many times you need to do 3n+1 to hit a product of evens.

    In another 70 years I think I’ll have this 🙂

  3. Come now, “Collatz 3n + 1 conjecture solved”? A bit sensationalist, don’t you think? =) The paper has not even undergone peer review yet. That said, however, it certainly does look like a serious attempt — by a student of Lothar Collatz, no less! Let’s hope that it’s correct (and that I can understand it)!

  4. First error I caught was “The Collatz conjecture states, that all Collatz sequences terminate after finitely many steps with the cycle 4, 2, 1, . . .”

    Tut; n=2.

  5. @Richard “In fact if that happens just over 75% of the time I think it would eventually end.”
    I don’t think your reasoning is correct (well, it depends what you mean by “end”). I agree that the sequence tends to decrease, but you can reach a cycle. Actually one can generalize the sequences to rational numbers, and even though you can do the same reasoning, there are an infinite number of cycles.
    About 20 years ago, I tried a probabilistic approach: find the probability of getting a cycle of length c (with the operations (3n+1)/2 for n odd and n/2 for n even), and got a relation with the partial quotients and convergents of the continued fraction of log(3)/log(2). The goal was not to be rigorous, but to try to intuitively explain what we can observe. My memory is a bit weak, because I thought I obtained all the cycles (with any integer, i.e. possibly negative) with convergents, but after looking at http://en.wikipedia.org/wiki/Collatz_conjecture I can see a cycle with negative integers that doesn’t correspond to a convergent.
    IIRC, I obtained the same formula as the one on Wikipedia (with different notation) about cycles of length c with b odd numbers: (3^{b-1} 2^{k_0} + … + 3^0 2^{k_{b-1}}) / (2^c – 3^b). What I was saying that |2^c – 3^b| should be “small” for some magnitude of b and c to increase the chance of getting an integer, hence the relation with the continued fraction of log(3)/log(2). Something I had noted is that the partial quotients of even position (i.e. the last partial quotient for the cases where 2^c – 3^b > 0) for positions 4 to 10 are larger than those of odd position, which is a bit bad luck…
    Actually, I now think this is much more complex and convergents don’t necessarily matter as they are too scarce. A naive probability is binomial(c,b) / (c * |2^c – 3^b|), the sign of the integers of the sequence being the sign of 2^c – 3^b. But I this is not sufficient, because the sum from b = 0 to b=c-1 doesn’t decrease quickly enough.

  6. @Scott: that’s not an error! The sequence starting with 2 is 2, 1, 4, 2, 1, 4, 2, 1, … as you can easily check, so it does fall into that cycle.

  7. So why don’t we just prove it and be done with it? Pick a number, any number. If it’s even and a power of 2, then repeated division by 2 (that pesky n/2 if n is even statement ) will converge to 1. If it’s odd, then 3n+1 will make it even. As my old math instructors would say “It’s intuitively obvious to even the most casual observer” , but you can prove it if you must. So ok, dividing that result by 2 will either end with another odd number eventually, or it will go to 1. When will it go to 1? When it’s a power of 2. That means we should find all of the numbers that make 3n+1 a power or 2. A little fiddling in Excel and you find that a starting set is (1,5,21,341, 1365, …) . You don’t really need 1 since it is, after all the solution to the whole mess, but I included it so you can see the really cool pattern that evolves.

    Thus 3*1+1 = 4 =2**2, 3*5+1 = 16, 3*21 +1 = 64 = 2**6, 3*341 + 1 = 1024 = 2**10 just to show a couple of examples. By the way, * means “times ” or multiplied by, ** means “exponent” or “to the power of” .

    The really cool pattern (as promised) is this:
    1 = 2**0 + 0, 5 = 2**2 + 1, 21 = 2**4 +5, 85 = 2**6+21, 341 = 2**8 + 85, 1365 = 2**10 + 341 and so on. As you can see (by looking at the exponents), for any even number (0, 2, 4, …) we can construct an odd number which, when plugged in to 3n+1, is a power of 2 and thus converges to 1. With the formula 3n+1 we can construct an even number from any odd number (1,3,5,7,9…). Since these 2 sets combined form the natural numbers, I say it’s QED.

  8. Of course “the really cool pattern” above cannot proove the Collatz Conjecture.
    If it was so easy, we could as well replace the term 3n+1 by simply +11, which also creates an even number from any odd number. The pattern then becomes even cooler, since any power of 2 – not only {2^n where n is even} – minus 11 is an odd number. But our resulting new conjecture, that any number leads to 1, is clearly false. q.e.d

  9. Guys,

    I am not a math student , but if I look at positive numbers only why is it so difficult to prove it ? Can a simple non mathematical explanation not suffice to prove the
    conjecture.

    Lets assume the conjuncture is incorrect .

    So we have a repeating sequence which ends in suppose number “n”
    since n is the last number in the sequence before repetition starts n has to be odd and the first number in sequence would be 3n+1.

    The repeating sequence would proceed as follows

    3n+1 , (3n+1)/2,(3n+1)/(2^2)… this would continue till we reach
    a point where
    (3n+1)/(2^x)=n
    2^x*n – 3n =1
    n(2^x – 3) = 1
    This is only possible if n=1 and (2^x-3)=1

    Since n=1 is the only possibility the conjecture is true.

    Would appreciate any feedback.

  10. Ravi,

    The “multiply by 3 and add 1” might have to kick in again before you get back to n.

    Your argument shows that 1 is the only possibility if the “multiply by 3 and add 1” only happens once.

    Maybe you can use it for some inductive argument, but I doubt it.

  11. Ok, a bit of a variant, but… I’m a teacher and not a high-level mathematician and just learned about this via the MathPickle site which uses the conjecture within the context of a story (Icarus and Daedalus)… long story short, the goal is “not” to get to 1. Icarus’s problem is the Collatz conjecture. Daedalus’s is identical with one exception – triple and SUBTRACT one. With that change, there are numbers that will “loop”. I want to learn more about this 3n-1 conjecture. Can anyone point me in that direction? Love Collatz conjecture but curious about why the Daedalus variant WILL work… sometimes.

  12. Hi,
    Any number positive integer number between [2^k]+1 and [2^(k+1)]-1 would require never less than k steps to converge to 1 using the Collatz algorithm. Thus if lim[k->infinite] {2^k}=infinite therefore the number of steps would be approaching at least infinite, the series will diverge and the conjecture is wrong.
    Just a reasoning that is got to be wrong somewhere, ¿any help to identify where?. Regards,

  13. Razvan Marinovici

    The sequence is completely linked to the starting number`s bit pattern. It’s not random. It depends on the flow of bits of the starting number. It’s not the number of 1`s or 0`s it is the actual position of the bits.

    Also the series is made from a lot of “restarts”, at each ceil(log2(n)) condensed steps, the series will “restart”, the original number is consumed, bit pattern exhausted.
    Example.
    5 – Reaches 2 after 3 steps and goes from there
    7 – Reaches 26 after 3 steps and starts fresh, 26 -> after 5 steps reaches 8
    17 – Restarts at 5 after 4 steps
    23(11011) – Restarts at 20 after 5 steps
    27(11101) – Restarts at 71 after 5 steps, so 71 is an fresh start, a new series (end of series for 27).

    It’s easy to find/calculate an infinity of numbers that go through X = (1,2) mod 3. The first number will be at ceil(log2(n)) condensed steps away from X. No number will have a series ending in X=0 mod 3 (not sure about this one)

    For example some numbers that go through 71
    221 -> 2^8
    14601557 -> 2^24
    14601781 -> 2^24
    470383381 -> 2^29
    4136169948971763906787 -> 2^72 will reach 71 after 72 steps
    8278656945066165491029 -> 2^73 will reach 71 after 73 steps

    5041018883571751 -53 steps-> 4267784006233 -42 steps-> 91354821257 -37 steps-> 6952931999 -33 steps-> 2*470383381 -30 steps-> 71

    All above numbers will have a different path to 71, however from that point onward it is a new series, common for all.

    If we look at the complete series it might be difficult to find a pattern, if we look at one piece at a time it might become easier. It’s even difficult to look at the bits and see something.

    Because it is a bit pattern, it is a binary tree, so it resumes to walking through the tree and finding a leaf that leads to a cycle, the process of walking through the tree gives us the (a)-> goes to ->(b). I think it might be easier than calculating all numbers and checking if they eventually cycle.

    We can try and construct a number. We can definitely go further away than 2^60.

  14. Deb, your variant is equivalent to considering the 3n+1 rule applied to negative numbers. See Wikipedia for details.

  15. After reading through some of the paper and finding MATLAB algorithms as evidence for sections of the proof I was a little disappointed. The abstract also leaves me wondering what holomorphic mappings to the complex unit disk with two linear functional equations has to do with number theory. It seems to me that some complex variable research may have been applicable to the Collatz conjecture and they attempted to apply it as a solution.

    Converging series seems to be the key to this problem. The issue is that they need to simultaneously be built through induction while also showing any number in the natural numbers is contained in one of these series through induction. Which the paper seems to be attempting to address through the use of the linear functional equations and the complex disk.

    The elephant in the room is the countable infinity of the natural numbers, and the finite arbitrary sequences that resolve no matter which starting value is chosen.

    In essence you need to build out those sequences but arbitrarily, for example the sequence:

    (Thinking of n=5)
    {n, 3n+1, (3n+1)/2, (3n+1)/4, (3n+1)/8, (3n+1)/16}

    You need infinitely many of these built out somehow through induction, and then through a separate induction process you need to show any arbitrary starting value will result in a sequence that contains one of those sequences as a subsequence (another piece that the paper also attempts to address).

    Logically this is very tricky as you need to work in two contrary directions simultaneously to achieve a proof, which has always proven difficult in mathematics 😉 You need exposure to graduate level mathematics regularly to learn the logical told for these conundrums. I’m assuming the use of the complex disk with the linear functional equations is one such method.

    These problems certainly are fun, this has got me remembering real analysis and Cauchy sequences. I guess I should brush up on some mathematics from time to time, I sure miss it from completing my undergrad.

  16. Hi guys, I am not a mathematician so can someone please explain what is so hard to prove about this conjecture? I can graph the numbers in my head and reason out using it why it will converge. I apologise, as I said I am not from mathematics field. My knowledge is very limited for this.

Leave a Reply

Your email address will not be published. Required fields are marked *