Collatz Conjecture
 

I am curious, has anyone ever heard of this? Or even better, has anyone here actually tried working on it?

For those unsure of what I mean.. Pick any postive integer x. If x is odd, multiply it by 3 and add one. If x is even, divide by two. Repeat this. The conjecture states that for any number in Z+ the sequence will end in the cycle 4, 2, 1.

Absane,

It is a very interesting problem, so much so that Paul Erdos thought it was beyond the mathematics of his time. He offered one of his famous prizes to anyone who could prove it. I know it has been checked up to pretty high numbers on the computer, and that there are statistical reasons why it is probably true. You may have already known these few tidbits and I don't really know much about it, but maybe someone else can tell you more.

I have actually figured out the statistical reasoning out myself. It is funny how simple the problem is to state, even more so than Fermat's Last Theorem... but it seems to be just as hard if not harder.

I have been working on it on and off since my senior year in high school.. I am now just barely in my Junior year of college. I reduced the problem down to a summation with 2^k and binomial coeficients (you know, the whole factorial thing). Basically 2^k*(n i) + 2^g(p i) etc. If I can show this reduces again to one big 2^m summation, I will have proved it. It requires a lot. I am just wondering if anyone else has suggestions.

How much do you know about iterated functions (as in fractals)?

Shamefully, very little.

You should look it up. I worked on the conjecture for about three days last year. I figured I could use something along the lines of iterated functions. And I'll (you'll) also have to develop some techniques independently. I was learning more interesting stuff last year, and didn't pay much attention to this. But you've probably got me started again.

Why only 3 days?

I think I am close to solving it myself because I reduced it to a diophantine equation... d = 2^k*[2^alpha - Z*(k-1)]. I just have to show that in the solution set of k and alpha they are the combination needed to make the 3x+1 problem work for all odd numbers. And I think it is reasonable to assume that one can say if it works for all odd numbers, then it works for all integers in Z+ (since you can divide an even number the appropriate number of times to make it odd).

It's easy to prove that there are no other repeating cycles that contain only one odd number.
Is it possible to prove that there are no repeating cycles containing [i]n[/i] odd numbers, for any or all [i]n[/i]>1?

Ah. I lost a few days of exam reading due to examining that function. In computer science it's a well known termination problem, and termination analysis has so far been quite unable to find a good decreasing measure. I toyed with some ideas about the number of different prime factors, but it's quite difficult to get a grasp on the sucker.

Does anyone know if it was shown that the number of cycles for any positive odd number is unique? That is, start with 1... the number of cycles for 1+2n for n is a positive integer, no two will have the same number of iterations to terminate at 1? I believe I just shown it to be true.

[QUOTE=Absane]Does anyone know if it was shown that the number of cycles for any positive odd number is unique? That is, start with 1... the number of cycles for 1+2n for n is a positive integer, no two will have the same number of iterations to terminate at 1? I believe I just shown it to be true.[/QUOTE]

You made a mistake then. There are infinitely many sets of odd numbers that take the same number of steps to hit 1. For example, 3 and 21, 227 and 1365, 14563 and 87381 (can you see the pattern?).

3,10,5,16,8,4,2,1

21,64,32,16,8,4,2,1

Damn you people, I'll sleep uneasy tonight, thinking about this problem again!

In relation to this problem... are there integers k and m such that 3^(k)*5=2^(m)-1?

k=1
m=4

No idea if there's any others.

[QUOTE=funkstar]I toyed with some ideas about the number of different prime factors, but it's quite difficult to get a grasp on the sucker.[/QUOTE]

I like funkstar's prime factor approach. The "even" operator continually gets rid of any factors of two. The sequence terminates when the "odd" operator gets rid of all other factors.

-Dale

[QUOTE=Pete]k=1
m=4

No idea if there's any others.[/QUOTE]

I wonder if there is a way to show it's the only solution. This is a specific case of 3^(k)*(3x+2)=2^(m)-1

Find all integer solutions.

Cancel that.. stupid idea. k is always 1.