Coding: Bring the Noise

%26lt;0011 Em

More thoughts on the Collatz Conjecture

leave a comment »

I made a quick housekeeping sweep of the blog recently, and wanted to revisit the Collatz Conjecture.  I’m sure it’s been suggested before, but I believe there’s another method of proving the conjecture:

Collatz(k) for all k \in [2^{n}, 2^{n+1}] where n \in \mathbb{Z}^+ > 2

That is to say, we only need prove that for an n > 2, all integers between consecutive powers of 2 resolve according to the collatz conjecture.  I’m not sure where to go from there, but for instance we can show that in general:

2^n + 1 \Rightarrow 3^{r} + 1 where r is the number of (divisible by 3) iterations such that n = 2r

Derivation:

Consider 2^n + 1 where n > 1

First step: 2^n + 1 must be odd, so multiply by 3 and add 1.

3(2^n +1) + 1

3\cdot2^n + 4

Second step: 3\cdot2^n + 4 must be even, so divide by 2.

\frac{3\cdot2^n + 4}{2}

3\cdot2^{n-1 }+ 2

Third step: 3\cdot2^{n-1}+ 2 must be even, so divide by 2.

\frac{3\cdot2^{n-1}+2}{2}

3\cdot2^{n-2}+1

We’ve gone through 3 steps.  If n = 2, we’re at 4 and we’re done.  Let’s say n is very large, so that we can go through another 3 iterations and find a pattern.

Fourth step: 3\cdot2^{n-2}+1 is odd again, so multiply by 3 and add 1.

3(3\cdot2^{n-2}+1) + 1

3^2\cdot2^{n-2} + 4

Fifth step: Even again, divide by 2.

\frac{3^2\cdot2^{n-2} + 4}{2}

3^2\cdot2^{n-3} + 2

Sixth step: Still even, divide by 2.

\frac{3^2\cdot2^{n-3} + 2}{2}

3^2\cdot2^{n-4} + 1

The next iteration will increment the power of 3, and give us a number divisible by 4, and so on.

More generally, we’ll have:

3^{\frac{k}{3}}\cdot2^{n-2\frac{k}{3}}+1 for k iterations where k is divisible by 3.

Letting r = \frac{k}{3} we have

3^r\cdot2^{n-2r}+1

When n=2r we can simplify:

3^r+1

I’m not sure where we go from here.  The next thing I want to do is a 3d plot of iterations to resolve against the position (from 0 to 1) between 2^n and 2^{n+1} for varying n.

Advertisements

Written by delwinna

May 13, 2013 at 2:15 am

Posted in Puzzles

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: