My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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
kaushiks.nitt is offline  
 
December 8th, 2008, 06:10 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
kaushiks.nitt is offline  
December 9th, 2008, 06:13 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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
kaushiks.nitt is offline  
December 10th, 2008, 06:18 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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-1<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+z-k1, 2k1*1.6+z-1.2*k1+.6) – 1
This is because Nk1-2k1 < Nk1+k1 < Nk1-2k1+1
, and given N= 2k1 p -1. Then Ni = 3i * 2k1-i *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 2z1-1<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 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..
kaushiks.nitt is offline  
January 16th, 2009, 06:49 AM   #8
Global Moderator
 
CRGreathouse's Avatar
 
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<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+z-k1, 2k1*1.6+z-1.2*k1+.6) – 1
This is because Nk1-2k1 < Nk1+k1 < Nk1-2k1+1
, and given N= 2k1 p -1. Then Ni = 3i * 2k1-i *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 2z1-1<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.
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).
CRGreathouse is offline  
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.
kaushiks.nitt is offline  
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).
kaushiks.nitt is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
collatz, conjecture, solution



Search tags for this page
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 06:20 AM
Collatz conjecture & More (Please Help) Aika Number Theory 6 April 29th, 2012 07:34 AM
Collatz conjecture, questions xolruf Number Theory 1 January 1st, 2012 09:11 AM
Similar to Collatz Conjecture 8Pickle Number Theory 6 September 7th, 2009 08:26 PM
Question relating to Collatz conjecture steiner1745 Number Theory 1 February 28th, 2007 09:09 PM





Copyright © 2018 My Math Forum. All rights reserved.