3 ms·

I can totally see how one could be sucked into this problem. The solution seems immediately reachable. After giving it some thought, I can prove that it is equ

I can totally see how one could be sucked into this problem. The solution seems immediately reachable. After giving it some thought, I can prove that it is equivalent to "every number will at some point reach a power of 2" because from a power of two you then go straight to 1 through divisions. This result seems even more reachable since I no longer need to prove that numbers eventually get smaller. I'm sure this is not a new discovery to people who have worked on the problem. But part of me really wants to spend the rest of the day puzzling around with where that approach goes. Edit: Thought about it more. The two ways it doesn't hit 1 would be for it to find a loop, that never hits a power of 2 or to grow infinitely. Thinking about how a loop with 3n+1 and n/2 would have to function, I think it's probably pretty easy to prove that 4-2-1 is the only loop that is possible. That leaves us with the infinite grows, but without ever hitting a power of 2. Edit2: Turns out 4-2-1 being the only loop that is possible is actually not easy to prove at all and isn't proven. But no matter, that wasn't how I was going to continue working on the problem anyway. The most promising solution to me is an inductive proof. Since I know all powers of 2 converge to 1 and only have /2 applied to them, my next step is to find the properties of numbers n such that 3n+1 is a power of 2. Only for every second power of 2 is this a whole number. The numbers for the powers of 2: [4, 16, 64, 256, 1024] have the possible precedents: [1, 5, 21, 85, 341]. Interestingly every subsequent number can be built from the previous one by 4n+1. Clearly it's 4 because it's every second power of 2. I feel like, if you recognize the structure of every number in the tree, you can prove that every natural number has one of those structures. And then you are done. Once again, I'm completely aware none of this is original thought. But I enjoy it anyway. Edit3: Every even number will be divided by 2 until it is an odd number. Now we only have to look at the structure of the odd numbers.

huffmsa 7y ago
Had the same thought further down the comments. Since you're getting even numbers at least 50% of the time, eventually you should go on a run. You also benefit from hitting a y =2^n x N number because you get to greatly reduced the size of y Further, every time you make it down to 1, you can append the values you hit on your way down to a list of seen values, as they're part of a convergence chain, meaning if you see them in a future cycle, you can stop your iteration early because you have a known outcome. So this doesn't necessarily become a computationally heavy problem with large numbers.
- huffmsa 7y ago
  And since 3n+1 will never be prime, you'll eventually reach a number which has factors which converge to 2^n
- cyborgx7 7y ago
  Yeah, this is definitely at least a semi-decidable problem. By following the process of the video in the beginning you can generate all values that converge towards 1, and you will reach each value at some point. Now, all that is missing is the other direction. How would you test if a number doesn't converge towards 0 in an algorithmic way that always finishes?
andrepd 7y ago
> I think it's probably pretty easy to prove that 4-2-1 is the only loop that is possible. Conjecture 2: https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/ https://terrytao.wordpress.com/2011/08/25/the-collatz-conjec... turns out its not :p
- cyborgx7 7y ago
  Damn, I was so sure it would be. This problem really is fascinating.
huffmsa 7y ago
The only way to grow infinitely is to hit more odd numbers than even, but you're hitting even at least 50% of the time. And eventually you'll get a number 2^n x N which will string together multiple divisions. So you're hitting n/2 more than 50% of the time, meaning your number is getting smaller more often than not, and will eventually go to 1.
- bluGill 7y ago
  If you hit even exactly 50% of the time you will grow to infinity - that is a sequence of even/odd will grow so long as the sequence continues, it is only when the sequence isn't even/odd that you will shrink. So you need to prove that you are hitting even more than x% of the time where x > 50. I'm not sure how to calculate the exact value of X though. This is one case where a single counter example would end the whole debate in about 5 minutes (I'm going to guess that is about how long it will take to calculate your whole sequence). However in absence of a counter example and the large number of of numbers that pass: it seems like it must be true - but we don't know how to prove it. We don't even know if it is possible to prove it (a proof that you can't prove it could be the greatest advance in math to this date - but again it is extremely hard to do that)
  - cyborgx7 7y ago
    You would first have to prove that the number is actually a counterexample. I don't know what you mean by calculating the whole sequence, as it would be an infinite sequence. Proving a counterexample seems like a halting problem kind of problem.
    - bluGill 7y ago
      Err... right. I stand corrected.
      - cyborgx7 7y ago
        But the question of a counterexample (eventhough it probably doesn't exist) is interesting. Is there a number for which we don't know weather it is a counterexample because it would take too long to compute? I feel like any single counterexample you'd propose would be proven wrong pretty quickly.

huffmsa 7y ago

Had the same thought further down the comments. Since you're getting even numbers at least 50% of the time, eventually you should go on a run. You also benefit from hitting a y =2^n x N number because you get to greatly reduced the size of y Further, every time you make it down to 1, you can append the values you hit on your way down to a list of seen values, as they're part of a convergence chain, meaning if you see them in a future cycle, you can stop your iteration early because you have a known outcome. So this doesn't necessarily become a computationally heavy problem with large numbers.

huffmsa 7y ago
And since 3n+1 will never be prime, you'll eventually reach a number which has factors which converge to 2^n
cyborgx7 7y ago
Yeah, this is definitely at least a semi-decidable problem. By following the process of the video in the beginning you can generate all values that converge towards 1, and you will reach each value at some point. Now, all that is missing is the other direction. How would you test if a number doesn't converge towards 0 in an algorithmic way that always finishes?

andrepd 7y ago

> I think it's probably pretty easy to prove that 4-2-1 is the only loop that is possible. Conjecture 2: https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/ https://terrytao.wordpress.com/2011/08/25/the-collatz-conjec... turns out its not :p

cyborgx7 7y ago
Damn, I was so sure it would be. This problem really is fascinating.

huffmsa 7y ago

The only way to grow infinitely is to hit more odd numbers than even, but you're hitting even at least 50% of the time. And eventually you'll get a number 2^n x N which will string together multiple divisions. So you're hitting n/2 more than 50% of the time, meaning your number is getting smaller more often than not, and will eventually go to 1.

bluGill 7y ago
If you hit even exactly 50% of the time you will grow to infinity - that is a sequence of even/odd will grow so long as the sequence continues, it is only when the sequence isn't even/odd that you will shrink. So you need to prove that you are hitting even more than x% of the time where x > 50. I'm not sure how to calculate the exact value of X though. This is one case where a single counter example would end the whole debate in about 5 minutes (I'm going to guess that is about how long it will take to calculate your whole sequence). However in absence of a counter example and the large number of of numbers that pass: it seems like it must be true - but we don't know how to prove it. We don't even know if it is possible to prove it (a proof that you can't prove it could be the greatest advance in math to this date - but again it is extremely hard to do that)
- cyborgx7 7y ago
  You would first have to prove that the number is actually a counterexample. I don't know what you mean by calculating the whole sequence, as it would be an infinite sequence. Proving a counterexample seems like a halting problem kind of problem.
  - bluGill 7y ago
    Err... right. I stand corrected.
    - cyborgx7 7y ago
      But the question of a counterexample (eventhough it probably doesn't exist) is interesting. Is there a number for which we don't know weather it is a counterexample because it would take too long to compute? I feel like any single counterexample you'd propose would be proven wrong pretty quickly.