## Saturday, March 27, 2010

### Colletz

XKCD brings my attention to a mathematical conjecture called the Collatz Conjecture that claims that for a particular operation, all numbers have a chain that eventually leads back to one. Read the Wikipedia article for details.
While a definite proof would win one a cool \$500, computer verification only suggests that the claim is true. No proof has actually been written. Mathematical proofs via computer are beyond me, but I did, for practice, write a verifying program, as they are very very short. Mine is 32 lines long, written in C.
`#include <stdio.h>void collatz(int);int main(int argc, char *argv[]){ if(argc==2) { int num=argv[1]; collatz(num); } else { printf("USAGE: collatz number\n"); } return 0;}void collatz(int num){ int count=0; while(num!=1) { if(num%2==0) { num=num/2; } else { num=num*3+1; } count++; } printf("Returned to 1 after %d cycles.\n",count);}`

The program accepts one number from you, the user, and runs a collatz chain until it reaches one. It then reports the length of this chain.
A trivial change to the main would produce a program that would report the length of ALL integers until it overflowed:
`int main(){ int num; for(num=0;num<MAX_INT;num++) { printf("%d:",num); collatz(num); } return 0;}`

The variable MAX_INT would be preset with a #define command according to the nature of the computer. Mine would be 2^64, as integers are 64-bits long on my computer.