Problem Solving: Verifying Conjecture

Learn to write a program that takes a stream of numbers (numbers ending with a delimiter) and finds out the number having a maximum length Collatz sequence.

We'll cover the following

There are so many mathematical claims which sometimes can be intuitively simulated and validated through computational programs. We will be working on one such example in this lesson.

The Collatz conjecture (3n+1-conjecture)

The Collatz conjecture is a famous mathematical conjecture which says;

  • Take any positive non-zero integer n.

  • If n is an even number, shrink it by dividing it by two, i.e., n = n/2.

  • If it is an odd number, multiply it by three and add 1 to it, i.e., n = 3n+1.

Claim: This change in the value of n is generating a sequence and it will always lead to 1. For example, for n = 3, the generated sequence will be 3, 10, 5, 16, 8, 4, 2, 1. We call 3 to generate the 3n+1 sequence of length 8.

The Collatz conjecture is one of the most amazing conjectures which is yet to be proven mathematically.

Validating the Collat-z conjecture on a range

Let’s create a program that takes a stream of numbers (where the stream will end with -1) as input and calculates which number has the highest Collatz sequence length.

Sample input

5 7 6 -1

Sample output

7

Explanation: Here is the following sequence generated by each number:

  • Collatz sequence for 5: 5, 16, 8, 4, 2, 1
  • Collatz sequence for 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
  • Collatz sequence for 6: 6, 3, 10, 5, 16, 8, 4, 2, 1

Hence the maximum sequence is generated by 7.

Implementation details

Let’s write a piece of code that, on a specific integer n, generates (changes values in n) a sequence following the rules of even (shrinking step n=n/2) and odd (expanding step n=3*n+1). The sequence stops when n has the value 1.

Press + to interact
while(n!=1)
{
     if(n%2 ==0) // if number is even
        n/=2;
     else        // if number is odd
         n=3*n+1;
}

Let’s think for a moment. How can we augment the above code to find out the sequence length generated on a given integer value?

Yes! We can count how many times this while loop has been executed.

Let’s make a function that finds the count of the generated Collatz sequence. We will call it CollatzSequenceLength().

Press + to interact
int CollatzSequenceLength(int n)
{
    int count=0;
    while(n!=1)
    {
        if(n%2 ==0)
            n/=2;
        else
            n=3*n+1;
        count++; 
            //increment in count after each step in sequence
    }
    return count;  // return sequence count of a number
}
/* 
THINK: 
   What can we do to print the sequence along too?
   For example: for n = 7 
   The sequence will be: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 
   The Sequence Length will be: 17
*/

Now, we want to find out the maximum sequence-generating number from the given stream.

Here is the sketch of the program:

  1. We will maintain maxCollatzSequenceLength and maxSequenceNumber, initially having the values 0 and -1.

  2. Input the number num if it is not the end of the stream.

  3. Measure the Collatz sequence length for a given number and store it in the variable count.

  4. If the new count is greater than maxCollatzSequenceLength, we update maxCollatzSequenceLength = count and maxSequenceNumber=n.

  5. Repeat steps 2 to 4 until the end of the stream.

    • In case of the end of the stream, return maxSequenceNumber of the maxCollatzSequenceLength.

Let us write our program by translating our sketch into code.

int maxCollatzSequenceGeneratingNumber()
{
    int num, count = 0;
    int maxCollatzSequenceLength = 0, maxSequenceNumber =- 1;
    while(true)
    {
        // taking the numbers from the user until -1
        cin >> num;
        if(endOfStream(num))
        {
            return maxSequenceNumber;
        }
        count=CollatzSequenceLength(num); // return the sequence count of conjecture number 
        
        if (count > maxCollatzSequenceLength)
        {
            maxSequenceNumber = count; 
              // maintain maximum count in max variable
            maxSequenceNumber= num; //maintain actual number in result that has maximum conjecture 
        }
    } 
}
ThemaxCollatzSequenceGeneratingNumber() function

Complete implementation

Here is the complete code.Read it and experiment with it with several input stream values. We highly recommend the step-by-step execution of the program to see if it’s working. After understanding it, do the follow-up exercise.

Instruction: Enter a similar list of numbers like 10 19 17 21 23 -1. For debugging the program, you may use this playground.

#include <iostream>
using namespace std;
int CollatzSequenceLength(int n)
{
    int count=0;
    while(n!=1)
    {
        if(n%2 ==0)
        {
            n/=2;
        }
        else
        {
            n=3*n+1;
        }
    count++;
    }
    return count;
}
int maxCollatzSequenceGeneratingNumber()
{
    int num = 0,count=0,result;
    // max variable initialized with the first number
    int max = num;
    cout << "Stream ending with -1(e.g. 10 19 17 21 23 -1): ";
    cin >> num;  // Number Stream e.g. 10 19 17 21 23 -1
    do
    {
        count=CollatzSequenceLength(num);// return the sequence count of conjecture number 
        if (count > max)
        {
            max = count;// maintain maximum count in max variable
            result= num;//maintain actual number in result that has maximum conjecture
        }
        // taking the next number out from the stream
        cin >> num;
    } 
    while(num!=-1);
    return result;
}
int main()
{
    int result=maxCollatzSequenceGeneratingNumber();
    cout<<"Maximum sequence is by :"<<result;
    return 0;
}
Complete implementation of maximum the Collatz sequence

Exercise: Printing the Collatz with the sequence length

Modify the above playground’s program so that the above program should also print the sequence of each number along with its sequence length.

Hint: Modify the CollatzSequenceLength() function so that now the program not only returns the count of the Collatz sequence of length n but also, prints the sequence, i.e., the values of n.

Here is a sample program:

A number stream (ending with -1): 10 19 17 21 23 -1
---------------------------------------------------
The Collatz's sequence of 10 : 10 5 16 8 4 2 1 
The Collatz's sequence length of 10 is: 6

The Collatz's sequence of 19 : 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
The Collatz's sequence length of 19 is: 20

The Collatz's sequence of 17 : 17 52 26 13 40 20 10 5 16 8 4 2 1 
The Collatz's sequence length of 17 is: 12

The Collatz's sequence of 21 : 21 64 32 16 8 4 2 1 
The Collatz's sequence length of 21 is: 7

The Collatz's sequence of 23 : 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 
The Collatz's sequence length of 23 is: 15

Maximum sequence is by :19

Instruction: Add the code in the above playground for this exercise.