/* ************************************
Collatz Conjecture Test
-----------------------
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
expect 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
E. Stuart Hicks
2013-12-05
************************************ */
#include
#include
#include
#include
#include
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 \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;
}