Collatz Conjecture: A simple recursive implementation

mgcadmin 16-10-2021

The Collatz Conjecture

The Collatz conjecture is an interesting "open" math problem regarding sequence generation. First proposed in 1937, the conjecture states that if you start with any positive integer(n), and if its even divide it by 2 (n/2), and if its odd multiply it by 3 and add 1 (3n + 1), that it will create a sequence of numbers that will invariably end in 1.

Despite its relativly simiple nature, it remains an open question, in fact it has been said that "Mathematics may not yet be ready for such questions". The problem lies in the sheer magnitude in the number of calculations that need would need to be done to prove this: it approaches infinity, because while we can prove that this holds true for every positive integer calculated thus far we can not say for certain that the next integer attempted will turn out to not satisfy the conjecture.

The Collatz conjecture is beautiful because its simplicity belies its complexity.

The conjecture lends itself beautifully to a recursive implementation, the description of it practically writes the code for you, complete with a base case.

The Algorithm

I've been doing alot of C and C++ lately, so i figured for this I would give Swift a whirl. As stated up above, this is the type of problem that screams recursion, and Swift indeed supports tail recursion. to test whether a number is odd or even we will use a func write a function that uses the modulo operator (%) on the input. If n % 2 == 0, than the number is even, if not, it is odd:

func isEven(num: Int) -> Bool {
    return (num % 2 == 0) ? true:false;
}

 

With that in place, it's now trivial to steer our input to the next operation: division by two or multiply by three and add one. 

func collatz(_ k: Int, _ count: Int) -> Int {
    if (k == 0 || k == 1) {
        print(k)
        return count
    }

    let inc = count + 1
    print("\(k)", "-> ", terminator: "")

    if (isEven(num: k)) {
        return collatz(k/2, inc)
    } else {
        return collatz((k*3)+1, inc)
    }
}

In the above code, k is the input number, and count is used for calculating the period of the sequence.

Testing the Conjecture

To make sure everything is working how its should we'll do a quick check of a few numbers:

for i in 1...5 {
   let result = collatz(i, 0)
       print("Collatz Conjecture starting interval of \(i) generated \(result) integer sequence.")
    }
}


1
Collatz Conjecture starting interval of 1 generated 0 integer sequence.

2 -> 1
Collatz Conjecture starting interval of 2 generated 1 integer sequence.

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Collatz Conjecture starting interval of 3 generated 7 integer sequence.

4 -> 2 -> 1
Collatz Conjecture starting interval of 4 generated 2 integer sequence.

5 -> 16 -> 8 -> 4 -> 2 -> 1
Collatz Conjecture starting interval of 5 generated 5 integer sequence.

 

Where things get weird

Assuming we had access to a mainframe with inifinite uptime and hypothetically could avoid integer overflow, we could simply run this program in an incrememnting for loop, with the condition that it would stop if the algorithm produced a sequence that did not end '1'. 

But here is the thing: If the number produced is not '1', than we have stated that it is to be divided by 2 if even, or multiply by 3 if its odd: so what gives?

The only way this conjecture could be "false" is if there exists a sequence that would lead back to itsself, essentially a pure "infinite loop" which would then open another question: can we prove that the sequence is truly infinite and inescapable? These are the type of things that send on spiraling down the rabbit hole, and as XKCD succinctly put, cause you're friends to stop calling.

As it stands, we wont be making math history with this article, But the Collatz conjecture is the type of exercise thats a fun use for teaching recursive algorithm implementation, at least its not the same old GCD algorithm.

If you would like to see my Swift implementation in its entirety, it is available on my github:

https://github.com/maxgoren/examples/blob/main/collatz.swift

 

---