Groups | Search | Server Info | Login | Register

Groups > comp.theory > #139396

Collatz Problem proved.

Show all headers | View raw

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.theory | Previous | Next — 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