3 ms·
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
by 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 agoYes, 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