The 3n+1 conjecture


Hi everyone!  First of all, note that there’s now a button to share a post with all of your friends by email, facebook, or twitter.  If you do share that would be great!

In a typical middle or high school math class it may be hard to tell, but math is constantly evolving.  There are many important problems in various fields which we don’t know the answer to.

Here’s one good problem that is easy to state, but that has stumped the best mathematicians in the world since 1937!  It is called the Collatz Conjecture (a conjecture is an unsolved problem) after the guy who came up the problem, Lothar Collatz.

Pick a number, any (positive whole) number.  If your number is even, divide it by 2.  Otherwise if it’s odd, do three times your number and add 1.  Do this procedure over and over, if your current number is even divide by 2, if odd multiply by 3 and add 1.  The conjecture is that eventually, no matter what your number is, you will get the number 1.

For example, for the number 6, the steps are as follows:

6 \rightarrow 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1.

Try it out for yourself!

Due to the power of computers, we know that every number up to 10^{18} satisfies the 3n+1 conjecture.  That’s 1,000,000,000,000,000,000.  While this is enough evidence to convince most people, it will only be proven when it shown for every single whole number (see my first post for why we prove things).

Also see my friend’s article about “The Art of Math” which came out recently in an online magazine called KidSpirit.  It covers other nice proofs, some of which I may write about in the future too 🙂  http://kidspiritonline.com/2010/09/the-art-of-mathematics/

Advertisements

5 responses to this post.

  1. Weinreich’s conjecture: If P is a conjecture, and P is true for all values of n from 1 to 10^18, then P.

    Is this problem P or NP? Do those categorizations even apply to this kind of problem?

    Reply

    • Posted by Meena on September 9, 2010 at 11:30 am

      Disproven! Also if you’re talking about the 3n+1 conjecture being P or NP that doesn’t really make sense. P and NP has to do with the time that it takes to solve a problem, the problem is in P if it can be solved in polynomial time (so if x is the length of the input it can be solved in say x^3+x time), and NP is nondeterministic polynomial time which is more complicated to explain but roughly you’re allowed to branch and perform many operations simultaneously. So I guess you could talk about whether deciding if a given number eventually yields one is in P or NP, but that’s a different question. Also this is way out of the scope of this blog so I’ll stop now 😛

      Reply

      • Posted by Allan on September 10, 2010 at 10:59 pm

        First off: “out of the scope of this blog” means you’re allowed to talk about it in the comments.

        Also: Sure, talking about whether it is polynomial in log(N) is pretty boring — but suppose that instead of writing it in binary, we wrote N ones. Or, abandon all pretense of Turing machine and try to figure out what the number of steps is in terms of N.

        The problem with figuring out whether this problem is in P is that it assumes the number of steps is finite. Which is the Collatz conjecture.

  2. I have a conjecture that every whole number has at most 30 digits. My conjecture is true for every number between 0 and 10 to the 18th power. So by Weinreich’s conjecture, my conjecture must be true for all numbers. 🙂

    Reply

  3. Posted by Anon on December 11, 2010 at 11:56 pm

    Suddenly, this came upon me:
    http://xkcd.com/710/

    Reply

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: