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 🙂


To Infinity and Beyond

As I mentioned in my previous post, prime numbers are numbers which have exactly 2 divisors: themselves and 1.  This means that 1 itself isn’t prime, which is very important!  Prime numbers are fundamental in number theory, which is the study of positive integers and divisibility.  This is because of unique factorization, which is the property that every number can be written in exactly one way (where the order of the divisors doesn’t matter) as the product of prime numbers where primes can be used more than once (this fact requires careful proof but we’ll assume for now).  So prime numbers are the building blocks of all numbers.

A very important result that there are an infinite number of primes was proved over 2000 years ago by the Greek mathematician Euclid (although there’s some debate about what he actually proved).  I will prove this in two different ways here.

Proof #1:  This proof is a , which is where you start by assuming the opposite of what you want to prove and show that the assumption is impossible by finding an impossible consequence.

Assume to the contrary that there are actually a finite number of primes, which we can let be p_1, p_2, p_3, \dots, p_n (the subscripts indicate that not all of the p’s are the same and that there are n of them).  By unique factorization, this means that every number can be written as a product of these primes.  However, consider the number p_1 \cdot p_2 \cdot p_3 \dots \cdot p_n + 1, taking the product of all of the primes and then adding 1.  This number is not divisible by any of the primes p_1, p_2, p_3 \dots, p_n.  Therefore it has no prime factorization, which is a contradiction.  So, since if there were a finite number of primes that would be a problem, we have shown that there are an infinite number of primes!

Proof #2:  While proof by contradiction is extremely useful and is often the only good way to prove things, in this case there is a direct way (without contradiction) to prove the infinitude of primes as well, if you don’t like the contradiction way.  It’s more like what Euclid said.  It is:

For any finite set of primes p_1, p_2, \dots, p_n, the number p_1 \cdot p_2 \cdot \dots \cdot p_n + 1 is divisible by another prime p_{n+1} which is different from those n primes.  Therefore, we can make any set of primes bigger and bigger, so there are an infinite number of them.

And now for some nerdy humor, a quote by Noga Alon, a famous Israeli professor:  “I was interviewed on the Israeli radio for five minutes and I said that more than 2000 years ago, Euclid proved that there are infinitely many primes.  Immediately the host interrupted me and asked, ‘Are there still infinitely many primes?’ ” 🙂

What is math anyway?

Since I’m trying to write a blog about math, I should probably explain what math is first!

Math, roughly speaking, is a vast collection of knowledge that is rigorously established. What does that mean? Proofs. Proofs are at the heart of math.

Mathematicians go crazy with proofs. In fact, they insist on making everything rigorous and basing things off of very basic assumptions called axioms. Even the simple, seemingly obvious fact that 0 \cdot n = 0 for any number n has proof using simpler axioms about our number system.

So why do we bother proofs? Often the first step towards proving something is noticing that a certain fact is true in a lot of cases. This is a pattern. But, patterns are not enough to show a general result. For example, in the early 1800’s, the mathematicians Legendre and Gauss noticed that the expression n^2-n+41 is a prime number for n from 1 to 40. (A prime number is a number that is only divisible by 1 and itself, so 3 is a prime number because it cannot be broken up into more factors but 6 isn’t a prime number because it is 2 \cdot 3.) It seems like with so much evidence, it should be true for all positive counting numbers, and that’s what they thought too. However, in the very next case, n=41, it fails to be prime. This is easy to see because 41^2-41+41=41^2, which is not prime. Silly Legendre and Gauss!  Furthermore, often a proof gives us important insights that can then be applied to other problems.  The why is crucial.

Making guesses is how math evolves.  Something that is not proven but is believed to be true is called a conjecture. There are many, many important problems with the status of conjecture right at this moment. That is what current mathematicians keep themselves busy with. For example, one conjecture that hasn’t been resolved is whether or not there are an infinite number of positive counting numbers for that same expression n^2-n+41 where the result is prime (so even though it isn’t true for all positive counting numbers, it could still be true for an infinite number of them).  This is an open question for almost all quadratic equations (an expression with a squared term as its highest power), in fact.

In most middle and high school math classes, proofs are often left out or only partially stated. I think this is a mistake, since proofs are so key to math. Everything has a proof. So, the next time your teacher tells you something is true, try to find a proof!

%d bloggers like this: