Course: PHP

Progress (0%)

# Exercise: Collatz Conjecture

Exercise 19 Easy

Prerequisites for the exercise

1. PHP while Loop
2. All previous chapters

## Objective

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

## 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 collatz_length() that takes in the starting value of the sequence as an argument and returns back its length.

Note that if the provided argument is not a positive integer, the function must return NULL:

Here's an example of its usage:

<?php

function collatz_length( /* ... */ ) { /* ... */ }

echo 'collatz_length(3): ', collatz_length(3), "\n";
echo 'collatz_length(17): ', collatz_length(17), "\n";
echo 'collatz_length(30): ', collatz_length(30), "\n";
echo 'collatz_length(10100000): ', collatz_length(10100000), "\n";
echo 'collatz_length(false): ', collatz_length(false), "\n";
echo 'collatz_length(INF): ', collatz_length(INF), "\n";
echo 'collatz_length(2.3): ', collatz_length(2.3), "\n";
echo 'collatz_length(0): ', collatz_length(0), "\n";
collatz_length(3): 8 collatz_length(17): 13 collatz_length(30): 19 collatz_length(10100000): 133 collatz_length(false): collatz_length(INF): collatz_length(2.3): collatz_length(0):

The first three lines in the output represent the lengths of three sequences shown above, respectively.

The last four lines, however, all represent invalid values passed in to collatz_length(), to which the function returns NULL. Remember that printing NULL in PHP doesn't display anything.

## New file

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

## Solution

To start with, let's deal with the edge cases as discussed in the section above, i.e. when the given argument to collatz_length() is not an integer, and if it really is one, then is not a positive integer:

<?php

function collatz_length($n) { if (!is_int($n) || $n < 1) { 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 up to 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. 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 $n * 3 + 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 by 1.

length is 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 and the loop won't execute. Altogether, we get to the following code: <?php function collatz_length($n) {
if (!is_int($n) ||$n < 1) {
return NULL;
}

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

So wasn't this simple?

"I created Codeguage to save you from falling into the same learning conundrums that I fell into."

— Bilal Adnan, Founder of Codeguage