Objective

Create a function to determine the length of a sequence of numbers obtained via the Collatz conjecture, ending at ::1::.

Difficulty

Easy

Description

One of the simplest yet extremely complicated to prove concepts in mathematics is that of the Collatz conjecture, proposed in 1937 by Lothar Collatz.

It's known as a conjecture (contrary to a theorem) because over all these years of mathematical revolution, no one has been able to prove it. Yes, no one!

The Collatz conjecture can be described as follows:

Take any positive integer ::n::. If it's even, divide it by ::2:: to obtain the next integer. Or else, multiply by ::3:: and then add ::1:: to obtain the next integer. Continue this process.

It's widely believed that for any starting integer, the whole sequence of integers eventually reaches ::1::.

And this is the conjecture: that we'd eventually reach the integer ::1:: no matter which starting integer we use.

The Collatz conjecture has been tested for a humongous array of numbers. It has been shown that the conjecture holds for all positive integers approximately up to the value ::2^{68}:: (that's a huge huge huge number!).

Anyways, let's consider some examples.

Here's the sequence of integers starting at ::3::, up to the point we reach ::1:::

::3,10,5,16,8,4,2,1::

Here's the sequence of integers starting at ::17::, once again up to the point we reach ::1:::

::17,52,26,13,40,20,10,5,16,8,4,2,1::

Here's the sequence of integers starting at ::30:::

::30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1::

And you can try it for any other positive integer yourself! See how far does the sequence go.

Now consider the sequence of integers starting at a given positive integer ::n:: and ending at ::1::, whereby every subsequent element is obtained by performing the rules mentioned above. The length of this sequence is simply the total number of elements in the sequence.

For instance, the length of the sequence that begins at ::3:: is ::8:: (as there are a total of 8 elements in it). Similarly, the length of the sequence that begins at ::17:: is ::13::.

In this exercise, you have to create a function called collatzLength() that takes in the starting value of the sequence as an argument and returns back its length.

Note that if the provided argument is any of the following, the function must return null:

  • Not a number, for e.g. 'Hello'.
  • The special number NaN.
  • The special numbers +Infinity or -Infinity.
  • A non-integral number, for e.g. 10.2.
  • Not a positive integer, for e.g. 0, -1.

Here's an example of its usage:

collatzLength(3)
8
collatzLength(17)
13
collatzLength(30)
19
collatzLength(10100000)
133
collatzLength(false)
null
collatzLength(Infinity)
null
collatzLength(2.3)
null
collatzLength(0)
null
View Solution

New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-24-Collatz-Conjecture and put the .html solution files for this exercise within it.

Solution

To start with, let's deal with the edge case as discussed in the section above, i.e. when the given argument to collatzLength() is not a positive integer:

function collatzLength(n) {
   if (typeof n !== 'number' || isNaN(n) || !isFinite(n)
   || parseInt(n) !== n || n < 1) {
      return null;
   }
}

If n is not a number, or is a number but NaN, or not finite (i.e. is +Infinity or -Infinity), or not an integral number, or less than 1, then it doesn't count as a positive integer. Hence, we return null.

Amazing.

Coming to the actual logic of the function, one thing is clear that we need a loop in order to iterate from the given number n upto 1.

But which loop to use?

Well, verily, we need the while loop because the situation at hand doesn't require a basic counting loop, with a known number of iterations. In other words, we don't know how long would the sequence run until we reach 1. Hence, this is a perfect scenario for while.

With the loop decided, let's now talk about the loop's condition.

Iterations ought to be performed as long as the given integer n doesn't become 1. Hence the condition of iteration becomes n !== 1.

So far, so good.

Moving on, inside the loop, we just ought to implement the two rules as stated in the description above. That is, if n is even, we set it to n / 2. Otherwise, we set it to 3 * n + 1.

A variable length, initialized to 1, serves to hold the length of the sequence which will ultimately be returned by the function. During each iteration of the loop, it is incremented.

It's initialized to 1 because the least value of n could be 1 and in that case, the length of the sequence of numbers would be 1.

Altogether, we get to the following code:

function collatzLength(n) {
   if (typeof n !== 'number' || isNaN(n) || !isFinite(n)
   || parseInt(n) !== n || n < 1) {
      return null;
   }

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

   return length;
}

Simple. Isn't this?