goolge translate is terrible recently, its output is different everytime!
I am not sure the idea will be conveyed properly, esp. for those not famil
iar
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 procedur
al
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 superstito
us
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/do wnload

The text is converted by google translate with modest modification from https://sourceforge.net/projects/cscall/files/MisFiles/Coll-proof-zh.txt/do wnload
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 wil
l
eventually calculate to 1 (i.e., cop(...cop(n))=1), then n is a Colla
tz
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 operatio
n
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 rough
ly
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 no
t
// 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 go
es
through |K| times of ibp operation process, the remaining J will be cha nged
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 approximat
ely
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 a lways
result in a number equal to 1.

Proof: Assume that all numbers with the bit length less than or equal t
o |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 numbe
r 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). --------------------------------------------------------------------------- ----


--- PyGate Linux v1.5.2
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)