谁解决了这个猜想，不说和哥猜的证明人一样有名， 也至少上很多大报的头条了。 |
you are under 40. |
Think of a Markov chain, with state space {1,2,...}. Notice that: 1) First verify that 1==>1, 4==>2==>1, 2==>1, therefore 1 is an absorbing state. 2) 4n ==> 2n, 4n+2 ==> 2n+1, they are absorbing states (become a smaller number); 3) 4n+1 ==> 3n+1, it is also an absorting state; 4) 4n-1 ==> 6n-1, with probability 0.5 to go to an absorbing state (4k+1). It is a transient state, with probability 1 to be absorbed. From above, all states (all positive integers) will eventually be absorbed to 1. Of course a formal proof can be more rigorous and will involve induction. |
很好的尝试。不过我有点看不懂，等其他各位来讨论吧！For any positive integer n, define the operations: F: F(n)=3n+1, n is odd, and G: G(n)=n/2, n is even. Now define a new operation H, For n even, n=(2^k)*m, where m is odd, H(n)=G(..G(n)..)=m, and For n odd, H(n) = F(n) = 3n+1. Therefore, H(n) turns odd to even, and even to odd. Now represent n in base 2, e.g., 43 ==> 101011. Notice that: 1) If n is even, H(n) removes the trailing zeros in n; 2) If n is odd, H(n)=3n+1=2n+n+1, where 2n is to add a trailing zero to n. We can verify that the number of 1's in H(n) is strictly decreasing. (By how many? I'll leave it as an exercise to you. A hint, think of XOR of neighboring bits.) 3) H(1)=100, H(100)=1. It is clear now that for any positive integer n, in limited steps, the number of 1's in n will be reduced to 1. QED. |
If n = 11...1 (all 1's), the number of 1's in H(n) equals that of n, but with a zero added as the second digit. For any other odd number n, which has 0's in between 1's, the number of 1's in H(n) is strictly less than that of n. |
what's the meaning of "XOR" in the sentence "think of XOR of neighboring bits." |
If n is odd, H(n)=3n+1=2n+n+1, where 2n is to add a trailing zero to n. We can verify that the number of 1's in H(n) is strictly decreasing. Seems not true;suppose n=1001001 then 2n = 10010010, n+1 = 1001010, and H(n) = 3n+1 = 11011100 so the number of 1's in H(n) increases in this case. |
You are right. I should've considered it more carefully. But I believe the idea is correct. In your case, we only need to apply H again. A thorough proof probably needs much more work. |
For any positive integer n, define the operations: F: F(n)=3n+1, n is odd, and G: G(n)=n/2, n is even. Now define a new operation H, For n even, n=(2^k)*m, where m is odd, H(n)=G(..G(n)..)=m, and For n odd, H(n) = H(F(n)) = H(3n+1) = m, for some odd m. Let's represent n in base 2, e.g., 43 ==> 101011. For convenience, I will need two more functions: B(n):= the number of bits of n. e.g. B(101011)=6. W(n):= the trailing consecutive 1's in n, e.g. W(101011)=2, W(101000)=0. 1) When n is even, H(n) removes the trailing 0's from n. Clearly B(H(n)) < B(n). 2) When n is odd, there are W(n) trailing 1's in n. H(n) has the following properties: 2.1) If W(n) > 1, then B(H(n)) <= B(n), W(H(n))=W(n)-1; 2.2) If W(n)==1, then B(H(n)) < B(n). In plain English, after each operation H, the number of bits will not increase, and the number of trailing 1's decrease by 1. When the number of trailing 1's is one, the next operation H will surely reduce the number of bits. For any positive integer n, in limited steps, the number of bits will be reduced to 1. QED. I thank QFT for pointing out my previous error. |
2.1) If W(n) > 1, then B(H(n)) <= B(n) It is wrong, e.g., 15 -> 23 -> 35. |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |