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

Groups > comp.lang.c++ > #123179 > unrolled thread

Collatz Conjectur proved.

Back to article view | Back to comp.lang.c++

Contents

  Collatz Conjectur proved. wij <wyniijj5@gmail.com> - 2025-12-24 20:03 +0800
    Re: Collatz Conjectur proved. wij <wyniijj5@gmail.com> - 2026-01-25 00:46 +0800
      Re: Collatz Conjectur proved. wij <wyniijj5@gmail.com> - 2026-02-06 14:19 +0800
        Re: Collatz Conjectur proved. red floyd <no.spam.here@its.invalid> - 2026-02-06 15:29 -0800
    Re: Collatz Conjectur proved. Bonita Montero <Bonita.Montero@gmail.com> - 2026-02-06 14:22 +0100

#123179 — Collatz Conjectur proved.

 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).
-------------------------------------------------------------------------------

[toc] | [next] | [standalone]

#123326

On Wed, 2025-12-24 at 20:03 +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).
  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

[toc] | [prev] | [next] | [standalone]

#123446

The proof is revised (bug fixed), even shorter (109 lines)!

----------
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.

+---------+
| Preface |
+---------+
   3x+1 problem: For any integer n greater than or equal to 1, if n is odd,
   multiply by 3 and add 1. If n is even, divide by 2.
   The question is, will all numbers be calculated to 1 using this method? The
   following proof states that the answer is yes, they will always be calculated
   to 1. Proving this problem using Peano's axioms like axiomatic system is
   difficult (or would be very lengthy), so an algorithm (Turing machine model)
   is used for proof.

-----------------------------------------------------------------------------
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: For any n∈N<1,+1>, the cop iteration operation terminates.
  Proof: Let procedure rcop2 decomposes the n in rcop into n= a+b form.

        void rcop2(int n) {
          int a=n, b=0;
          for(;a+b!=1;) { // a+b measure point A (a+b is equivalent to n in the
                          // cop iteration process)
            if((a%2) != 0) {
              --a; ++b; // a,b are adjusted so that a remains even, so that the
                        // following algorithm can be performed and remains
                        // equivalent to the cop(n) iteration.
            }
            // a/b measures point B
            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)
            }
            a= a/2; // (a+b)/2 will be executed in each iteration
            b= b/2;
          }
        }

      Let n be odd and there be no --a, ++b process. Assume that each odd
      operation is paired with an even operation. Then, at measurement point B,
      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.
        Because "approximately half the limit value (n-1)/2" (not including the
        actual iterations which involve --a and ++b operations making aₓ smaller
        and bₓ larger) is recursively true, we can deduce that:
        (1) The actual value of aₓ/bₓ will decrease to the final value 0, and
            a=0, eventually.
        (2) The number of times bₓ is odd is less than the number of times bₓ is
            even (there are two, or more, consecutive even operations).

      Let r= a/b, aₓ=0. The value aₓ₋₁, before iterating to 0, is 1 (measurement
      point A). At this point, rₓ₋₁ is a small value, relative to the initial
      value r₁ (the value of aₓ/bₓ can be considered as decreasing continuously
      by (n-1)/2). When n>=5, bₓ₋₁ (=aₓ₋₁*rₓ₋₁ =rₓ₋₁) is guaranteed to be less
      than n-1. Therefore, nₓ₋₁= aₓ₋₁+bₓ₋₁ < 1+(n-1) <=> nₓ₋₁<n.

      From nₓ₋₁<n, we can prove by mathematical induction that the proposition
      "the iterative operation of cop(n) terminates" holds true.

+------------+
| References |
+------------+
 [1] Real number contains infinity. Recurring decimals are irrational numbers.
     Peano-Axioms system can hardly prove ∞∉ℕ.
     https://sourceforge.net/projects/cscall/files/MisFiles/RealNumber2-en.txt/download

[toc] | [prev] | [next] | [standalone]

#123451

On 2/5/2026 10:19 PM, wij wrote:
>[redacted]

So submit your paper to a peer reviewed publication, and collect your
Fields Medal.  Stop bothering us here.

[toc] | [prev] | [next] | [standalone]

#123448

The proof the mathematicians are looking for isn't a proof for certain
numbers but *one* proof for all numbers. So far no one has found this
proof.

Am 24.12.2025 um 13:03 schrieb wij:
>   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).
> -------------------------------------------------------------------------------
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web