Mathematics from the eyes of a High School Student! – Bidit Acharya

The Collatz Conjecture

Before we begin the discussion, I’d like to play a little game with you

  1. Pick any natural number.
  2. If your number is even, divide it by 2. If it is odd, multiply the number by 3 and add 1 to it. (i.e. for an even number n compute \frac n2 and for an odd number n, compute 3n+1. )
  3. You now have with you a new number. Repeat step 2. Do not stop until you end up with the number 1.

For no natural number n will this process continue indefinitely. You will get to 1 after some finite number of repetitions. This is the essence of the Collatz Conjecture.

Example I choose the number 21. Since it is odd, I multiply it by 3 to get 63 and add 1 to it to get 64. Since 64 is even, I divide it by 2 to get 32 which gives me 16 which gives me 8, 4, 2 and then finally 1. As desired!

Now this was a pretty easy example but you can try it out for yourselves. Let me tell you that for some numbers, it will take a ridiculously long time until you get to 1. For example for the number 521, it takes 124 steps to get to 1!

Significance of the Conjecture

The Collatz Conjecture was first proposed by German mathematician Luthar Collatz in 1937. The conjecture has many different names but the most amusing of of them is HOTPO which stands for Half Or Triple Plus One. This conjecture may seem rather unimportant and inapplicable. Despite its frivolous nature, the conjecture is seems to be pretty important for number theorists.

According to Greg Muller‘s answer here on Math.SE, “…the Collatz conjecture seems to say that there is some sort of abstract quantity like ‘energy’ which is cannot be arbitrarily increased by adding 1. That is, no matter where you start, and no matter where this weird prime-shuffling action of adding 1 takes you, eventually the act of pulling out 2s takes enough energy out of the system that you reach 1. I think it is for reasons like this that mathematicians suspect that a solution of the Collatz conjecture will open new horizons and develop new and important techniques in number theory.”

My take on this conjecture

The Collatz conjecture is probably one of the first conjectures I encountered. Since it was pretty easy to understand I thought that maybe I could prove it without any help (at that point, I did not know what a conjecture was!) I tried for a few weeks and then finally decided to look it up on the internet for a hint. It was then that I found out that it was yet to be solved!

This is how I tried to tackle this problem back then

Any power of 2 will certainly get to 1. Infact, this is the only way to get to 1. The sequence obtained for any number (called the hailstone sequence) should always “enter” the series 1,2,4,8,16,32, 64 \ldots (powers of 2) if it is to eventually get to 1. Even more so, the hailstone sequence will only enter the series 1,2,4,8,16,32,64 \ldots from even powers of 2 only (like 16 or 64). This is pretty easy to prove

Consider a number x that is not a power of 2 but will be one on the next iteration (like $latex 5$; since 5 \times 3 +1=16=2^4. Note that x has to be odd because if it were even then x would have to be a power of 2 hence it would have already entered the series of powers of 2.

So since x is odd the next number in line would be 3x+1. This should be a power of 2. OR \exists n,x \in \mathbb N such that,

3x+1=2^n \iff x= \frac{2^n-1}{3}\;\;\;\;\;\;\;\;(1)

What is required is that n be proved even.

Lemma \text{ For some }x,n\in \mathbb N,\; 3x+1=2^n\iff n|2

Proof  The fact that x\in \mathbb N implies (2^n-1)|3. This follows from(1). We now find the solution set for the equation 2^n-1\equiv 0\; (\bmod \;3) or 2^n \equiv 1\; (\bmod \;3).

We begin by noting 2\equiv -1\; (\bmod \;3) \implies 2^n\equiv (-1)^n\; (\bmod \;3). Since (-1)^n=1\iff n|2, it follows that  2^n\equiv 1\; (\bmod \; 3)\iff n|2. This means that the quantity 2^n-1 is divisible by 3 iff n is even.  It follows from this that if a quantity 3x+1 equals some power of 2, then 2 has to be even. As desired.

Obviously, not every odd number n will result in a power of 2. For instance, 7\times 3+1=22 is not a power of 2 but 21\times 3+1=64 is a power of 2. Is there some pattern to it? As it turns out, there is; and it is pretty easy to spot it too. For this we go back to (1) :

x= \frac{2^n-1}{3}

The odd number x has to satisfy this relation. So to find new xs, ll we need to do id plug in even numbers n into the equation. We see that the series of x’s obtained follow a certain pattern.

To make things easier, define a function f:n\to\frac{2^n-1}{3}. The domain of the function is the set of even numbers.

For even number n, if we look at the difference f(n+2)-f(n), we see that it is $2^n$. So, difference between the odd number x that results in 2^n in the next iteration and the other odd number that results in 2^{n+2} differs by 2^n.

Example The number 5 results to 16 (5\times 3+1) which is 2^4 and the number 21 results to 64 which is 2^6. The difference between 5 and 21 is 16; which is 2^4.

While these things hardly have anything to do with proving the conjecture itself, these are the observations that I made on the hailstone sequence. I thought I could prove it then, but these observations is as far as I got.

I actually had many other things to post about but none of them involved my own observations. So I decided to flip the pages of my scrap book  and post it here.

Please do comment and share this post. Any constructive feedback is welcome!

About these ads

Comments on: "The Collatz Conjecture" (4)

  1. Willie Johnson Jr. said:

    There is a free download of my e-book at Amazon for the next 2 days: How To Solve the Beal and Other Mathematical Conjectures. ( Yes it tackles the Collatz conjecture also.)

  2. Chris Bernardini said:

    There is a regularity in this conjecture that i have found. but unfortunately i am having a hard time getting anyone to even look at my work on this problem. i have found a method to form the entire tree of descent of any Odd number just by using its value as a starting point.. it involves a few simple steps and a few rules. i cannot prove any of them but they are there and i have picked them all out through rigorous analysis. if you wish to know more about my analysis email me at chrisb2213@gmail.com and maybe between the two of us we can work this problem out. all i want is if my work is used to get some mention for it when and where it is used. all prize money if there even is any for this prize is all yours if you can formulate a proof using my research i could care less about money. this is about Mathematics. the only thing im going to tell you about my research here is that you have to split up all the odd numbers into various sets. and the numbers behaviors are all defined by which set it is contained in. no sets have unions and 1 causes itself to be forced into its own subset of odd numbers in two different distinct ways. i hope to hear from you if you truly have an interest in this problem.

    Good luck and best wishes,

    Chris J. Bernardini Jr.

  3. Really nice :D I really like the way you put it! I just read about Collatz Conjecture two weeks ago and I am still looking into it. But did you notice the typo $2^n$?

Please leave in your thoughts on the Post

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: