From Newsgroup: comp.theory

The proof is revised (bug fixed), even shorter (109 lines)!
----------
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. +---------+
| Preface |
+---------+
3x+1 problem: For any integer n greater than or equal to 1, if n is odd,
multiply by 3 and add 1. If n is even, divide by 2.
The question is, will all numbers be calculated to 1 using this method? The
following proof states that the answer is yes, they will always be calculated
to 1. Proving this problem using Peano's axioms like axiomatic system is
difficult (or would be very lengthy), so an algorithm (Turing machine model)
is used for proof. ----------------------------------------------------------------------------- Collatz function ::=
int cop(int n) {
if(n<=1) {
if(n<1) {
throw Error;
}
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: If an integer n, nreeN<1,+1>, after the cop iteration will
eventually calculate to 1 (i.e., cop(...cop(n))=1), then n is a Collatz
number. Otherwise n is not a Collatz number.
Collatz Problem: For each integer n, nreeN<1,+1>, is n a Collatz number? IOW,
the question is equivalent to asking whether the following procedure rcop
terminates or not.
void rcop(int n) {
for(;n!=1;) {
n=cop(n);
}
}
Prop: For any nreeN<1,+1>, the cop iteration operation terminates.
Proof: Let procedure rcop2 decomposes the n in rcop into n= a+b form.
void rcop2(int n) {
int a=n, b=0;
for(;a+b!=1;) { // a+b measure point A (a+b is equivalent to n in the
// cop iteration process)
if((a%2) != 0) {
--a; ++b; // a,b are adjusted so that a remains even, so that the
// following algorithm can be performed and remains
// equivalent to the cop(n) iteration.
}
// a/b measures point B
if((b%2)!=0) { // Equivalent to (a+b)%2 (because a is even)
a= 3*a;
b= 3*b+1; // 3*(a+b)+1 =(3*a) +(3*b+1)
}
a= a/2; // (a+b)/2 will be executed in each iteration
b= b/2;
}
}
Let n be odd and there be no --a, ++b process. Assume that each odd
operation is paired with an even operation. Then, at measurement point B,
we have:
areU= n-1
areo= (3*areoreireU)/2 =... = (n-1)*(3/2)-urU+-|
breU= 1
breo= (3*breoreireU+1)/2=... = 2*(3/2)-urU+-| -1
areo/breo= (areoreireU)/(breoreireU) = ((n-1)*(3/2)-urU+-|)/(2*(3/2)-urU+-| -1)
=... = (n-1)/(2- 1/(3/2)-urU+-|)
Interim summary: areo/breo < areoreireU/breoreireU, and lim{x->reR} areo/breo = (n-1)/2.
Because "approximately half the limit value (n-1)/2" (not including the
actual iterations which involve --a and ++b operations making areo smaller
and breo larger) is recursively true, we can deduce that:
(1) The actual value of areo/breo will decrease to the final value 0, and
a=0, eventually.
(2) The number of times breo is odd is less than the number of times breo is
even (there are two, or more, consecutive even operations).
Let r= a/b, areo=0. The value areoreireU, before iterating to 0, is 1 (measurement
point A). At this point, rreoreireU is a small value, relative to the initial
value rreU (the value of areo/breo can be considered as decreasing continuously
by (n-1)/2). When n>=5, breoreireU (=areoreireU*rreoreireU =rreoreireU) is guaranteed to be less
than n-1. Therefore, nreoreireU= areoreireU+breoreireU < 1+(n-1) <=> nreoreireU<n.
From nreoreireU<n, we can prove by mathematical induction that the proposition
"the iterative operation of cop(n) terminates" holds true.
+------------+
| References |
+------------+
[1] Real number contains infinity. Recurring decimals are irrational numbers.
Peano-Axioms system can hardly prove reRreerao.
https://sourceforge.net/projects/cscall/files/MisFiles/RealNumber2-en.txt/download
--- Synchronet 3.21b-Linux NewsLink 1.2