Problem 14: projecteuler.net: Matlab: Largest Collatz Sequence

Problem

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Using the rule above and starting with 13, we generate the following sequence:
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Solve the above problem using Matlab

Solution

Collatz sequence has already been defined in the problem section. If you want to know more about collatz sequence then click on the links below:

1) Collatz Conjecture

2) Collatz sequence

The solution is simple and we will only use the basics to solve this problem. Please have a look at the program(s) to get an idea of the program. If you are not able to understand the program then go to the explanation section below the program section. If you still can't understand the program after reading the explanation section then visit the links below to learn the basics behind the program(s).

1) tic, toc

2) for loop in matlab

3) while loop in matlab

4) if else in matlab

5) disp in matlab

6) rem function in Matlab (Remainder after division)
7) logical function in matlab
8) Functions in Matlab
9) Vectors in Matlab

Don't get scared of all these links, these are just for the reference. First have a look at the program and if you don't understand, then go to explanation section and then, if you still don't understand, then select the only link which you didn't understand in the program have a look at them and there you go, you will understand the program easily.

It should be noted here that this program has a unique characteristic: This program uses both for loop and the while loop or combination of both the for and while loop to accomplish the task.

Program

We can write the program in two ways. But out the two programs one program execution time is far less than the other. Try both the programs and comment the program number which has the less execution time. All the Matlab files has been attached at the end of each program. You can download them for free.

Program 1:

function result = even(n)

%This function will return whether the number is even or odd

if rem(n,2) == 0
    result = logical(1);
else
    result = logical(0);
end

You can download the above program in matlab file format for free from here: even.m

function result = size_collatz(x)
%this function will give the length of the collatz sequence of a given
%number using the vector
vec = [x];
while x~= 1
    if even(x)
        x = x/2;
    else
        x = (3*x)+1;
    end
    vec = [vec,x];
end
result = length(vec);

You can download this file as matlab file format for free from here: size_collatz.m

We can also write the above program (size_collatz) without using the vectors as follows:

function result = size_collatz2(x)
%this function will give the length of the collatz sequence of a given
%number
count = 0;
while x~= 1
    if even(x)
        x = x/2;
        count = count+1;
    else
        x = (3*x)+1;
        count = count+1;
    end
end
result = count+1;

You can download the above file in matlab file format for free from here: sizecollatz2.m

And the final main script for finding the number which produces the largest chain under one million is as follows:

tic;
largest = 1000000;
for i = 1:999999
    if size_collatz2(i)>size_collatz2(largest)
        largest = i;
    end
    disp(largest);
end
toc

Download the above script in Matlab file format for free from here: largest_collatz.m

To run your program you can use the scripts combinations as follows:

Combination 1
even.m
size_collatz.m
largest_collatz.m

Combination 2
even.m
size_collatz2.m
largest_collatz.m
Both of the combinations in the program 1 give results approximately at same timing. But the difference only occurs when you will use the program 2.

Program 2:

tic;
count1 = 0;
for i = 1:1000000
    x = i;
    count = 0;
    while x~=1
        if rem(x,2) == 0
            x = x/2;
            count = count+1;
        else
            x = 3*x+1;
            count = count+1;
        end
    end
    if count>count1
        largest = i;
        count1 = count;
    end
end
disp(largest)
toc

You can download the above program in Matlab file format from here: largest_collatz2.m

Once again, run the program for yourself and comment the best program you think which is giving the fastest results.

Explanation

I will explain this post program wise so that there won't be any confusion for you.
Program 1
even.m
In this program I have used the if else statement in combination with the rem function to check if the given input number is divisible by 2 or not. If the number is divisible by 2 then the number is even and thus the result returned is logical(1) or else true. Else if the number is not divisible by two then the result is logical(0) meaning false or not an even number.
size_collatz.m
Here in this function we have created a vector which stores the numbers of the collatz sequence. To understand this program let us consider the example of input as 13, then
During at first the vec value will be [13], now while loop starts as the value of 13 is not equal to 1. In the while loop the number is not even so the else statement is invoked and the value of x is changed from 13 to 40. After that 40 gets stored in the vec vector and now the vector is [13,40]. In the next iteration as the condition is satisfied(40~=1), the if statement is invoked because the 40 is even. Now the value of the x is changed from 40 to 20 and the same gets stored in the vec. The vec value here is [13,40,20]
And this continues till the end and the result we get is [13,40,20,10,5,16,8,4,2,1].
Finally at the end the length of the vec is calculated and the result is returned for processing in the next program (largest_collatz)
size_collatz2.m
In this function unlike the above function where we will create a vector and find the length of the vector, we will use a counter variable to find the length of the chain directly by increasing the counter variable for every iteration.
So coming to the program, I have created a count variable and initiated it to zero. To understand the program easily let us consider the example of 13, now,
13 is not an even number and thus the else statement is invoked and the value of x changes to 40 and the counter variable 'count' increases to 1, in the next iteration the value of x changes from 40 to 20 and the counter variable changes its value to 2 and this iterations continue till the value of x changes to 1 and thus here in this example,the counter variable changes to 9, Finally after all the iterations the 1 is added to the value of the count variable because in the starting of the program we haven't calculated the value of the 13(in this example). Thus the result is 10 and this is returned for further processing.
largest_collatz.m
In this program initially we have created tic to start the clock so that at the end of the program where we have toc to end the clock and thus we can find the time of execution.
we have created largest = 1 million
Now the for loop starts and the if statement checks if the size of the collatz sequence of the collatz of the iterator is greater than the size of the collatz of the largest then the largest is replaced with the iterator variable, so that at the end of all the iterations the largest will be the answer. This can be assumed as if you are larger than me then I have to go out, if some other person is larger than you, you have to go out and give the place, if some other is larger then that person will stay and other will go out. And similarly the larger will stay and others will go out. "Survival of the largest!!"
Finally at the end of the for loop the toc gets executed and the value of the largest and the time of execution is given as output.
largest_collatz2.m
This program is very simple. In this program instead of having different functions, I have combined all the programs in one script and the result is largest_collatz2.m . Now lets us see the program:
First the tic is started to start the stop watch.
count1 = 0
In the for loop the value are iterated from 1 to 1 million.
Now a variable 'x' is created to store the value of i.
count is initiated to 0;
A while loop checks the conditions and the count variable is increased for every iteration until the value of x is 1. And after the while loop iterations are over an if statement is initiated to check is the value of the previous count(count1) is greater than the count of the present variable(count) and if it is greater then the largest is the i(iterator).
"The same principle of the survival of the largest applies here".
Finally the value of largest is displayed using the disp.
And the toc is initiated to stop the stopclock and the the value of the time of execution is also displayed.

I have tried to explain the program in a easy to understand fashion. If you have any doubt or didn't understand the program then please contact me so that it will be useful for you and also others. You can contact me from here: contact me

References

1) Project euler problem 14 - Jasons code blog

2) Project euler 14: Longest collatz sequence - mathblog

All the above programs have been high lighted using hilite.me

The problem has been taken from projecteuler.net from here: problem 14-project euler

Keywords: even number,odd number, matlab functions, projecteuler.net, size of collatz, largest collatz less 1 million