Groups | Search | Server Info | Keyboard shortcuts | Login | Register
Groups > comp.lang.c > #396517
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Collatz Conjecture proved. |
| Date | 2026-01-30 05:40 +0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <61986172eb7e65b7d17786f6f83015fed0c30ee1.camel@gmail.com> (permalink) |
| References | <96ed450bdb96454829f94b79519afa93595b27c1.camel@gmail.com> <5dbb5d96b3bb34ac21754a4f59617b572059e857.camel@gmail.com> <10lg35d$1eqba$1@dont-email.me> |
On Thu, 2026-01-29 at 16:50 +0000, Mike Terry wrote:
> On 24/01/2026 16:37, wij wrote:
> > 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).
>
> If you could prove just this much, you would become famous, at least amongst mathematicians!
>
> > 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
>
> I think "interpolated" is not the right word. Not sure exactly what is being claimed, but maybe
> this doesn't matter - check my next comment...
>
> > 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,
>
> Regardless of your reasoning, it is clear (and easily proved) that as the cycle repeats, aᵢ at the
> same point in the cycle must decrease until it becomes zero. At this point aᵢ remains zero for all
> further i, and no more --a,++b operations occur. (So there can only be finitely many such ops, but
> I agree aᵢ has to become zero, which seems to be what you want to claim.)
>
>
> > 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ₓ.
>
> That doesn't follow from anything you've said so far. So this proof will not make you famous. Maybe
> you can work on this and fill in the gap. You need an earlier "Prop: If aᵢ=0 then bᵢ <= 4" or
> equivalent". Then you can be famous!
>
> It does seem to be the case with numbers I've tried [n up to 30,000,000 ish], that aᵢ only becomes
> zero when we hit the final 1-4-2-1 cycle, so your claim is plausibly /true/, but that's not a
> /proof/ in any sense, of course.
>
> > 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
>
> This is just an approximation, not exact. It is not hard to get the exact value, since you seem to
> know about geometric series...
>
> > 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.
>
> I agree with this value (n-1)/2, /given your assumptions/ :
> - n odd
> - no --a operations
> - every odd op is followed by exactly one even op.
>
> But those assumptions are impossible in a real example, and real sequences will include multiple
> even ops and/or --a ops.
>
> OTOH all sequences have aᵢ/bᵢ as non-increasing, so aᵢ/bᵢ will reach zero (and stay there) or
> converge to some other limit value >= 0. In the latter case, you have not shown that that limit
> value will be (n-1)/2. (Hopefully your argument below does not depend on the particular value to
> which it converges?)
>
> > (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)
>
> It must converge, but not necessarily to (n-1)/2 ...
>
> After this point your argument seems to lose focus, and the notation is wrong!
>
> >
> > Let r = a/b, then n/b = (a+b)/b = a/b+1 = r+1
> > => b = (a+b)/(r+1)
>
> ok this is simple algebra for any /specific/ iteration value of n,a,b. These values are changing as
> we iterate...
>
> > 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)
>
> True for m,b,r for /that specific iteration/.
>
> > => 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)
>
> No that's not right - you're mixing values of m,b,r with those for later iterations of cop() and
> with limits. Also you're assuming r-->(m-1)/2. That was a specific result given your (impossible)
> assumptions listed above. In general r /does/ converge, but might converge to some other number, or
> become zero (in which case it also converges to zero so it's still true r converges). That is,
> unless you find a way to fix your proof to prove otherwise...
>
> To avoid confusing m,b,r as you've defined them with later iterations of cop(), best to call the
> values for later iterations mᵢ,bᵢ,rᵢ or similar. And assume rᵢ-->R (e.g.).
>
> So:
> The limit of r+1 = R+1 // with possibility R=0
> bᵢ = mᵢ/(rᵢ+1)
> lim bᵢ = lim mᵢ / (R+1)
> ... EXCEPT that you have not shown that mᵢ converges, so that last line is nonsense - we only use
> 'lim' symbol when we the limits are known to exist...
>
> >
> > Since there is a limit (the numerical value is not important),
>
> ??? a limit to what? rᵢ ---> R, but it seems you're trying to argue bᵢ converges? That's not
> plausible. You can see this must be wrong, just from your earlier (overly) simplified sequence for
> which you originally calculated R = (n-1)/2. In that calculation you wrote:
>
> bₓ = (3*bₓ₋₁+1)/2 = ... = 2*(3/2)ˣ⁻¹ -1
>
> and it is clear that bᵢ is growing in an unbounded fashionry, not converging to b=2. You've just
> got muddled... Note: I don't necessarily agree with this bₓ formula - it looks to be only an
> approximation, but I do agree with your aₓ/bₓ limit [with your given assumptions].
>
> > 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.
>
> That is also not right - once aᵢ becomes zero, there will be /no more --a operations, so there can't
> be infinitely many of them!
>
> Regardless:
>
> 1. IF there are infinitely many iterations of --a, they can be interspersed
> with a *= 3 operations, so it does not follow (just from what you've said)
> that a /must/ become zero.
> 2. If a does become zero, it does not follow that the 1-4-2-1 loop has been
> encountered, unless you have some argument to prove that. [This is
> the same problem as with your earlier "no cycles" proof.]
>
> >
> > 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.
> >
> ..aside from fixing the problems above.
>
>
> Mike.
I agree with many point of your criticism, it is helpful.
Since your comments are on the original script, I will post the updated version to avoid
unnecessary reply.
--- [quote from the finalized version]
Prop: ....[cut]
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;
}
}
The following proof demonstrates:
1. The ratio a/b is decreasing.
2. b has limit.
3. a must decrease to below b because of the above reasons.
4. Done, n=a+b has limit (cop(n) is known to terminate for n<2¹⁶ at
least).
Let n be odd and there be no `--a`, `++b` process. Assume that each odd
operation is paired with only one even operation, 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) = n/(r+1)
After sufficient iterations:
=> The limit of r+1 = (n-1)/2 + 1 = (n+1)/2
=> b = (2*n)/(n+1) = 2/(1+1/n)
=> b = 2 (the limit of b. it is known that n is a large number)
Since b has 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
condition.
----------------------
1. a/b ratio (formula) is a lower bound estimate as stated. In the real cases,
it decreases faster.
2. In the iteration, even ops does not change a/b ratio. Ops --a,++b only makes
the ratio a/b more decreasing.
3. The proof only needs to show there is a limit. What value a/b converges does
not important.
Back to comp.lang.c | Previous | Next — Previous in thread | 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