Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #395941
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Collatz Conjecture proved. |
| Date | 2025-12-24 20:05 +0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <96ed450bdb96454829f94b79519afa93595b27c1.camel@gmail.com> (permalink) |
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).
-------------------------------------------------------------------------------
Back to comp.lang.c | Previous | Next — Next in thread | Find similar
Collatz Conjecture proved. wij <wyniijj5@gmail.com> - 2025-12-24 20:05 +0800
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
Re: Collatz Conjecture proved. Jan van den Broek <fortytwo@xs4all.nl> - 2026-01-31 14:11 +0100
Re: Collatz Conjecture proved. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-02-03 03:58 -0800
Re: Collatz Conjecture proved. Jan van den Broek <balglaas@dds.nl> - 2026-02-03 21:27 +0000
csiph-web