wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Unsolved: 3x+1 Sequence Conundrum
        
(Message started by: Sameer on Nov 25^th, 2006, 10:59pm)

Title: Unsolved: 3x+1 Sequence Conundrum
Post by Sameer on Nov 25^th, 2006, 10:59pm

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....

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by TenaliRaman on Nov 25^th, 2006, 11:24pm

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". :-/

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by Sameer on Nov 26^th, 2006, 2:01am

I found it here: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1099916635;start=21#21

However if people are interested in discussing please feel free to. Looks like almost 2 year old discussion

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by Sjoerd Job Postmus on Nov 26^th, 2006, 3:36am

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.

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by fiziwig on Dec 24^th, 2006, 11:26am

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.

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by Icarus on Dec 24^th, 2006, 5:30pm

on 12/24/06 at 11:26:41, 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.

???

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by fiziwig on Dec 24^th, 2006, 9:51pm

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.

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by fiziwig on Dec 25^th, 2006, 12:15am

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

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by Obob on Dec 25^th, 2006, 1:37am

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.

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by Icarus on Dec 25^th, 2006, 6:04am

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 12/25/06 at 00:15:42, 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.

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by fiziwig on Dec 25^th, 2006, 8:41am

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...

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by Leonid Broukhis on Jan 28^th, 2007, 12:14pm

on 12/25/06 at 06:04:14, 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 :P

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by Icarus on Jan 28^th, 2007, 1:23pm

>:(

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?

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by ThudnBlunder on May 9^th, 2011, 4:41pm

...by xkcd :)

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by ThudnBlunder on Jun 3^rd, 2011, 2:40pm

http://www.newscientist.com/blogs/shortsharpscience/2011/06/simple-number-puzzle-possibly.html

Title: Re: Unsolved: 3x+1 Sequence Conundrum
Post by swt on Aug 10^th, 2011, 7:56am

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