Paul Waring

Project Euler problem 14

Longest Collatz Sequence

Find the longest Collatz Sequence for 1 <= x₁ < 1,000,000, where:.

• If x_n is even, x_n+1 = x_n / 2
• If x_n is odd, x_n+1 = 3x_n + 1

A sequence ends when x_n = 1. All sequences are believed to end in 1, although this is unproven (for the purposes of this problem it is true for all the numbers we will look at).

Solution

First we need a function which calculates the length of a sequence for a given start number. This is straightforward as we only need a loop with a single terminating condition (x_n = 1) and a test for evenness (divide by two, no remainder) so we can calculate the next number.

int collatz_length(int start) {
    int length = 1;
    int64_t current = start;

    while (current != 1) {
        if (current % 2 == 0) {
            current = current / 2;
        } else {
            current = (current * 3) + 1;
        }

        length++;
    }

    return length;
}

One thing to be aware of is that the individual terms in a sequence may exceed the start number. For example, if we start at 13, the maximum term in the sequence is 40. If we only use a 32 bit integer, this will overflow when we reach a start number of 11383, and end up as a negative number. In this case it is very unlikely that the number will ever get back to 1, and therefore we will have an infinite loop. We must therefore use a 64 bit integer to store the current term, even though the start and length integers only need to be 32 bits (16 bits would be insufficient).

We can then call this function for every number from 1 to 999,999, remembering the longest length.

The full solution is:

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

#define MAX_START 1000000

static int collatz_length(int start) {
    int length = 1;
    int64_t current = start;

    while (current != 1) {
        if (current % 2 == 0) {
            current = current / 2;
        } else {
            current = (current * 3) + 1;
        }

        length++;
    }

    return length;
}

int main() {
    int current_start = 0;
    int longest_chain = 0;
    int current_chain = 0;
    int longest_chain_start = 0;

    for (current_start = 1; current_start < MAX_START; current_start++) {
        current_chain = collatz_length(current_start);

        if (current_chain > longest_chain) {
            longest_chain = current_chain;
            longest_chain_start = current_start;
        }
    }

    printf("%d\n", longest_chain_start);

    return EXIT_SUCCESS;
}          

Note that the collatz_length function has been made static to indicate that it is not called from outside this compilation unit.