Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #139421

Re: Collatz Problem proved.

Show all headers | View raw

On Sat, 2026-01-24 at 14:41 -0500, Richard Damon wrote:
> On 1/24/26 11:51 AM, 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
> > 
> 
> My first thought is you ASSUME that the result is some other cycle, and 
> not that some number can continually grow.
> 
> While every 3n+1 will be even and thus we divide by two, that result 
> (3n+1)/2 will still be bigger than n, and can be odd. The sequence can 
> even have some steps with multiple divides as long an they are 
> infrequent enough as a divide by 2 step followed by a divide by 4 step 
> get you to:
> 
> 3*(3n+1)/2+1)/4 = 9/8*n + 3/8 which is still growing.
> 
> Thus even 1.5 Even operations per odd isn't enough to prove convergence.
> 
> To get the numbers to be not increasing you need to show that you get at 
> least log2(3) ~ 1.585 even steps per odd step
> 
> Until you prove the values converge and not grow continually, your limit 
> operations don't apply.

Yes, iteration of cop(n) is proved to 'converge' (this word could be misleading
to convey the idea of 'equal'. See the reference, converge is not equal).

1. The proof shows the the ratio a/b is decreasing
2. b has limit
3. a must decrease to below b because of the above reason (a/b is decreasing 
   and b has limit).
4. Done, n=a+b has limit (cop(n) is known to terminate for values less than 
   2^16 at least).

What is interesting is that Collatz Problem defies nearely all proofs based on 
traditional logic, formalism. Similar kinds of understanding/reasoning likely 
won't work here.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Collatz Problem proved. wij <wyniijj5@gmail.com> - 2026-01-25 00:51 +0800
  Re: Collatz Problem proved. Richard Damon <Richard@Damon-Family.org> - 2026-01-24 14:41 -0500
    Re: Collatz Problem proved. wij <wyniijj5@gmail.com> - 2026-01-25 05:32 +0800
      Re: Collatz Problem proved. Richard Damon <Richard@Damon-Family.org> - 2026-01-24 18:19 -0500
        Re: Collatz Problem proved. wij <wyniijj5@gmail.com> - 2026-01-25 08:34 +0800
          Re: Collatz Problem proved. Richard Damon <Richard@Damon-Family.org> - 2026-01-25 12:59 -0500
            Re: Collatz Problem proved. wij <wyniijj5@gmail.com> - 2026-01-26 04:10 +0800
              Re: Collatz Problem proved. Richard Damon <Richard@Damon-Family.org> - 2026-01-25 16:04 -0500
          Re: Collatz Problem proved. wij <wyniijj5@gmail.com> - 2026-02-06 14:19 +0800

csiph-web