Project Euler Solution 14

Problem Statement#

Find the longest sequence using a starting number under one million.

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.

Solution#

This problem is very simple. But if we try to find the chain length by finding the entire sequence for a number, it takes a very long run time. The solution is to memoize the chain length of a number whenever a chain length is found. This reduces the cost of finding the entire sequence as the number grows larger.

The table below shows the sequence and chain length of numbers below 10.

Number	Sequence	Chain Length
1	1	1
2	2→1	2
3	3→10→5→16→8→4→2→1	8
4	4→2→1	3
5	5→16→8→4→2→1	6
6	6→3→10→5→16→8→4→2→1	7
7	7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1	17
8	8→4→2→1	4
9	9→28→14→7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1	20
10	10→5→16→8→4→2→1	6

From the table, it is clear that

Chain length of 10 : 1+ chain length(5) = 1 + 5 = 6

Chain length of 9 : 3 + chain length(7) = 3 + 17 =20

Chain Length of 8 : 1 + chain length(4) = 1 + 3 = 4

etc,.

Now the problem is very clear and so we can solve easily.

Implementation#

#include <stdio.h>
int MAX_NUM = 1000000;int chainLength[1000000] = { 0 };long long int num;int i, count, starting_num, new_count;
int main(){    count = 0;    for (i = 1; i < MAX_NUM; i++)    {        num = i;        new_count = 1;        while (num != 1)        {            new_count++;            if (num % 2 == 0)            {                num = num / 2;            }            else            {                num = (3 *num) + 1;            }            if (num >= MAX_NUM) continue;            if (num < i)            {                new_count += (chainLength[num] - 1);                break;            }        }        chainLength[i] = new_count; //memoizing the chain lenght        if (count < new_count)        {            count = new_count;            starting_num = i;        }    }    printf("%d", starting_num);    return 0;}

Sample Output#

Sample Output