Collatz Problem

FINDING THE MAXIMUM COLLATZ SEQUENCE BELOW ONE MILLION

The collatz sequence for a positive integer can be defined by the rules below

n=n/2 (for even number) and n = 3n+1 (for odd number)

for example: starting with 17 and using the rules above we can form a sequence

17 => 52 => 26 => 13 => 40 => 20 => 10 => 5 => 16 => 8 => 4 => 2 => 1 (13 terms for 17).

Now if we want to find a positive integer below one million with a longest number of term, we can simply follow the rules and find which number has a maximum terms. The other faster solution will be

Steps: If we want to find 17 alone, we can simply follow the rules and find the number of terms, but if we are starting from 1 to find all the positive integers (below one million) by the time we reach 17 we would have already found the number of terms for 13 (which is the first term to be less than 17) which is 10. So the number of terms for 17 will be 3+10. That is the idea implemented in the below code.

The positive integer 837799 has the maximum number of terms of collatz sequence below one million

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <math.h>

/*

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

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

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

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.

*/

// The answer is

// 837799

int collatz_sequencecount(int the_num,int *seqcount_list);

bool IsDivisible_dbl(double *dividend, int *divisor);

int main()

    // Collatz Sequence

    int *sequence_count,the_seq;

    int i;

    int max_sequence = 0;

    sequence_count = (int *)malloc(1*sizeof(int)); // Add 1 size to the sequence count list

    for(i=1;i<2000000;i++)

        *(sequence_count+(i-1))=collatz_sequencecount(i,sequence_count);

        // Increase the size of the array

        int *temp = (int *)realloc(sequence_count,(i+1)*sizeof(int));

        if(temp != NULL)

            sequence_count = temp;

        else

            printf("Error Allocating Space");

        if (max_sequence<(*(sequence_count+(i-1))))

            the_seq = i;

            max_sequence = (*(sequence_count+(i-1)));

    printf("%d => %d\n",the_seq,max_sequence);

    return 0;

int collatz_sequencecount(int the_num,int *seqcount_list)

    int seq_count = 1;

    double modify_num = the_num; // modify_num has to be double as it can go higher than int limit

    // Check the num is odd or even

    int Mom_even = 2;

    while(modify_num!=1)

        if(IsDivisible_dbl(&modify_num,&Mom_even)==true)

            //It is even

            modify_num = modify_num/2;

            if(modify_num<the_num)// If modified number is less than initial value then we already have it in the list

                seq_count = seq_count + (*(seqcount_list+((int)modify_num-1))); // If the sequence count is already in the list then we can just refer to

                break;

            else

                seq_count++;

        else

            //It is odd

            modify_num = (modify_num*3)+1;

            seq_count++;

    return seq_count;

bool IsDivisible_dbl(double *dividend, int *divisor)

    double remainder =(*dividend)- (double)(floor((*(dividend)/(*(divisor))))*(*divisor));

    if(remainder == 0)

        return true;

    else

        return false;

Google Sites

Report abuse