Collatz Conjecture Counter-Example Search Using Scala

As a lover of mathematics, Collatz’s conjecture is fascinating to me. Simple to define, easy to compute, but a beast to (dis)prove.

Put simply, for positive integers, n>1:

We can then generate a sequence of these numbers, starting at an initial value n, by:

Collatz’s Conjecture is simply, that these sequences, for all positive integer values, n, will eventually reach one. It may bounce around a lot, increasing well beyond the initial value, go back lower, perhaps spiking again, over-and-over, until eventually, it reaches one. For a lovely discussion of Collatz’s Conjecture see:

The stopping-time is defined as the number of iterations, i, required before reaching one.

Lots of effort has been done to prove, for increasing values of, N, that all n≤N satisfy the conjecture. That is not my goal, because:

• It’s really hard to do with limited resources
• I would have to compete with people who have a lot more resources, and probably a better insight into (dis)proving the conjecture
• Paul Erdős, is quoted to have said of this problem: “Mathematics is not ripe enough for such questions”

Okay, great, so what is my goal?

Goals

• To write a simple Scala program that can find the stopping number for very very large integers
• Run it on a Raspberry Pi, which can run noiselessly looking for a counter-example
• With P(success) > 0, I will find a counter-example, become famous, and wealthy, allowing me to read novels and drink coffee with my cats until my last days

Scala Code

You can find this in GitHub at: (https://github.com/scottralph/collatz). I hope to clean up the code further but make no hard promises. The only challenging part of the coding is to deal with arbitrarily large integers and do basic arithmetic operators on them. I could have used off-the-shelf libraries for this, but I wanted to keep it simple, and a little fun, so I did it myself.

The interesting class is called Digits, and uses an array of bytes as its main focus of attention. I wanted to be able to deal with numbers whose digits would be up to a million digits long. Such a number is still computable in an hour or so on a weak processor.

• The toString() method on lines 9–22 simply outputs the digits in groups of 100
• Line 25, asHashString() is a helper-function that creates a string-verion of the number, for purposes of efficiently hashing in a set
• The method addOne(), on lines 28–50, is straightforward. The only trick is to deal with the carry, and also expand the size of the result when all of the digits are 9.
• The method multiplyDigit, on lines 52–67, multiplies the values by a given scalar
• Likewise half(), 69–82, halves the number
• The method next(), on lines 84–89, just takes the current number and computes the next one of the sequence
• stoppingTime() computes the number of steps to reach 1
• The object companion object method apply() takes an integer for the length and generates a random integer of the specified length

If I find a counter-example, you can read about me in the news, otherwise I will be here working for a living.