Collatz Conjecture

In this blog post we deviate a little from the ES6 parade I’ve been writing here. We dive into the Collatz Conjecture (otherwise known as the 3n + 1 conjecture) on today’s blog. The Collatz conjecture is the simplest open problem in mathematics.

 Collatz Conjecture

The conjecture states that:

Take any positive integer 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 (which has been called “Half Or Triple Plus One”, or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

Basically if we give the number 10 the breakdown is as follows: 10 > 5 > 16 > 8 > 4 > 2 > 1 (match!). The conjecture states that every arbitrary positive integer will reach back to the number 1 after jumping through the hoops.

collatz_conjecture.png
Source: https://xkcd.com/710/

 Trivial Code

So to automate most of the rudimentary math involved we will write a program to run through the possibilities until we reach the number 1 or I guess run in perpetuity if in fact the conjecture is false.

function collatz(num = null, trace = []) {
  // Type checking and check if positive int
  // Zero is defined as neither negative nor positive
  if (typeof num !== 'number' || num <= 0) {
    return new Error(`Invalid argument: ${num}`);
  }

  // Log out the trace
  trace.push(num);

  // Check to see if its a match
  if (num === 1) {
    console.log('It matches!');
    return trace;
  }

  // Main recursion
  if (num % 2 === 0) {
    // even
    return collatz((num / 2), trace);
  } else {
    // odd
    return collatz(((num * 3) + 1), trace);
  }
}
 Enhancements to consider

Screen Shot 2016-10-23 at 9.04.42 AM.png

 Importance in Computer Science

Well… we could use the Collatz conjecture as an interview question but going beyond the most basic use case of the mathematical function f(x) required by the conjecture we see that the Collatz conjecture has impacts on Number Theory and Computer Science.

Gerhard Opfer, in 2011, published a paper that claims to have prove the Collatz conjecture. This proof, however, was later proven to have a flaw and was debunked.

The Collatz conjecture is similar to that of Fermat’s Last Theorem which is decidedly simple to understand but unbelievably hard to prove.

The same can be said about analyzing code.

Some minuscule codebase can have a very high complexity while other very large (cough “enterprise”) projects are very easy to implement and comprehend.

Think about validating an email address using regex.

A solution to Collatz conjecture would have consequences for symbolic dynamics, discrete mathematics, decidability, and number theory. Basically the back bone of computer science would be changed.

 
9
Kudos
 
9
Kudos

Now read this

Spirally Traversing a Two-Dimensional Array in JavaScript

This is a way to traverse a two-dimensional array (or a matrix) from the top left, spirally in a clockwise manner in JavaScript. This solution is inspired by functional programming and it uses tail recursion. Steps: When you start with... Continue →