From Newsgroup: comp.lang.c

goolge translate is terrible recently, its output is different everytime!
I am not sure the idea will be conveyed properly, esp. for those not familiar
with the Collatz Conjecture. If not, its my failure.
While looking back, the proof of Collatz Conjecture is unbelievably simple.
I think it is because: According to the Church–Turing conjecture (and my own
conjecture): No formal language has greater expressive power than procedural
language, particular C/C++ (just imagine that if this proof was made in
traditional formalism).
But the development of C is, IMO, 'average'. C++ 'may be' still superstitous
in their 'expressive' and 'useful'....
This file is intended a proof of Collatz Conjecture. The contents may be updated anytime. https://sourceforge.net/projects/cscall/files/MisFiles/Coll-proof-en.txt/download
The text is converted by google translate with modest modification from https://sourceforge.net/projects/cscall/files/MisFiles/Coll-proof-zh.txt/download
Reader might want to try different translator or different settings. ----------------------------------------------------------------------------- Collatz function ::=
int cop(int n) {
if(n<=1) {
return 1; // 1 is the iteration endpoint
}
if(n%2) {
return 3*n+1; // Odd number rule
} else {
return n/2; // Even number rule
}
}
Collatz number(n): If an integer n, n>=1, the cop iteration operation will
eventually calculate to 1 (i.e., cop(...cop(n))=1), then n is a Collatz
number.
Collatz Conjecture: For all integer n, n>=1, n is a Collatz number.
The cop operation can be managed to an ibp function is a combination of
(3n+1)/2 and n/2 operations. Each ibp operation is processed according to
the least significant bit (LSB) of n. 0 corresponds to the n/2 operation
and 1 corresponds to the two cop operations (3n+1)/2.
int ibp(int n) {
if(n<=1) {
return n; // 1 does not iterate
}
if(n%2) {
n= (3*n+1)/2; // Odd and even cop operations are considered as one
// ibp iteration
} else {
n/=2;
}
return n;
};
Let the bit sequence of n be abc. The ibp iteration result can be roughly
shown in the following figure ((3x+1)/2= x+⌊x/2⌋+1):
abc
1+ abc // x3+1 operation
1+ abc // If there is an even operation (i.e. n/2), delete a line
1+ abc
ABCXX // The state after ibp iteration: A,B,C represent the sum of
// bits related to a,b,c and carry. X represents carrys not
// directly related to a,b,c.
Let n=JK, J,K represent two consecutive base-2 numbers. Let |K|
represent the number of bits of the binary number of K, then after n goes
through |K| times of ibp operation process, the remaining J will be changed
to J' due to odd/even operations and carrys. However, the maximum value of
J' is approximately J*(3/2)^|K|. The maximum length of J' is approximately
log(J*(3/2)^|K|)= log(J)+ 0.4*|K|.
Prop: For any integer n, n>1, the iteration of the cop function of n will always
result in a number equal to 1.
Proof: Assume that all numbers with the bit length less than or equal to |n|
are Collatz numbers. Let the binary representation of n be 1ddd. 2n, 2n+1
be 1ddd# (# represents 0 or 1). Let the binary form of K be ddd#, J=1
(the most significant bit).
Assum J becomes J' after |K| ibp operations, |J'|= |J|+ 0.4*|K| =
1+ 0.4*|K|.
By assumption, if |J'|≤ |K|, then J' will be a Collatz number because
when |K|>=2, J' is also a Collatz number.
1+0.4*|K|≤ |K|
<=> 1 <= |K|- 0.4*|K|
<=> 1 <= 0.6*|K|
<=> 1/0.6 ≤ |K|
Thus, the cop iteration for integers 2n and 2n+1 will calculate to 1.
That is, all integers greater than 4 are Collatz numbers (since 1, 2,
and 3 are known to be Collatz numbers). ------------------------------------------------------------------------------- --- Synchronet 3.21a-Linux NewsLink 1.2