Author |
Topic: Unsolved: 3x+1 Sequence Conundrum (Read 7488 times) |
|
Sameer
Uberpuzzler
Pie = pi * e
Gender: 
Posts: 1261
|
 |
Unsolved: 3x+1 Sequence Conundrum
« on: Nov 25th, 2006, 10:59pm » |
 Quote  Modify
|
I read tihs in a book and thought it would be interesting to bring it up. Sorry if it is already out there. This puzzle belongs to unsolved category.
Begin with an arbitrary positive integer.
Repeat the following: If number is even, halve it; if odd, triple it and add 1.
Prove that you will eventually cycle in the sequence 1, 4, 2, 1, 4, 2 ...
E.g.
Consider number 9.
since it is odd I will triple it 27 and add 1 making it 30.
Since it is even, I will half it 15. Continuing, I will get
46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1....
|
|
 IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #1 on: Nov 25th, 2006, 11:24pm » |
Quote Modify
|
This conjecture is called Collatz conjecture. Erdos seems to have said that "Mathematics is not yet ready for such problems". (Hehehe)
This was definitely discussed in wu forums. I am not however able to get any results on either searching for "collatz" or "3n+1". 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #3 on: Nov 26th, 2006, 3:36am » |
Quote Modify
|
First of all, we know that when we reach 1, we're in the cycle. Thus, I don't care that much about the cycle.
Define the function to as the function that assigns 3n+1 to odd n, and n/2 to even n, and totime as the function that measures how many iterations it takes to reach 1.
Assume we have a set S with all the n € N with totime[n] not€ N. Then, we have three choices. to[n] makes a loop with n in it, a loop without n, or just go to infinity
We will look at the smallest n.
Assume n is even. Then, n/2 is also an element of n. Because it's the next step of to, this one must also be in S, thus we do not have the smallest element yet.
Thus, n is odd. This would speed up computerbased checking by a factor two. n = 2m+1
3n+1 is even. But how about 1.5n+.5? 3n+1 = 6m+3+1 = 6m+4 = 2(3m+2). So 1.5n+.5 = 3m+2
Thus to[to[2m+1]] = 3m+2 = 2m+1 + m+1.
For to[3m+2] to be larger than 2m+1, 3m+2 needs to be odd, thus 3m needs to be odd, thus m is odd... 3m+2 = 2k+1, to[to[2k+1]] = 3k+2, so to[to[to[to[2m+1]]]] = 3k+2 = 3m+2 + k+1 = 3m+3+k. If k is even, this is even, if k is odd, this is odd.
If this is even, then 1.5m+1.5+k must be larger than 2m+1. thus, k > .5m - .5
If this is odd, I don't care about the value 
I hoped to get into an argument where I would have proven that to[....to[n]]] < n, which can not be true because n is the smallest that cycles to infinity. But, logically, I couldn't reach that.
|
|
IP Logged |
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #4 on: Dec 24th, 2006, 11:26am » |
Quote Modify
|
Just off the top of my head it seems like this could be divided into cases as follows:
Let N be the smallest number greater than 1 which fails to converge to 1.
Let the numbers that follow N be called the successors of N.
Let the numbers that precede N be called the predecessors of N.
If N is the smallest such number then every successor of N must be >= N.
If N is the smallest such number then every predecessor of N must be >= N, otherwise N can be reached from a number smaller than N.
If N is the smallest such number then every predecessor of every successor of N must be >= N, otherwise some successor of N can be reached, without passing through N, from a number smaller than N.
If N = 2k is even then the immediate successor of N is N/2 which is smaller than N. Therefore N must be odd.
If N is of the form N = 3k+1 then one immediate predecessor of N was k which is smaller than N.
If N is of the form N = 3k+2 then one immediate predecessor of N was 2N = 6k+4, and one immediate predecessor of that predecessor was (6k+4-1)/3 = 2k+1. Since N = 3k+2, N > 2k+1 and N is not the smallest such number.
Therefore if N exists it must be of the form 3k.
The form 3k can be divided into 2 cases where k is of the forms k = 4q+1, and k = 4q+3.
The remaining possible forms are thus: {12k+3, 12k+9} (The form 12k+6 can be ignored since it is also of the form 2k.)
If N is of the form 12k+3 then its successors are: 3(12k+3)+1 = 36k+4; 18k+2; 9k+1 < N = 12k+3.
Therefore N, if it exists, must be of the form 12k+9.
I've only gone a few more levels, but it seems as if by enumerating successors AND predecessors AND predecessors of successors it can be demonstrated by induction that N, if it exists, must be of the form Ak+C where A can be shown to increase without bounds as the recursion goes deeper. Thus the conditions for the existence of N become more and more stringent with each iteration and thus the conditions for the existence of N cannot be satisfied by any finite form. Therefore N is not finite. Therefore the conjecture is true for all finite N.
That's informal, of course, but I don't see why it can't be formalized once it is formally established in what manner A increases without bounds with each iteration.
On Edit: "Each iteration" refers to each iteration of the proof process, not each iteration of the {N/2; 3N+1} process, so technically, the proof is infinitely long, but it can be shown that the proof is constructible in an infinite but countable number of steps.
|
| « Last Edit: Dec 24th, 2006, 12:42pm by fiziwig » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #5 on: Dec 24th, 2006, 5:30pm » |
Quote Modify
|
on Dec 24th, 2006, 11:26am, fiziwig wrote:Let the numbers that precede N be called the predecessors of N.
...
If N is the smallest such number then every predecessor of N must be >= N, otherwise N can be reached from a number smaller than N. |
|
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #6 on: Dec 24th, 2006, 9:51pm » |
Quote Modify
|
I'm not sure I understand your
But if we require that N be the smallest in the series and some number K<N such that K -> L -> M -> N then K is a predecessor of N and is smaller than N which contradicts our original requirement that N be the smallest number that does not ultimately lead to 1, since we have found a smaller number, K, which also does not lead to 1. If the assumption can be shown to lead to a contradiction then the assumption cannot be true and there is no smallest number which fails to converge to 1.
|
|
IP Logged |
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #7 on: Dec 25th, 2006, 12:15am » |
Quote Modify
|
On Edit: Stop the presses. There's a problem with the 12x+1 case and the 12x+7 case. I need to iron out that problem before it's actually correct.
--gary
The proof is actually simpler than I originally thought.
Let N be the smallest number that does not converge to 1.
N must be of one of the forms: 12x, 12x+1, 12x+2, 12x+3, ... 12x+11. Those 12 forms account for every possible value of N.
The even forms 12x, 12x+2, 12x+4, 12x+6, 12x+8, 12x+10 are all followed by N/2 which is smaller than N, thus contradicting the assertion that an even N is the smallest such number. Therefore N, if it exists, must be odd.
If N is of the form 12x+1 then the immediate predecessor of N is (N-1)/3 = 4x, which is smaller than N contradicting the assertion because 4x also does not lead to 1 yet is smaller than the claimed smallest value.
If N is of the form 12x+3 then its successors are: 3(12x+3)+1 = 36x+4; 18x+2; 9x+1 which is less than N which contradicts the assertion.
If N is of the form 12x+5 then one immediate predecessor of N is 2N = 24x+10, and one immediate predecessor of that predecessor is (24x+10-1)/3 = 8x+3 which is less than N contradicting the assertion because if N does not converge to 1 then 8x+3 which is less than N also does not converge to 1.
If N is of the form 12x+7 then the immediate predecessor of N is (12x+7-1)/3 = 4x+2 which is less than N contradicting the assertion.
If N is of the form 12x+9 then the successors of N are 12x+9 -> 3(12x+9)+1 = 36x+28 -> 18x+14 -> 9x+7 which is less than N contradicting the assertion.
If N is of the form 12x+11 then then one immediate predecessor of N was 2N = 24x+22, and one immediate predecessor of that predecessor was (24x+22-1)/3 = 8x+7 which also does not lead to 1 and is smaller than N which contradicts the assertion.
Thus we have shown that whenever we assert that there exists an N which is the smallest number that does not eventually lead to 1 we can, for every possible form of N, arrive at a contradiction to the assertion that there is a smallest number N by showing that there must always be one more number which is smaller. (And one more after that that is smaller still, etc.) Therefore the assertion that a smallest N exists which fails to converge to 1 is false. Therefore the conjecture is proven. QED
--gary shannon
|
| « Last Edit: Dec 25th, 2006, 12:46am by fiziwig » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #8 on: Dec 25th, 2006, 1:37am » |
Quote Modify
|
In the case 12x+3, you incorrectly expanded 3(12x+3)+1. This should equal
36x+10->
18x+5->
54x+16->
27x+8->
something depending on the parity of x.
I haven't read over the rest. I don't mean to discourage you, but it is extremely improbable that there is a "simple" solution to this problem. I imagine a solution to this problem could easily be worthy of a PhD in math at any university.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #9 on: Dec 25th, 2006, 6:04am » |
Quote Modify
|
Okay - I understand now what you were saying that had me confused. But you have another problem, that you've made repeatedly. Here is one example:
on Dec 25th, 2006, 12:15am, fiziwig wrote:| If N is of the form 12x+1 then the immediate predecessor of N is (N-1)/3 = 4x, which is smaller than N contradicting the assertion because 4x also does not lead to 1 yet is smaller than the claimed smallest value. |
|
Because 4x is even, it successor is 2x, not 12x+1 = N. I.e., it is not the immediate predecessor of N. In fact, any number of the form 12x+1 has no predecessor. The only sequence it occurs in is the one it originates. The same can be said of other numbers.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #10 on: Dec 25th, 2006, 8:41am » |
Quote Modify
|
Yes, I figured out that the 4x was a real problem. I clearly jumped the gun and should have spent a bit longer combing through my "proof".
Oh well. Back to the drawing board.
As for finding a simple proof, there's always the chance (admittedly VERY slim) that everyone has managed to overlook something simple but not immediately obvious. Hope springs eternal...
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #11 on: Jan 28th, 2007, 12:14pm » |
Quote Modify
|
on Dec 25th, 2006, 6:04am, Icarus wrote:| In fact, any number of the form 12x+1 has no predecessor. The only sequence it occurs in is the one it originates. The same can be said of other numbers. |
|
How about 24x+2 
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #12 on: Jan 28th, 2007, 1:23pm » |
Quote Modify
|
Didn't anyone tell you you are supposed to just accept what I say, and not go off and see if it's true or not?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
...by xkcd
|
| « Last Edit: May 9th, 2011, 4:43pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
swt
Newbie
Gender:
Posts: 1
|
|
Re: Unsolved: 3x+1 Sequence Conundrum
« Reply #15 on: Aug 10th, 2011, 7:56am » |
Quote Modify
|
Collatz conjecture has not been proven yet as indicated in the following excerpt from the preprint of Gerhard Opfer
Quote:Author's note:
The reasoning on p. 11, that "The set of all vertices (2n; l) in all levels will contain all even numbers 2n>=6 exactly once." has turned out to be incomplete.
Thus, the statement "that the Collatz conjecture is true" has to be withdrawn, at least temporarily.
June 17, 2011 |
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print