December 8th, 2008, 04:51 AM  #1 
Senior Member Joined: Dec 2008 Posts: 206 Thanks: 0  Collatz Conjecture's solution
I(S.Kaushik) have a solution to this conjecture. The solution is stated below. Consider any number N for the sake of convenience we choose it to be an odd natural number. let this number N be the nth odd number then we do 3n+1/2 as per the formula the above operation increments the original number N by n (N and n are defined above). similarly if the new number(N new) obtained is odd we do the above operation else if it is even then we do N new/2 this is nothing but subtracting (n new), where (N new) is the (n new)th even number. We know that nth odd number  nth even number is 1!! . Thus if the above process is considered in terms of summation of n and subtraction of n news . We can see it for ourself that the end result is always 1!!! m. thus the conjecture is proved . I have just mentioned the outline of this proof for more details contact me at kaushiks.nitt@gmail.com 
December 8th, 2008, 05:10 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Collatz Conjecture's solution
Your proof is flawed. When dividing by 2, you are not subtracting the "(n new)th even number" and you are not subtracting it from the "nth odd number" (because you are at an even number, or you wouldn't be dividing by 2). Also, your proof implies (wrongly) that the only even numbers that are reached are 2. The mistake would have been easier to notice if you standardized your notation. 
December 9th, 2008, 04:37 AM  #3 
Senior Member Joined: Dec 2008 Posts: 206 Thanks: 0  Re: Collatz Conjecture's solution
I just gave a brief outline of the solution i will explain it properly in this reply. Consider any number N . According to the conjecture if N is odd then we do 3N+1/2 if it is even then we do N/2. Presently lets assume that N is odd and it is the nth odd number. For example 3(N) is the second(n) odd number and similarly 23(N) is the twelth(n) odd number and so on. Now as N is odd we do 3N+1/2 this is nothin but adding N to small n. thus the new number obtained after carrying out the operation is N+n. i.e. 3N+1/2 is N+n u can check this for any N. Similarly if N is even and it is the nth even number. For example 6(N) is the third(n) even number. Now as N is even we do N/2 this is nothin but subtracting n from N thus the new number obtained after carrying out the operation is Nn. i.e. N/2 is Nn for any N. We know that nth odd number  nth even number. Obvious. Now consider The following functions fodd(n) = Fodd(n1)+3. n is been described above and N =2n1. With fodd(1)=2. This is true as 1 is the first odd number and thus N+n =2(1+1). Example for n=5 i.e. N=9 it is the fifth odd number fodd(5)=Fodd(4)+3. This is a recursive function. As it was defined for odd number we define the same for even numbers also. Thus feven(n) = Feven(n1)+1. With feven(1)=1 .n is described above and N=2n;Check for any value . The initial values of Feven and fodd represent the value after the function defined by colltaz has been carried out on the number N. As N> infinity. n> infinity. We observe that feven(n)=n; and thus will include all numbers. Thus if after k iterations i.e. after applying the formula K times if the function is decreasing ,We can cnclude that the function is always decreasing. The proof is simple and can be proved by induction or any other standard technique. Thus the function defined by collatz decreases and hence it is convergent and it converges to 1. 
December 9th, 2008, 05:13 AM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Collatz Conjecture's solution Quote:
 
December 10th, 2008, 04:07 AM  #5 
Senior Member Joined: Dec 2008 Posts: 206 Thanks: 0  Re: Collatz Conjecture's solution
When i meant d initial values of feven and fodd i didn't mean it is 2 or 1. I meant tat when u consider any number N and try o apply collatz conjecture to it . Then wat u get is nothing but N+n (N is odd) or Nn (N is even) and N is the nth odd or even number respectively depending on your choice. Thus i meant that N+n can be described by fodd(n) and Nn can be described by feven(n). Similarly N+n(N is odd in this case use Nn if N was even) will become Nnew and u can find a corresponding nnew to this and apply the Fodd or feven function suitably based on wat Nnew turns out to be. The rest of d proof has been explained in the previous reply itself. Have a look through it and let me know if something is wrong. Thank you 
December 10th, 2008, 05:18 AM  #6  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Collatz Conjecture's solution Quote:
Remember, there are two possibilities you're trying to rule out: * A number n such that lim sup (n, C(n), C(C(n)), C(C(C(n))), ...) = +infty: an unbounded sequence. * A number n > 4 such that C(C(...C(n)...)) = n: a nontrivial loop.  
January 16th, 2009, 01:36 AM  #7 
Senior Member Joined: Dec 2008 Posts: 206 Thanks: 0  Re: Collatz Conjecture's solution
Collatz Conjecture is true for 1 (obvious) Induction: If the conjecture is true for all numbers between (1, N1) and if it is true for N Also then the conjecture is proved. The conjecture is stated as if F(n) = (3n+1)/2 for n= odd F(n) = n/2 for n= even Then recursively applying the formula to the new value of N we find tat after some z iterations the value of the function is 1. Note: • If the conjecture is true for N then it is true for 2N, 4N,… • Also if N = 2k p 1 ( any odd number can be expressed like this ) If k=1 then after 2 iterations we get N2 € ( 1, N1) i.e. N2 belongs to (1, N1) thus the conjecture is true. • If k=2 then the numbers N = 2k p 1 are of the form 4p1. Thus after two iterations we get an even number , and this number is divided by 2 as per the conjecture and N4 ( number after 4th iteration) is N+p; If p happens to be odd then N4 is even and N5 € ( 1, N1). Thus the conjecture is true in this case also. For even p no conclusion can be made. Remarks: From note 1 we know that if N1 is odd, then k is even and N/2 € (1, N1) thus the conjecture is true. Hence we need to consider the case where N1 is even. N is odd.. Odd numbers are either of the form 1+4(k1) or 3+4(k1). The numbers of the form 1+4(k1) are divisible only by 2 and not higher powers of 2 thus conjecture is true for these numbers. So now consider the odd numbers of the form 3+4(k1). In tat the numbers of the form 3+8(k1) are divisible only by 4 and not higher powers of 2 thus from note 3 we infer that if the number is of the form 3+16(k1) the conjecture is true.  B Also numbers of the form 11+12(k1) can be eliminated as these numbers can be obtained directly from an odd number € (1, N1).  A Example: to prove that the conjecture is true for 11 given tat the conjecture was proved for all numbers € ( 1, 10). We know tat applying the function to N=7 after 1 iteration results in 11. As the conjecture was proved for 7 it is true for 11 also !!! Thus the actual sequence under consideration was N?={3,7,11,15,19,23,27,31,35,…} If ? is divisible by 3 then the conjecture is true proved. Look A for proof. Also if ?= 1+4(x1) where x is any natural number the conjecture is true. Look Bfor proof. Thus we have a very few numbers for which we need to prove the conjecture is true!!. Now consider the generalized proof if N= 2k1 p 1. Then this number will become even after k iterations where 2k1 denotes the highest power of 2 that perfectly divides N+1. 2z1<p<2z The new number after k1iterations is Nk1= 3k1p 1. (even). Let 3k1p 1= 2k1 p1. Where 2k1 denotes the highest power of 2 that perfectly divides 3k1p 1.(Nnew). The new number after k1+k1 iterations is Nk1+k1=p1. ( Obvious!!) Then p1< max (2k1*1.6+zk1, 2k1*1.6+z1.2*k1+.6) – 1 This is because Nk12k1 < Nk1+k1 < Nk12k1+1 , and given N= 2k1 p 1. Then Ni = 3i * 2k1i *p 1 (i<k1) , and 3i < 21.6*i (for any i). Thus 1 is true. Now becomes our new odd number and p1= Nk1+k1 =2k2 p2 1. Again 2z11<p<2z1 . This Nk1+k1 will become even after k2 iterations from now and that will be Nk1+k2+k1 = 3k2p2 1. = 2k2 p3. This will be become odd after k2 iterations and the new number will be p3. Again this p3 is bounded as p1. This is obvious as we can consider p1 as the original number. Also it is trivial that the bound for p3 can be expressed in terms of k1,z and k2 and k1. If c= 1.6*k1+z. Then N?ki+ki (i runs from 1: m) < 2 c?ki + .6 *?ki+1 ( i runs from 1:m). One can also infer that we can find the bound for ki’s also. Thus the number reaches infinity only when m reaches infinity. Thus there is no way to disprove the conjecture. There doesn’t exists a trivial proof though as there doesn’t exists any relationship between ki’s and ki’s . Ki is at least 1(obvious) thus we can say tat after some Y iterations . The new number Becomes less than the original number. In fact this happens when ?ki +1 < 2( ?ki ). (i runs from 1:m). We can prove that the value’s of some ki’s >1. Using probabilistic approach (Tedious work !!!) . There also exists relation between ki and ki in some cases though. • Consider the original number if k1 is odd and p1 is divisible by 2i (i>1) then k1 is 1. • If k1 is even and p1 is divisible by 2i (i=1) then k1 is 1. • If k1 is odd and p1 is divisible by 2i (i=1) then k1 >= 2. • if k1 is odd and p1 is divisible by 2i (i>1) and k1 is divisible by 2i1 then k1 is min(i , i1+2). Thus the only way to disprove the theorem is to carry out infinite iterations but if we carry out infinite iterations we will encounter all numbers and thus 2?ki > ?ki+1. This is easy to check and the best part is the difference between sucessive numbers is one. So if we have all numbers the net result would be one. Thus the conjecture indeed approaches 1. Because when we do (3N+1)/2 we are incrementing the value by (N+1)/2 and in doing N/2 we are decrementing the value by N/2. I regard this as a solution to the conjecture. If u find something wrong then pls do tell me.. 
January 16th, 2009, 05:49 AM  #8  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Collatz Conjecture's solution Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
 
January 16th, 2009, 07:25 AM  #9 
Senior Member Joined: Dec 2008 Posts: 206 Thanks: 0  Re: Collatz Conjecture's solution
So do u mean to say that the proof is almost correct except for a few loop holes. I dont mind payin u for the repair job. But can u guaranty me that the proof would be accepted indeed.

January 16th, 2009, 07:27 AM  #10 
Senior Member Joined: Dec 2008 Posts: 206 Thanks: 0  Re: Collatz Conjecture's solution
What you mean is that the smallest counterexample to the Collatz conjecture, if such a number exists, cannot be of the form 4k+1. You have not shown that every sequence starting with a number of the form 4k+1 ends in the loop (1, 4, 2).


Tags 
collatz, conjecture, solution 
Search tags for this page 
collatz conjecture infinity disproved,collatz conjecture forum,i have the solution of collatz problem,aproaches to solution collatz conjecture,collatz conjecture solution,a suitable conjecture about the salary scale,colltaz conjecture,collatz conjecture,math forums collatz,math forum collatz,collatz conjecture sol,collatz conjecture proof by induction,collatz conjecture proof
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
an argument that the Collatz conjecture is false  dkcox  Number Theory  15  January 8th, 2014 05:20 AM 
Collatz conjecture & More (Please Help)  Aika  Number Theory  6  April 29th, 2012 06:34 AM 
Collatz conjecture, questions  xolruf  Number Theory  1  January 1st, 2012 08:11 AM 
Similar to Collatz Conjecture  8Pickle  Number Theory  6  September 7th, 2009 07:26 PM 
Question relating to Collatz conjecture  steiner1745  Number Theory  1  February 28th, 2007 08:09 PM 