The 3N+1 Conjecture, Simple Problem, Tough Proof

Thread Starter

MrAl

Joined Jun 17, 2014
11,345
Hello there,

Some of you may have heard of this by another name as there are several people associated with the long history of this problem. For those that never heard of this i will give a short introduction.

There are some simple rules to this problem as follows:
1. Pick a number from 1 to any number and it must be a whole number like 1,2,3, 21,56, etc.
2. If the number is even, divide by 2.
3. If the number is odd, multiply by 3 and add 1 (hence the general name of this problem).
4. After you get a result, repeat steps 2 and 3 using the result from either step 2 or step 3.

First i will give an example of a "loop".
Start with 1. It is odd, so 1*3+1=4.
Now 4 is even, so divide by 2 to get 2.
Now 2 is even, so divide by 2 to get 1.
We started with 1 and got 1 as a result, so if we keep going we will just repeat the 1,2,4 sequence.
That is what is known as a loop. Once we hit a loop we are done because it will just keep repeating.

Now for a slightly bigger example but still fairly short.
Start with 26, it's even so divide by 2 getting 13.
That's odd so 13*3+1=40
That's even so 40/2=20, then 20/2=10, then 10/2=5.
That's odd so 5*3+1=16.
That's even so 16/2=8, then
8/2=4, then 4/2=2, then 2/2=1, then 1*3+1=4
so we hit the 1,2,4 loop i outlined above so we are done working with the number 26.

Now for the conjecture...
"No matter what number you start with (step 1) you always end up with the 1,2,4 loop".

It's still just a conjecture because it has not been proven or unproven to date.
If you want to play around with this and see if you can prove or disprove it, be forewarned it has been proven true up to the number 2^68 so you'd have to start there if you wanted to use trial and error as has been done getting to that number.
Good luck if you do.

I thought this was interesting because it's such a simple problem but possibly not possible to prove or disprove.
As a side note, there is a scientist that is somewhat casually trying to show that the universe evolves from simple functions like this not from elementary particles. What is amazing about this function is it could generate huge structures before finally settling to that 1,2,4 sequence. if you pick a larger number something above 6000 you can get a wild variation, but even with smaller numbers like 27 you get 111 results before it settles to the 1,2,4 sequence which is still kind of lengthy.

Try it out it's kind of cool :)
 
Last edited:

Delta Prime

Joined Nov 15, 2019
1,311
Try it out it's kind of cool
When n =1we have n 3 + 5n = 6 which is obviously divisible by 6.
By inductive hypothesis, it remains to prove that 3n(n + 1) is divisible by 6. But this is easy as there must be an even number between two consecutive natural numbers,so 2 divides n(n+ 1), which implies 6 divides 3n(n + 1).
I just proved & disproved it at the same time & I cannot be proven wrong or right. ;)
(Edit: therefore I have you in between a rock and a smiley face with a tongue sticking out) :p
Never discussed Infinity with a mathematician or else you will never hear their end of it!
 
Last edited:

Thread Starter

MrAl

Joined Jun 17, 2014
11,345
When n =1we have n 3 + 5n = 6 which is obviously divisible by 6.
By inductive hypothesis, it remains to prove that 3n(n + 1) is divisible by 6. But this is easy as there must be an even number between two consecutive natural numbers,so 2 divides n(n+ 1), which implies 6 divides 3n(n + 1).
I just proved & disproved it at the same time & I cannot be proven wrong or right. ;)
(Edit: therefore I have you in between a rock and a smiley face with a tongue sticking out) :p
Never discussed Infinity with a mathematician or else you will never hear their end of it!
What the heck are you talking about?
You are going to have to be a little more clear if you want to show some proof or something. You can not do anything other than n/2 or 3*n+1 in any one step. But if you still have something to say about it you will have to elaborate and do so in a clear and concise way, but know that i am not the determiner of all proofs or disproofs either so you dont have to convince me of anything you have to convince a bunch of mathematicians throughout the history of this problem and i welcome you to try to do so if you desire.
So what that means is if you did come up with a proof or anti proof or any combination of that or really anything else under the sun i am not the guy to talk to because i may not be able to go over your proof anyway. I was really just presenting the problem for others to take a look at and see what they think.

Personally i did think it was kind of interesting that we keep getting back to the 1,2,4 sequence though and that the number we choose to start with results in either a short sequence before we get stuck in that loop or a very very long sequence before that. The way one guy put it was kind of funny... "No matter how much or what stock i invest in, it always ends up that my investment always turns into 1, 2, or 4 dollars" (ha ha).
 
Last edited:

Delta Prime

Joined Nov 15, 2019
1,311
The way one guy put it was kind of funny... "No matter how much or what stock i invest in, it always ends up that my investment always turns into 1, 2, or 4 dollars" (ha ha).
I agree & I surrender ,at the same time volunteer for mutiny. It's a conjecture. My explanation stands!
 

ApacheKid

Joined Jan 12, 2015
1,508
This should be enough to bring you to your senses:

Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."[8]

If he felt that way, then it is a very very serious problem indeed!
 

Thread Starter

MrAl

Joined Jun 17, 2014
11,345
I agree & I surrender ,at the same time volunteer for mutiny. It's a conjecture. My explanation stands!
"My explanation stands"

I just wanted to see you elaborate a little it doesnt make sense yet. I am sure it does to you, but you should explain what you are doing and trying to do so i know what your strategy was.
 

Deleted member 115935

Joined Dec 31, 1969
0
I thought the answer was 42 anyway ....

i.e. way beyond my maths this ....
 

ApacheKid

Joined Jan 12, 2015
1,508
I guess people have already tried a proof-by-contradiction and that led nowhere.

I have no idea what a proof would even look like, recall that the infamous four color problem now has a proof but it was not a purely mathematical proof, it inherently relied on a computer as part of the proof...
 

Thread Starter

MrAl

Joined Jun 17, 2014
11,345
I guess people have already tried a proof-by-contradiction and that led nowhere.

I have no idea what a proof would even look like, recall that the infamous four color problem now has a proof but it was not a purely mathematical proof, it inherently relied on a computer as part of the proof...
So far the only 'proof' or lack thereof is in the form of trial and error where we just keep trying more and more numbers, 1,2,3,4,5,...,1000,1001,1002,...,1000001,100002,.., etc., until we find one that does not end in the 1,2,4 loop. However, it is thought that since no disproof was found up to the number 2^68 that the proof or disproof would not come like that it would come in the form of some kind of logical reasoning which most likely also involves a little math.

It could also be that this may be one of those problems that can not be proved or disproved.
 

Delta Prime

Joined Nov 15, 2019
1,311
If "n"is a odd multiply"n by 3"& add 1 to it & find 3n +1.Repeat the process (which has been called Half of Triple
Plus One or HTPO)indefinitely.
The conjecture puts forth the following hypothesis.Whatever positive number one starts with
one will always eventually reach 1 after a finite number of steps.
Old school hypothesis have little meaning to one who's just graduated from high school! Meaning I stand on the shoulders of giants! Isn't that the purpose of life!The conveyance of knowledge to see what no one else has seen but given the information I could not have attained without their magnificent insight! For the old school that's a rhetorical question. & I do not wish to die in order for everyone else to find out I am ahead of my time. Because more than likely I'll be the butt of the joke.
To put a smile on your face it's all I'm here for! :)(edit) I dropped out of high School 30 years ago! :p
Give or take 30 years!
 
Last edited:

Delta Prime

Joined Nov 15, 2019
1,311
you dont have to convince me of anything you have to convince a bunch of mathematicians throughout the history of this problem and i welcome you to try to do so if you desire
:)
Thank you!I am not trying to convince you.I'm trying to convince the mathematicians throughout history of this problem.But the only way to do so... Is to join them.Then again what is a lifetime compared to eternity?
 

Thread Starter

MrAl

Joined Jun 17, 2014
11,345
In which case it would have to be true, we just couldn't prove it!
Yeah i think that is the consensus, that it is true but we cant prove or disprove it yet.

Just one example that does not work would disprove it but finding that example is too hard to do. What we need is some logic that tests every number in one or two or a smallish set of statements.
I have to wonder if they tried automated reasoning on this problem yet.

I have also seen something like this work with other simpler functions too. For example, if you start with any positive number i think from anything over 0 (including fractions like 0.3) and keep taking the square root you end up with 1 every time. In fact, even if we take the square root of any non zero negative number i think we still end up with 1 because the imaginary part tends to zero as we go and the real part tends to 1.
Something like that is probably easier to prove or disprove because we can see a limit happening with each step, but with the 3n+1 problem the different numbers may create a short sequence or an incredibly long sequence with a lot of ups and downs. I think someone may have proved that the ups and downs are limited in scope but still did not prove that we get to the loop for every number. There must be stuff written about this on the web might be interesting to look around a little.

There are a lot of other simple functions that generate a lot of interesting things too like fractals. Maybe this is just one type of fractal that happens to end rather than keep getting more and more detailed.

You know what else would be interesting, to have a sort of contest to see who could find the longest sequence. From what i understand there are some numbers that generate a very very large sequence. I am going to see if i can find one with a really long sequence.
It is interesting that the number 1250 generates a sequence of just 27 numbers, but the number 27 generates a sequence of 111 numbers.

I did find a sequence of length 688 using the number 11200681 which of course is over 10 million.
That is the longest or at least one of the longest sequences up to about 12 million i think but this needs to be verified because i am not using large integers to do all the calculations.
So to get really really long sequences are have to go up pretty high with the starting number.
 
Last edited:

Thread Starter

MrAl

Joined Jun 17, 2014
11,345
If you want to create any specific length, it is easy. 2^n produces a sequence of of length n.

Bob
Ha ha, yes, very observant of you.

What i wanted to do mainly was look for long sequences and count the number of sequences that have the same number of steps, within given ranges like 10 million, 100 million, etc., but see i think there may be and probably is longer sequences in the range of 2^n than you get with just 2^n. For example:
2^32 would have 32 steps but 2^32=4294967296 which is way higher than 12 million and as i mentioned i found a sequence 688 steps long within that range (1 to 12000000 that is).
Still interesting though.
 

ApacheKid

Joined Jan 12, 2015
1,508
All computable functions can be represented as a Turing machine or a program that a Turing machine can run. I'm not too sure but the Collatz conjecture seems to be unprovable because its about a Turing machine halting and there's no algorithm for deciding if a program will eventually halt or not.
 
Top