4 ms·

One interesting way to look at this is as a bit twiddling puzzle. The "N /= 2 if even" step is removing all the rightmost 0s in the binary representation. The r

One interesting way to look at this is as a bit twiddling puzzle. The "N /= 2 if even" step is removing all the rightmost 0s in the binary representation. The remaining bits on the left have "(N << 1) + N + 1" applied. Wonder if the behavior of those remaining bits can be broken down into a finite set of conditions and be shown to eventually yield a power of 2.

ealexhudson 6y ago
Eventually getting to a power of 2 means that n*3 must eventually, at some point, be a non-prime Mersenne number. If there were something about the initial conditions it feels like you'd be saying something about the distribution of Mersenne primes, which is unlikely?
acqq 6y ago
Yes in pseudo C-like binary-oriented notation the step is: if ( lowest bit of x is 0 ) x >>= 1 else x += ( x << 1 ) + 1 And it's immediately obvious that the else branch always produces an even number.
- eigenket 6y ago
  Yes, this is quite well known. See (e.g.) the third paragraph on Terrence Tao's blog here 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... For what its worth Tao is possibly the only person in the world I wouldn't be shocked to hear of making progress on the Collatz conjecture. He actually proved a pretty nice result on it recently https://arxiv.org/abs/1909.03562 https://arxiv.org/abs/1909.03562 but the technology employed doesn't seem strong enough to go beyond "almost all" statements.
  - acqq 6y ago
    > Yes, this is quite well known. Sure, thanks for that Terence Tao links! I just wanted to confirm the efficiency of C notation to "see" what happens with the bits at the lowest level in this case, at least to those used to C. Now thinking about it, literal C would be even more concise: if ( x & 1 ) x >>= 1 else x += ( x << 1 ) + 1
    - zvr 6y ago
      You have the then/else parts reversed -- and missing semicolons.
      - acqq 6y ago
        Yes, you‘re right, thanks.

ealexhudson 6y ago

Eventually getting to a power of 2 means that n*3 must eventually, at some point, be a non-prime Mersenne number. If there were something about the initial conditions it feels like you'd be saying something about the distribution of Mersenne primes, which is unlikely?

acqq 6y ago

Yes in pseudo C-like binary-oriented notation the step is: if ( lowest bit of x is 0 ) x >>= 1 else x += ( x << 1 ) + 1 And it's immediately obvious that the else branch always produces an even number.

eigenket 6y ago
Yes, this is quite well known. See (e.g.) the third paragraph on Terrence Tao's blog here 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... For what its worth Tao is possibly the only person in the world I wouldn't be shocked to hear of making progress on the Collatz conjecture. He actually proved a pretty nice result on it recently https://arxiv.org/abs/1909.03562 https://arxiv.org/abs/1909.03562 but the technology employed doesn't seem strong enough to go beyond "almost all" statements.
- acqq 6y ago
  > Yes, this is quite well known. Sure, thanks for that Terence Tao links! I just wanted to confirm the efficiency of C notation to "see" what happens with the bits at the lowest level in this case, at least to those used to C. Now thinking about it, literal C would be even more concise: if ( x & 1 ) x >>= 1 else x += ( x << 1 ) + 1
  - zvr 6y ago
    You have the then/else parts reversed -- and missing semicolons.
    - acqq 6y ago
      Yes, you‘re right, thanks.