My Math Forum Collatz Conjecture's solution
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 December 8th, 2008, 05: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, 06: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, 05: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 N-n. i.e. N/2 is N-n for any N. We know that nth odd number - nth even number. Obvious. Now consider The following functions fodd(n) = Fodd(n-1)+3. n is been described above and N =2n-1. 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(n-1)+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, 06: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:
 Originally Posted by kaushiks.nitt The initial values of Feven and fodd represent the value after the function defined by colltaz has been carried out on the number N.
This is the claim you fail to support, without which your proof has no relation to the Collatz conjecture. Your functions are trivial: fodd(n) = 3n-1, feven(n) = n.

 December 10th, 2008, 05: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 N-n (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 N-n can be described by feven(n). Similarly N+n(N is odd in this case use N-n 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, 06: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:
 Originally Posted by kaushiks.nitt Have a look through it and let me know if something is wrong.
Yes, you still haven't explained what relation fodd and feven have to the Collatz function, though you've claimed the relationship twice. How about some examples?

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, 02: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, N-1) 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, N-1) i.e. N2 belongs to (1, N-1) thus the conjecture is true. • If k=2 then the numbers N = 2k p -1 are of the form 4p-1. 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, N-1). 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 N-1 is odd, then k is even and N/2 € (1, N-1) thus the conjecture is true. Hence we need to consider the case where N-1 is even. N is odd.. Odd numbers are either of the form 1+4(k-1) or 3+4(k-1). The numbers of the form 1+4(k-1) 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(k-1). In tat the numbers of the form 3+8(k-1) 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(k-1) the conjecture is true. - B Also numbers of the form 11+12(k-1) can be eliminated as these numbers can be obtained directly from an odd number € (1, N-1). - 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(x-1) 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. 2z-11. 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 p-1 is divisible by 2i (i>1) then k1 is 1. • If k1 is even and p-1 is divisible by 2i (i=1) then k1 is 1. • If k1 is odd and p-1 is divisible by 2i (i=1) then k1 >= 2. • if k1 is odd and p-1 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, 06: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:
 Originally Posted by kaushiks.nitt The numbers of the form 1+4(k-1) are divisible only by 2 and not higher powers of 2 thus conjecture is true for these numbers.
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).

Quote:
 Originally Posted by kaushiks.nitt So now consider the odd numbers of the form 3+4(k-1). In tat the numbers of the form 3+8(k-1) 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(k-1) the conjecture is true. - B
Wrong. You haven't shown anything about numbers of the form 8k+3. F(F(F(8k+3))) = 9k+4 > 8k+3.

Quote:
 Originally Posted by kaushiks.nitt 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. 2z-1
I can't follow this part of your post because the notation is nonstandard.

Quote:
 Originally Posted by kaushiks.nitt 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. [...] We can prove that the value’s of some ki’s >1. Using probabilistic approach (Tedious work !!!) .
If you think you're going to prove the Collatz conjecture, you can't just skip steps like these.

Quote:
 Originally Posted by kaushiks.nitt 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 makes no sense.

Quote:
 Originally Posted by kaushiks.nitt 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.
Using the geometric mean rather than the arithmetic mean would make more sense, and would give a strong *heuristic* that the Collatz conjecture is true.

Quote:
 Originally Posted by kaushiks.nitt I regard this as a solution to the conjecture. If u find something wrong then pls do tell me..
It has holes in many places, as I pointed out above. If you'd like help with repairing the proof, I bill at \$30 / hour. If you pay for 10 hours upfront I'll sign a nondisclosure agreement. I can even draft one for you -- but I'll charge for the time it takes to write one for you (about 30 minutes to customize my existing boilerplate).

 January 16th, 2009, 08: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, 08: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

,
,
,
,
,
,

,

,

,

,

,

,

# collatz conjecture proof

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post dkcox Number Theory 15 January 8th, 2014 06:20 AM Aika Number Theory 6 April 29th, 2012 07:34 AM xolruf Number Theory 1 January 1st, 2012 09:11 AM 8Pickle Number Theory 6 September 7th, 2009 08:26 PM steiner1745 Number Theory 1 February 28th, 2007 09:09 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top