Facebook
Google
GitHub
Linkedin
Well technically this problem does not actually halt, it just loops indefinitely. I am not sure though if we can consider that halting but you could look at other problems to see if any of those that were classified as halting actually just got stuck in a continuous loop or repetition of some kind.
The 3N+1 Conjecture, Simple Problem, Tough Proof
- Thread starter MrAl
- Start date
I've been playing with a variation of this conjecture. If you replace 3n+1 with 3n-1 you can end up with several different loops.
For example,
n=5 gives the loop 5,14,7,20,10,5.
N=17 gives the loop 17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34,17.
It seems new loops occur when n=1+ a power of 2 (the power being >2).
For example,
n=5 gives the loop 5,14,7,20,10,5.
N=17 gives the loop 17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34,17.
It seems new loops occur when n=1+ a power of 2 (the power being >2).
Last edited:
That's an interesting one too. There seems to be a lot of functions like this but most of them (maybe all of them) dont end in the same loop all the time like the 3n+1 problem does. That might be what sets it apart.
I thought about this a little more and i am thinking now that this is just one of those things that we just have to "accept" as true without mathematical proof. This may seem strange, but we have accepted many things without mathematical proof in our life times without realizing it. For example, can inertia really be proven mathematically? We had the 'definition' for years but never any proof or why it actually works that way. There are again conjectures but i dont think there is any real proof.
Then there is quantum mechanics. We have both entanglement and non locality, both have been proven to be true through experiment (as was inertia) so they are not magic anymore but there seems to be no real explanation as to why these things happen the way they do as they break classical mechanics and before that classical mechanics was all we had.
So what do we do about these things? Well with inertia we did not prove it mathematically but we use the math behind it very easily, so we went from accepting it to using it to calculate other things that are a consequence of the way things move when not acted on by any outside forces. So we do the same thing with quantum mechanics. We know how tiny particles behave (even though we dont really know why) and so we can use that knowledge to advance technology and come up with some fascinating new things ... all without knowing the true cause of any of it (see footnote [1] below).
Perhaps with problems like this 3n+1 thing we need to do the same thing. It seems different, but after all we did experiments up to a very large number and came up with the same results: the same loop each time. So maybe we just need to accept that ANY number will lead to that same conclusion and therefore apply it as if it were true even though we dont yet have a specific proof or explanation of why it happens. For most practical purposes it will always work, so if in the future we find a worthy technological application for this we can use it to advance that particular technology, all without any rigorous proof.
[1] Do a search for new technologies brought about though the study and use of quantum mechanics. One out of the many are sensors that can detect incredibly small things and have incredibly high resolution unlike anything ever before it and probably never dreamed of before QM's. Things like this are going to change the future world drastically. I believe that we are now sitting very close to a pinnacle in technology brought about by new ideas based on QM's that will change things like never before. The ramifications will be even more extreme than Einstein's relativity because they will be so useful to humanity.
Then there is quantum mechanics. We have both entanglement and non locality, both have been proven to be true through experiment (as was inertia) so they are not magic anymore but there seems to be no real explanation as to why these things happen the way they do as they break classical mechanics and before that classical mechanics was all we had.
So what do we do about these things? Well with inertia we did not prove it mathematically but we use the math behind it very easily, so we went from accepting it to using it to calculate other things that are a consequence of the way things move when not acted on by any outside forces. So we do the same thing with quantum mechanics. We know how tiny particles behave (even though we dont really know why) and so we can use that knowledge to advance technology and come up with some fascinating new things ... all without knowing the true cause of any of it (see footnote [1] below).
Perhaps with problems like this 3n+1 thing we need to do the same thing. It seems different, but after all we did experiments up to a very large number and came up with the same results: the same loop each time. So maybe we just need to accept that ANY number will lead to that same conclusion and therefore apply it as if it were true even though we dont yet have a specific proof or explanation of why it happens. For most practical purposes it will always work, so if in the future we find a worthy technological application for this we can use it to advance that particular technology, all without any rigorous proof.
[1] Do a search for new technologies brought about though the study and use of quantum mechanics. One out of the many are sensors that can detect incredibly small things and have incredibly high resolution unlike anything ever before it and probably never dreamed of before QM's. Things like this are going to change the future world drastically. I believe that we are now sitting very close to a pinnacle in technology brought about by new ideas based on QM's that will change things like never before. The ramifications will be even more extreme than Einstein's relativity because they will be so useful to humanity.
Last edited:
dcbingaman
- Joined Jun 30, 2021
- 1,065
The proof could be restated as eventually you will always get a number that happens to be 2^k. Obviously this reduces to one due to division by two. So we could restate the proof as: You will always eventually run across a number that happens to be 2^k. As soon as this happens, regardless of the value of k. The game is over.
We could take that to the next step: some number will eventually arrive such that 3 times it plus one will give you a 2^k number. Or:
3n+1=2^k
n=(2^k-1)/3 must be the previous number. I have no idea where I am going with this one.
This even number can never be 2^1. The smallest number you can get with 3n+1 is 4. So the proof can be refined a little as you will always eventually get a number that is 2^k and k cannot be 1 but must at least be 2 minimum. You can take this one step further:
2^k-1 must be divisible by 3, this is only possible if k happens to be an even number of 2 or greater.
So prove that any number will eventually arrive a 2^k where k must be greater than 1 and must be an even number.
This being the case we can replace the equation with 3n+1=2*2^k where k must be an odd number one or greater.
or
(3n+1)/2=2^k where k must be an odd number one or greater.
Let k=1 then 2^k=2 and 3n+1=4 when n=1
Let k=3 then 2^k=8 and 3n+1=16 and n is thus 5
let k=5 then 2^k=32 and 3n+1=64 and n is thus 21
let k=7 then 2^k=128 and 3n+1=256 and n is thus 85
sequence:
2, 8, 32, 128 ----> 2, (2*4), (8*4), (32*4), ---> The sequence is nothing more than start at 2 and multiply the previous number by 4 creating the next number and so on....
We could take that to the next step: some number will eventually arrive such that 3 times it plus one will give you a 2^k number. Or:
3n+1=2^k
n=(2^k-1)/3 must be the previous number. I have no idea where I am going with this one.
This even number can never be 2^1. The smallest number you can get with 3n+1 is 4. So the proof can be refined a little as you will always eventually get a number that is 2^k and k cannot be 1 but must at least be 2 minimum. You can take this one step further:
2^k-1 must be divisible by 3, this is only possible if k happens to be an even number of 2 or greater.
So prove that any number will eventually arrive a 2^k where k must be greater than 1 and must be an even number.
This being the case we can replace the equation with 3n+1=2*2^k where k must be an odd number one or greater.
or
(3n+1)/2=2^k where k must be an odd number one or greater.
Let k=1 then 2^k=2 and 3n+1=4 when n=1
Let k=3 then 2^k=8 and 3n+1=16 and n is thus 5
let k=5 then 2^k=32 and 3n+1=64 and n is thus 21
let k=7 then 2^k=128 and 3n+1=256 and n is thus 85
sequence:
2, 8, 32, 128 ----> 2, (2*4), (8*4), (32*4), ---> The sequence is nothing more than start at 2 and multiply the previous number by 4 creating the next number and so on....
Last edited:
