Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #396446
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Collatz Conjecture proved. |
| Date | 2026-01-25 00:37 +0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <5dbb5d96b3bb34ac21754a4f59617b572059e857.camel@gmail.com> (permalink) |
| References | <96ed450bdb96454829f94b79519afa93595b27c1.camel@gmail.com> |
On Wed, 2025-12-24 at 20:05 +0800, wij wrote:
I have just finished the script. Any defect,insufficiency, or typo?
------------------
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) {
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, n∈N<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, n∈N<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: cop(n) iteration contains no cycle (except for the '1-4-2-1' cycle, since
1 is the termination condition).
Proof: n can be decomposed into n= a+b. rcop(n) can be rewritten as rcop2(n):
void rcop2(int n) {
int a=n,b=0;
for(;a+b!=1;) { // a+b= n in the cop iterative process.
if((a%2)!=0) {
--a; ++b; // Adjust a and b so that a remains even and the
// following algorithm can be performed and remains
// equivalent to cop(n) iteration.
}
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)
} else {
a= a/2;
b= b/2;
}
}
}
Let nᵢ, aᵢ, bᵢ represent the values n,a, and b in the iteration.
Assume that the cop(n) iteration is cyclic. The cycle is a fixed-length
sequence, and the process must contain the operations 3x+1 and x/2 (and
the associated operations --a and ++b, unless n is a 2^x number, but such
numbers do not cycle). Let the cyclic sequence of n be:
n₁, n₂, n₃, ..., nₓ (n=n₁).
Because --a and ++b are continuously interpolated during the cycle, if
aᵢ≠0, then bᵢ and nᵢ=aᵢ+bᵢ will increase infinitely, contradicting the
assumption that nᵢ is cyclic. Therefore, aᵢ=0 must hold during the cycle,
but the condition of aᵢ=0 only exists in 1-4-2-1, aᵢ=0 cannot cause the
non-1-4-2-1 cycle of n₁,n₂,n₃,...,nₓ.
Therefore, we can conclude that cop(n) iterations are non-cyclic.
Prop: For any n∈N<1,+1>, the cop iteration operation terminates.
Proof: Since an odd number n will always become even immediately after the
cop iteration, it must undergo n/2 iterations. Therefore, we have an
equivalent rcop3:
void rcop3(int n) {
int a=n,b=0;
for(; a+b!=1;) {
if((a%2)!=0) {
--a; ++b;
}
// a/b measure point A
if((b%2)!=0) {
a= 3*a;
b= 3*b+1;
}
a= a/2;
b= b/2;
}
}
Let n be odd and there be no `--a`, `++b` process. Assume that each odd
operation is paired with only one even operation (the actual ratio is 1.5
even operations, but 1.5 is a statistical value; the decisive inference
can only take the guaranteed value of 1). Then, at measurement point A,
we have:
a₁ = n-1
aₓ = (3*aₓ₋₁)/2 = ... = (n-1)*(3/2)ˣ⁻¹
b₁ = 1
bₓ = (3*bₓ₋₁+1)/2 = ... = 2*(3/2)ˣ⁻¹ -1
aₓ/bₓ = (aₓ₋₁)/(bₓ₋₁) = ((n-1)*(3/2)ˣ⁻¹)/(2*(3/2)ˣ⁻¹ -1)
= ... = (n-1)/(2-1/(3/2)ˣ⁻¹)
Interim summary: aₓ/bₓ < aₓ₋₁/bₓ₋₁ and lim{x->∞} aₓ/bₓ = (n-1)/2.
(After eight iterations, aₓ/bₓ is approximately 0.51. Actual iterations
may also include --a and ++b operations, so the actual value of aₓ/bₓ
will converge faster than the formula)
Let r = a/b, then n/b = (a+b)/b = a/b+1 = r+1
=> b = (a+b)/(r+1)
Assuming the cop(n) iteration does not terminate, and m is one of the
number in the iteration sequence. Therefore, we can derive the
following:
=> b = m/(r+1)
=> The limit of r+1 = (m-1)/2 + 1 = (m+1)/2
=> b = (2*m)/(m+1) = 2/(1+1/m)
=> b = 2 (the limit of b. At least it is known that m will be a large
number)
Since there is a limit (the numerical value is not important), the
iteration involves an infinite number of iterations of --a, a will
inevitably become zero, so the iteration cannot fail to meet the
iteration termination contion.
If n is even, then repeating the even operation (a finite number of times)
cop(n) will yield an odd number without affecting the termination result
as stated above. Therefore, the proposition is proved.
[Reference] Real number and infinity. Recurring decimals are irrational numbers.
https://sourceforge.net/projects/cscall/files/MisFiles/RealNumber2-en.txt/download
Back to comp.lang.c | Previous | Next — Next in thread | Find similar
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-25 00:37 +0800
Re: Collatz Conjecture proved. Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-25 00:23 +0000
Re: Collatz Conjecture proved. James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-01-24 23:06 -0500
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-25 13:28 +0800
Re: Collatz Conjecture proved. Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-25 08:15 +0000
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-25 16:46 +0800
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-25 10:38 +0100
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-25 18:55 +0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-25 19:06 +0800
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-25 12:47 +0100
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-25 23:44 +0800
Re: Collatz Conjecture proved. James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-01-25 12:22 -0500
[OT] Proofs. Was: Collatz Conjecture proved. Ben Bacarisse <ben@bsb.me.uk> - 2026-01-25 11:33 +0000
Re: [OT] Proofs. Was: Collatz Conjecture proved. richard@cogsci.ed.ac.uk (Richard Tobin) - 2026-01-25 13:11 +0000
Re: Collatz Conjecture proved. Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-25 18:52 +0000
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-26 03:58 +0800
Re: Collatz Conjecture proved. James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-01-25 11:25 -0500
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-26 01:20 +0800
Re: Collatz Conjecture proved. Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-01-26 01:25 +0100
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-26 23:51 +0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-27 00:07 +0800
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-26 21:05 +0100
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-26 21:07 +0100
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-27 04:34 +0800
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-27 09:21 +0100
Re: Collatz Conjecture proved. antispam@fricas.org (Waldek Hebisch) - 2026-01-27 16:31 +0000
Re: Collatz Conjecture proved. Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-01-27 18:24 +0100
Re: Collatz Conjecture proved. antispam@fricas.org (Waldek Hebisch) - 2026-01-28 15:17 +0000
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-27 18:44 +0100
Re: Collatz Conjecture proved. Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-01-27 22:52 +0000
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-28 08:29 +0100
Re: Collatz Conjecture proved. Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-01-28 10:27 +0100
Re: Collatz Conjecture proved. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-01-28 12:59 -0800
Re: Collatz Conjecture proved. Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-01-30 06:33 +0100
Re: Collatz Conjecture proved. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-01-30 11:59 -0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-28 04:08 +0800
Re: Collatz Conjecture proved. Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-01-27 15:11 -0800
Re: Collatz Conjecture proved. Ben Bacarisse <ben@bsb.me.uk> - 2026-01-28 17:34 +0000
Re: Collatz Conjecture proved. richard@cogsci.ed.ac.uk (Richard Tobin) - 2026-01-28 18:23 +0000
Re: Collatz Conjecture proved. David Brown <david.brown@hesbynett.no> - 2026-01-29 08:39 +0100
Re: Collatz Conjecture proved. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-01-28 13:02 -0800
Re: Collatz Conjecture proved. James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-01-26 21:18 -0500
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-28 04:01 +0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-30 08:29 +0800
Re: Collatz Conjecture proved. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-01-27 19:46 -0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-28 12:34 +0800
Re: Collatz Conjecture proved. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-02-03 04:16 -0800
Re: Collatz Conjecture proved. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-01-28 13:04 -0800
Re: Collatz Conjecture proved. Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-01-29 16:50 +0000
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-30 05:40 +0800
Re: Collatz Conjecture proved. Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-01-30 02:20 +0000
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-30 11:03 +0800
Re: Collatz Conjecture proved. Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-01-30 04:22 +0000
Re: Collatz Conjecture proved. Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-01-29 20:38 -0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-31 05:30 +0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-02-06 14:16 +0800
Re: Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2026-01-30 11:52 +0800
csiph-web