Collatz Conjecture

This takes a number and applies the Collatz conjecture to it. This involes the following rules:

• If the number is even, x = x / 2
• If the number is odd, x = 3x + 1

The result of applying this enough times is believed to always yield 1; however, to date, no one has been able to formally prove it.

This implementation has been extended to support all integers. We use the following modified rules:

• If the number is even, x = x / 2
• If the number is odd, x = 3x + (|num| / num)

This equation for odds still results in equivalent computation for the positive integers used by the original conjecture thereby maintaining validity of the results in the original space.

Negative integers will converge on -1 instead of 1. The modified odd equation will effectively result in x=3x-1 instead. The result is that the sequence to -1 resembles that in which the one the number's positive partner takes to 1 except in negative number space. (i.e. 5,16,8,4,2,1 vs -5,-16,-8,-4,-2,-1)

Zero is a special case as |0|/0 is invalid. If treated as an even number (as is the case here) it will remain 0 and never change. If treated as an odd number, the original equation for odds (x=3x+1) results in 1 as with the positive integers. I'm not really sure which is more "valid" so I just handle it differently and allow 0 to be another halting state.

/* cc -std=c99 -lm -o collatz collatz.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <errno.h>

long long int f(long long int num) {
   if (num % 2 == 0) return num / 2;
   else return 3 * num + (llabs(num) / num);
}
/*   else return 3 * num + 1;   # Original */
/*   else return (3 * num + (llabs(num) / num)) / 2;   # Optimized */

int main(int argc, char **argv) {
   long long int num, iter;

   if (argc < 2) {
      printf("Usage: %s <integer>\n", argv[0]);
      exit(1);
   }

   num = strtoll(argv[1], NULL, 10);
   if (num == 0) {
      if (errno == EINVAL) {
         printf("Error: Unable to convert to base 10\n");
         exit(2);
      } else if (errno == ERANGE) {
         printf("Error: Value out of supported range\n");
         exit(3);
      } /* else - no error they just provided "0" */
   }

   printf("1 : %lld\n", num);
   for (iter=2; llabs(num) > 1; iter++) {
      num = f(num);
      printf("%lld : %lld\n", iter, num);
   }

   return 0;
}