I enjoy reading geeky webcomics. It’s one of my guilty pleasures. xkcd is my favorite, by far. A few weeks ago, I was perusing the xkcd store and found the Collatz Conjecture t-shirt (I’m also incredibly partial to geeky shirts.) I wasn’t familiar with the premise of this conjecture, so I hopped over to Wikipedia to see what it’s about.
According to the article, The Collatz Conjecture is the hypothesis that if you follow the algorithm presented, you will always end up at 1. The algorithm is to start with any natural number (a positive integer), and test it: if it’s odd, multiply your number by 3 and add 1; if it’s even, divide it by 2. Continue the algorithm indefinitely, and, according to the conjecture, you will always end up at 1.
That’s the idea, anyway. But it’s never been proven to be true. It’s assumed to be true, but not proven. (It hasn’t been proven because you cannot test every positive integer.) So it’s called a conjecture rather than a rule. And that’s where I started programming. I figured, hey, that’s easy. I’ll just write a program to prove it for me! Well, sort of. There’s an infinite set of positive integers, but a finite amount of memory in my computer. It will eventually run out of memory space on the machine. But it would still theoretically run forever on a perfect computer. What follows is no formal proof, but it’s about as close to a Q.E.D. as we will see for now in this problem. It starts with 2, proves that it goes to 1 (2 / 2 = 1), and then iterates to 3:
- 3 * 3 + 1 = 10
- 10 / 2 = 5
- 5 * 3 + 1 = 16
- 16 / 2 = 8
- 8 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
and so on. Now just to find a machine with infinite memory…
~Jonathan
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | // ***************************************************** // Programmer: Jonathan Landrum // Date: 16 December 2011 // ***************************************************** // Program: collatz.java // Purpose: Testing the Collatz Conjecture // Assumptions: None. // ***************************************************** public class collatz { // --------------------------------------------- // main(): // Does ALL the things // --------------------------------------------- public static void main (String[] args) { // ------------------------------------- // Variables // ------------------------------------- int n, in = 2, out = 1; Scanner scan = new Scanner(System.in); // ------------------------------------- // Introduce the program // ------------------------------------- System.out.println ("---------------------------"); System.out.println ("- -"); System.out.println ("- Collatz Conjecture Test -"); System.out.println ("- -"); System.out.println ("---------------------------"); System.out.println (); System.out.println ("Takes the positive integers"); System.out.println ("and tests them against the"); System.out.println ("Collatz Conjecture."); System.out.println (); // ------------------------------------- // Main block // ------------------------------------- while (out == 1) { n = in; while (n > 1) { if (n%2 == 0) { n = n/2; } else { n = n * 3 + 1; } // End if } // End while out = n; System.out.println (in); in++; } // End while } // End main } // End collatz |
Jonathan Landrum is a full-time husband and student, and a part-time research assistant and IT guy. He both works and studies at Mississippi College, where he is pursuing a Bachelor of Science in Computer Science. Continue reading…
Just because there is an infinite set of numbers is NOT why the conjecture is unproven. For example, There Is an infinite quantity of Mersenne Numbers having an even number of bits, but it is easy to prove that every one of them is diviible by 3 without having to test them all.
What is the reason it’s not provable? I haven’t had Foundations of Mathematics yet, so I don’t know the details of forming formal proofs. I just assumed it was because of the infinite set. Can you explain?
Obviously, no one knows WHY it’s unproven. But take my Mersenne Number example: by the successor rules for forming Mersenne Numbers, one sees that the successor of 1mod3 is 0mod3 and that the sucessor of 0mod3 is 1m0d3 all the way to infinity. Since the first Mersenne Number is 1mod3 with an odd number of bits, that means that all even bit Mersenne Numbers are 0mod3 (and therefore, divisible by 3). What’s important is I don’t HAVE to test every Mersenne Number. This is a simple example. The problem is that no such process has been worked out for Collatz that can decide the issue for the infinite set. So people keep testing it, not because they will ever reach infinity. but on the chance they might stumble on a counterexample. You wouldn’t need to explain why, just demonstrate it.
Also, in Collatz there is something called The Crossover Point. If it’s an interger, then there is a loop cycle. Now before you say “it must never be an integer” consider that when in the negative domain, the rossover Point IS an integer, that’s how we get the loop cycle at -17. As far as I know, there is no positive domain interger Crossover Point, but I can’t prove it. The point is that a mechanism exists that COULD make the conjecture false (although it would be a very large number).