Collatz Conjecture - Implementing a Natural Number

Collatz conjecture is a strange problem in mathematics. In particular, the conjecture states the following:

Take any natural number n. If n is even, divide it by 2 to get n / 2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

Wikipedia, Collatz Conjecture

What's particularly interesting about it is trying to formally prove the validity of the statement. While a proof would be rather fascinating for a problem such as this, I'm certainly not the man to be working on creating that. Instead, I've become more interested in its implementation as software.

Here's a basic implementation of the algorithm:

n € N (integer >= 0)

while ( n != 1 ) {
    if ( n % 2 == 0 ) 
        n = n / 2
    else
        n = 3*n + 1
}

return


Normally, the question for a person is "Will this halt?" I believe there is a proof that this is an undecidable problem, but that's not what really interest me here. What interests me here is more detail oriented towards system.

The largest possible representable integer on a 32-bit computer is 4,294,967,296 (unsigned). This, in respect to Collatz conjecture, is a relatively small number. The question then is simply how does one verify significantly larger numbers? A simple solution is using a 64-bit machine which can provide for an incredibly larger integer, but this is very platform specific and still has a very well defined limit.

Oddly enough, I did not find any implementations of a natural number that I really liked online. There is a solution online that I've found from searching a bit, but I found this implementation a little bit convoluted and a bit over-the-top. For our purposes, we probably don't need to implement a super formal definition of a Natural using a successor operator. It also seems like the problem of not having enough digits should have been worked on already.

A solution I came up with in Java made resolving this problem pretty simple - Implement a natural number class that has no hard defined limit by using BigInteger. As per the Java API on BigInteger:

All of the details in the Spec concerning overflow are ignored, as BigIntegers are made as large as necessary to accommodate the results of an operation.

In other words, the desired effect we want except that this will allow for positive and negative values. Regardless, this is a fairly trivial fix. My solution is given below (minus some comments and some simple unit tests):

@SuppressWarnings("serial")
public class Natural extends BigInteger {
/**
* Natural constructor created from an array of bytes
* 
* @param naturalNumber The value of the natural number
* @throws NumberFormatException If the number is not a natural number
*/
public Natural(byte[] naturalNumber) throws NumberFormatException {
    super(naturalNumber);

    if (!isNatural(this))
    throw new NumberFormatException("The number n must be a natural number - " + naturalNumber + " >= 0");
}

/**
* Natural constructor created from an array of bytes
* 
* @param naturalNumber The value of the natural number
* @throws NumberFormatException If the number is not a natural number
*/
public Natural(String naturalNumber) throws NumberFormatException {
    super(naturalNumber);

    if (!isNatural(this))
        throw new NumberFormatException("The number n must be a natural number - " + naturalNumber + " >= 0");
}

/**
  * Defines whether a number (n) is natural or not
* 
* @param BigInteger n The number to verify is natural
* @return boolean Whether or not n is natural or not
*/
public static boolean isNatural(BigInteger n) {
    return n.compareTo(BigInteger.ZERO) >= 0;
}
}

With this simple implementation, and a revised implementation of Collatz Conjecture using Natural, I've been able to validate some fairly large digits (5,000 digits and larger if I remember correctly). I've also posted the code above here to help alleviate the horrible formatting issues.

There are lots of other things to think and talk about in respect to Collatz Conjecture including how to log the steps and how to enhance performance. All things I'll write about later hopefully!

Someone called Maria's name
I swear it was my father's voice
Saying, "If you stay you'll all be slain
You must leave now - you have no choice
Take the servants and ride west
Keep the child close to your chest
When the American troops withdraw
Let Zapata take the rest"

Warren Zevon, Veracruz