Groups | Search | Server Info | Login | Register

Groups > comp.theory > #139479

Re: Collatz Problem proved.

Show all headers | View raw

On Sun, 2026-01-25 at 12:59 -0500, Richard Damon wrote:
> On 1/24/26 7:34 PM, wij wrote:
> > On Sat, 2026-01-24 at 18:19 -0500, Richard Damon wrote:
> > > On 1/24/26 4:32 PM, wij wrote:
> > > > 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:
> > > 
> > > 1.5 can't be the actual ratio and we reach convergence as that means we
> > > approximately do x3 /2 x3 /2 /2 -> x9/8 so the number continue to grow
> > > 
> > > We need to see a ratio > log2(3) ~ 1.585 to converge (which has happened
> > > on all numbers tested)
> > > 
> > > Also, you can't ignore the --a, ++b steps, as if we really have no
> > > double divide by two steps, every time b is even, so must have a been,
> > > and thus we move a count of a to b, and eventually a may go to 0,
> > > 
> > > > > > 
> > > > > >          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.
> > > 
> > > This is an UPPER limit ignoring the affects of the --a, ++b
> > > In actuality, a will be less, and b greater giving a smaller ration.
> > > 
> > > > > >            (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
> > > 
> > > So, we can reach a point where r = 0, and r+1 = 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
> > > 
> > > OR LESS. r can be as small as 0, thus b = m.
> > > 
> > > > > >          => b = (2*m)/(m+1) = 2/(1+1/m)
> > > 
> > > No, since r can be less, even 0, b can be = m.
> > > 
> > > > > >          => b = 2 (the limit of b. At least it is known that m will be a large
> > > > > >                    number)
> > > 
> > > Nope, this came from improper assumptions.
> > > 
> > > > > > 
> > > > > >          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.
> > > 
> > > But there isn't a limit
> > > 
> > > > > > 
> > > > > >          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).
> > > 
> > > You BEGAN with the assumption that it was cyclic, which need not hold.
> > > 
> > > > 
> > > > 1. The proof shows the the ratio a/b is decreasing
> > > 
> > > And can go down to 0, thus b can become all of m
> > 
> > The proof does not say so. You need to prove what you say.
> 
> The proof ignores the conditions that make it go there.
> 
> The --a and ++b WILL happen, and often
> 
> In fact, all we need to do is to notice that a will be smaller (and 
> progressive so) than you prediction and b larger to see that you "limit" 
> on a/b is actually an upper bound on that limit.
> 
> > 
> > > > 2. b has limit
> > > 
> > > No such proof. You ignored a factor that allows your r to decrease to 0,
> > > breaking the factor you needed.
> > 
> > What? Break what I need?
> 
> The fact that your calculation for the limit wasn't correct.
> 
> If r gets smaller than your predictions, b can get bigger than your 
> prodictions, as it MUST.
> 
> > 
> > > > 3. a must decrease to below b because of the above reason (a/b is decreasing
> > > >      and b has limit).
> > > 
> > > Yes, and a can become 0
> > > 
> > 
> > That is what you say. Prove it. (I know a will, but not in the proof)
> 
> No, I don't need to prove it, just show that your calculations are based 
> on errors.
> 
> Your estimates for a are too high, and your estimates for b are too low, 
> and thus the rest of your proof just doesn't have anything to stand on.
> 
> > 
> > > > 4. Done, n=a+b has limit (cop(n) is known to terminate for values less than
> > > >      2^16 at least).
> > > 
> > > But by the time a gets down there, b has grown larger than that. The
> > > problem is that if a/b grows very small the ratio of b/a grows very
> > > large, and thus your logic doesn't work.
> > 
> > Can you read English? I started to doubt.
> 
> 
> Your results says b will end up being 2 as a limit, which just shows 
> something must be wrong, and fails the sniff test.
> 
> It starts out with the series
> 
> b0 = 1
> b1 = 3 because (3*1+1)/2 = 2, which means that since we assume only one 
> divide by two, that a is now odd, so we do --a and ++b
> b2 = 5 (3*3+1)/2
> b3 = 9 (3*5+1)/2 ++
> b4 = 15
> 
> B will NEVER go down if we are on a path with only 1 divide by two, or 
> even if we average 1.5 divides by two (that makes it grow by AT LEAST 
> 9/8 per step).
> 
> Thus, we see that you assumptions on a and b are incorrect, and your 
> results are just incorrect.

Sorry, your response does not seem to be reasonable (I cannot figure out
what you are really referring to).
But, thanks for suggestions.

> > 
> > > > 
> > > > 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.
> > > 
> > > It defies YOUR logic as you made assuptions that don't hold, which
> > > breaks your assumption of a limit of b compared to a.

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