[C/C++] Project Euler #14 Longest Collatz Sequence(Dynamic Programming)

Problem Description:
This problem involves finding the starting number below one million that produces the longest sequence when generating a Collatz sequence.

The Collatz sequence is defined by the following rules:

 

1. For a given integer n :
• If n is even, divide it by 2 ( n = n / 2 ).
• If n is odd, multiply it by 3 and add 1 ( n = 3n + 1 ).

 

2. The sequence ends when n = 1 .

For example, starting with the number 13, the sequence generated is:
\[ 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \]
This sequence contains 10 terms.

The goal is to determine the starting number below one million that generates the longest Collatz sequence and to find the length of that sequence.

 

This problem can be most effectively solved using dynamic programming.

When calculating the Collatz sequence, there are instances where we may encounter a chain length that has already been computed. Without optimization, if the chain length averages around 100 terms and we calculate for all numbers up to 1,000,000, the computation could reach approximately 100 million steps. By using dynamic programming, we can significantly reduce this number. This is, of course, based on the assumption that the sequence eventually reaches 1, which so far has had no exceptions.

 

Mathematically, if we confirm that all numbers up to 1,000,000 are part of a Collatz sequence, we know that eventually, dividing by n/2 will ensure the number decreases, guaranteeing a valid sequence. While a pure mathematical proof of this is elusive, empirical evidence supports the assumption.

 

Although numbers may grow significantly due to repeated occurrences of odd numbers (leading to the 3n+1 operation), the result of 3n+1 always becomes even, so consecutive odd numbers are not possible. With this in mind, I initially thought it would be feasible to use a 32-bit integer ( int32 ) to handle numbers below 1,000,000. However, the program encountered an error where values became negative, leading me to use a 64-bit integer ( int64 ) instead. I’m unsure whether uint32 would suffice, but int64 resolved the issue.

 

Since creating an excessively large array is impractical, I set a maximum limit ( MAXDP ) for storage. For numbers exceeding MAXDP , their chain lengths are not stored. I considered optimizing further by storing only odd numbers, given that even numbers reduce quickly. However, this approach would have complicated the program unnecessarily, so I decided to finalize it at this stage.

Collatz sequence

 

Below is the source code I wrote.

//------------------------------------------------
//    Project Euler #14 - Longest Collatz Sequence
//        - by Aubrey Choi
//        - created at 2014-12-30
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    MAXDP    5000000

int getchains(int64_t n);

int solve1()
{
    int max = 1, k = 1;

    for( int i = 2 ; i < 1000000 ; i++ )
    {
        int c = getchains(i);
        if( c > max ) max = c, k = i;
    }
    printf("Ans = %d (%d)\n", k, max);
}

int getchains(int64_t n)
{
    static int chain[MAXDP];

    if( n == 1 ) return 1;
    if( n >= MAXDP )
    {
        if( n%2 ) return getchains(3*n+1)+1;
        else return getchains(n/2)+1;
    }
    if( chain[n] ) return chain[n];
    if( n%2 ) return chain[n] = getchains(3*n+1)+1;
    else return chain[n] = getchains(n/2)+1;
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}