Simple Collatz Conjecture testing script

  • javascript
  • nodejs
posted on 1st December 2021 ∙ by Hynek Svacha ∙ 9 min read

It is seemingly a simple problem: We take a number n. If n is even, divide it by 2. If it’s odd, multiply it by 3, then add 1. Proceed with the resulting number (the result is our new n). The conjecture is that no matter what the initial value is, the sequence will always result in a 4 – 2 – 1 loop.

My older son (eight years old) has developed some passion for math. Because I’d like to feed his passion as far as I can, I introduced him to the above mentioned problem: the Collatz Conjecture.

The problem that “looks very simple, but even the most famous and clever mathematicians, with the help of the fastest computers, haven’t solved it yet 🤷” actually caught his attention. We tried to test a couple of numbers just with paper and a pen. It was fine, but as soon as we finished the first one, I was itching to write some code that would test the number and relieve us of the chore of manually counting every step.

So I did it. And the kids were actually excited! Both of them spent at least an hour testing (mainly) ridiculously large numbers. In the meantime, I was fiddling a little with the script, adding some colors and such, which also caught their attention. They’re on the way to becoming some nice geeks 🤓!

So, is Collatz a good way to introduce kids to math AND coding? I wouldn’t dare to say so. But if you’d like to try, I can show you how I did it.

The algorithm

The algorithm itself is very simple (yes, it can be written in a more fancy way, but I’m O.K. with good ol’ while loops).

/*
 *  Take a number. Let's assume it is a positive integer (we'll check for that later).
 *
 *  If it's even (the remainder of division by 2 is 0), divide it by 2.
 *  Otherwise, multiply it by 3 and add 1. Proceed with the result.
 *
 *  If the result ever gets to 1, stop. Collatz was right about that number!
 *  (If we didn't stop, we'd get into the infinite 4 – 2 – 1 – 4… loop.)
 */

let n = 42;

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

console.log("Regarding number 42, it seems that Collatz was right.");

Well, it is really nice that it works for one arbitrary number (even if the number is The Answer to the Ultimate Question of Life, the Universe, and Everything), but how about the user input?

The readline module

In Node.js, there is a built-in class readline (I am sure there are multiple third-party libraries, but let’s use the default one). Since it is built-in, there is no need to install it, we’ll just require it.

This is the example from the official docs. First, we’ll instantiate a rl object by calling readline.createInterface(). Then, we’ll use an rl.question() method to get the user input from the prompt; we can also listen to events using the rl.on() method (in the example, we’re listening to close event).

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.question("What is your name ? ", function (name) {
  rl.question("Where do you live ? ", function (country) {
    console.log(`${name}, is a citizen of ${country}`);
    rl.close();
  });
});

rl.on("close", function () {
  console.log("\nBYE BYE !!!");
  process.exit(0);
});

So let’s apply this to our Collatz:

Our first draft

So, let’s modify the example above to fit our needs (testing the Collatz):

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.question("Insert a number: ", function (input) {
  let n = Number(input);

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

  console.log(
    `Regarding number ${Number(input)}, it seems that Collatz was right.`
  );
  return rl.close();
});

rl.on("close", function () {
  process.exit(0);
});

Add type guard

It looks neat, doesn’t it? It actually works most of the time. The problem with this code arises when we input anything that is not a positive integer, e.g., a string. Then, it results in an infinite stream of NaNs.

So we probably need to check the user input before using it (which is always a good practice). We can end up checking if the input (explicitly cast to a number by Number(input) earlier) is an integer (this way we’ll be safe from NaNs and floats) and that it’s a positive one (there is a native Math.sign method, but it is IMO slightly easier to just check if it’s bigger than 0).

If the check fails, we finish the execution:

//...
let n = Number(input);

if (!Number.isInteger(n) || Number(n) <= 0) {
  console.log("Error: input must be a positive integer");
  return rl.close();
}
//...

But is it the best user experience? I don’t think so. I think our poor user deserves a second chance. But how can we do that?

Add recursion

We’ll apply a simple recursion. We extract our procedure to its own function, collatz, and we’ll call it over and over until our oblivious user finally inputs the right input or gives up.

What? That doesn’t sound like the best UX either? All right. We’ll give our tormented user a hint. Better than that, we’ll give him a chance to quit our script execution by typing exit.

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

function collatz() {
  rl.question("Insert a number: ", function (input) {
    if (input === "exit") return rl.close();

    let n = Number(input);

    if (!Number.isInteger(n) || Number(n) <= 0) {
      console.log(
        "Please, insert a positive integer, e.g., 7, 42, or 1234, or type 'exit' to quit."
      );
      return collatz();
    }

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

    console.log(
      `Regarding number ${Number(input)}, it seems that Collatz was right.`
    );
    return rl.close();
  });
}

rl.on("close", function () {
  process.exit(0);
});

collatz();

Great! We have our first MVP. But it is a little dull, is’t it? Let’s change it.

Add some swag

For our final product, let’s polish it a little bit. I, as an adult, like stats. Kids, on the other hand, like colors. We’ll add both. Also, I don’t like the scientific notation on the large numbers; if the number is huge, it should look huge.. Also, it wouldn’t hurt to use some numeric separators to make the numbers on the output more legible. We’ll use the Number.toLocaleString() method to achieve that.

We’ll need to install some dependencies. The first one is chalk module, which will give us the desired colors. For simplicity sake, we will not use the latest version (because it fully moved to ES modules, which brings some difficulties), but version 4. The other one is dedent module, which will fix (hopefully) the obnoxious problem with template strings indentation.

npm install chalk@4 dedent

// or

yarn add chalk@4 dedent

Now, we are equipped to make our output more colorful and informative:

const readline = require("readline");
const chalk = require("chalk");
const dedent = require("dedent");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

function collatz() {
  rl.question("Insert a number: ", function (input) {
   if (input === "exit") return rl.close();

    let n = Number(input);

    if (!Number.isInteger(n) || Number(n) <= 0) {
      console.log(
        "Please, insert a positive integer, e. g. 7, 42, 1234, or type 'exit' to quit."
      );
      return collatz();
    }

    let maxNum = 0;
    let iterations = 0;
    let evens = 0;
    let odds = 0;

    while (n !== 1) {
      maxNum = Math.max(maxNum, n);
      iterations += 1;

      if (n % 2 === 0) {
        evens += 1;
        n = n / 2;
      } else {
        odds += 1;
        n = n * 3 + 1;
      }
      console.log(
        n <= 4
          ? chalk.red(n.toLocaleString())
          : chalk.yellow(n.toLocaleString())
      );
    }

    console.log(
      chalk.green(dedent`
        =======================
        Highest number reached: ${maxNum.toLocaleString()}
        -----------------------
        Number of steps: ${iterations.toLocaleString()}
        -----------------------
        Even numbers count: ${evens.toLocaleString()}
        -----------------------
        Odd numbers count: ${odds.toLocaleString()}
        =======================
      `)
    );

    console.log(
      chalk.cyan(
        `Regarding number ${Number(input)}, it seems that Collatz was right.`
      )
    );

    return rl.close();
  });
}

rl.on("close", function () {
  process.exit(0);
});

collatz();

Another cool idea would be to output the series as a graph. Damn, let’s implement that right now!

It is actually not that hard. We need to know how wide our terminal is, and that information is stored in process.stdout.columns property. What is the point of knowing that? Because then we can display the highest number in sequence as a full-width bar, while the others will scale proportionally. Therefore, we just don’t log the actual n right away but store it in an array because we need to know the value of the biggest number before any output.

Once the sequence is done, we’ll iterate over the collected values, and after each value, we’ll display a bar that will show the ratio between the biggest number in sequence (which will take up full terminal width) and the current number. To display the bars, we’ll create arrays of characters (and join them right away). We’ll need to handle situations when some of the numbers are too small, and considering the ratio, they shouldn’t have any bars whatsoever. That would look kind of weird, so in these cases, we’ll apply a single character:

// ...

let maxNum = 0;
    let iterations = 0;
    let evens = 0;
    let odds = 0;

    let sequence = [];

    while (n !== 1) {
      maxNum = Math.max(maxNum, n);
      iterations += 1;

      if (n % 2 === 0) {
        evens += 1;
        n = n / 2;
      } else {
        odds += 1;
        n = n * 3 + 1;
      }

      sequence.push(n);
    }

    let columns = process.stdout.columns;
    let ratio = columns / maxNum;

    for (let num of sequence) {
      console.log(chalk.yellow(num.toLocaleString()));
      console.log(
        chalk.yellow(
          Math.floor(num * ratio) < 1
            ? ``
            : new Array(Math.floor(num * ratio)).fill(``).join("")
        )
      );
    }
// ...

The script can be further enhanced in numerous ways. For dealing with really large numbers, it is probably a good idea to cast all the numeric variables to a BigInt type.

For making the output more vivid, it can be cool to print the sequence with a noticeable delay, wrapping the logging functions in setTimeout().

Enjoy! 👍


If you find anything in this post that should be improved (either factually or in language), feel free to edit it on Github .