Groups | Search | Server Info | Keyboard shortcuts | Login | Register
Groups > comp.lang.c > #396520
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Collatz Conjecture proved. |
| Date | 2026-01-30 11:03 +0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <9abc83f6fa352ccf3b1b61b29be9b86c75dad316.camel@gmail.com> (permalink) |
| References | <96ed450bdb96454829f94b79519afa93595b27c1.camel@gmail.com> <5dbb5d96b3bb34ac21754a4f59617b572059e857.camel@gmail.com> <10lg35d$1eqba$1@dont-email.me> <61986172eb7e65b7d17786f6f83015fed0c30ee1.camel@gmail.com> <10lh4i6$1pdbd$1@dont-email.me> |
On Fri, 2026-01-30 at 02:20 +0000, Mike Terry wrote:
> On 29/01/2026 21:40, wij wrote:
> > 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.
>
> So we agree a/b converges, but the updates above do not address any of the problems raised in my
> previous post...
>
> Mike.
Will you elaborate precisely?
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