Project Euler #14 - C

Question:

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:
Anytime I am asked to find some maximum under some limit, in this case the longest chain produced by a number under 1,000,000, I assume the best way to tackle the problem is a decrementing for loop. However, applying this iterative sequence to 1,000,000 integers is not the best way to solve this problem. 


Lets take the number 500,000 for example. Obviously, this number is going to have some massive chain stemming from it... 250,000 -> 125,000 -> 62,500 . Something important can be realized from this observation: the chain for 250,000 is a subset of the chain of 500,000, the chain of 125,000 is a subset of 250,000, and so on. This can be imagined to be equivalent to those little russian dolls which fit inside one another. Luckily, this greatly simplifies the problem. 


Starting from the top, subsets can packaged up and thrown out as the sequence progresses. To do this, create an integer array (numbers[0] = 1, numbers[1] = 2, ... numbers[999999] = 1000000) and during each iteration of the sequence, if an integer is produced which is between 1 and 1,000,000, the corresponding entry in the array can be set to 0 and ignored as a starting point in subsequent iterations. 


So, the algorithm is fairly simple:
1) Apply the iterative sequence to a starting number. 
2) Zero the corresponding entries in the integer array during each iteration of the sequence. 
3) Also, count the number of iterations in the sequence. 
4) If the number of iterations exceeds the current number of most iterations, replace the number with the most iterations with the current number. 
5) Find the next starting number by finding the next non-zero entry in the integer array. 


On my machine, this algorithm solved this problem consistently around .7 seconds. 



#include <stdio.h>
#define LIMIT 1000000


static int numbers[LIMIT] = {0};


int main (void)
{
int high_chain = 0;
int high_num = 0;
int chain_length = 0;
int curr_num = LIMIT;


/* Populate numbers array with 1-LIMIT*/
int i;
for (i = 0; i < LIMIT; i++)
numbers[i] = i + 1;


for (curr_num = LIMIT; curr_num > 1; curr_num--)
{
if (numbers[curr_num-1] == 0)
continue;


chain_length = 0;

long long temp_num = curr_num;

while(temp_num != 1)
{
if (temp_num < LIMIT)
numbers[temp_num-1] = 0;


if (temp_num & 0x1) // odd
temp_num = temp_num * 3 + 1;
else // even
temp_num >>= 1;


chain_length ++;
}


if ( chain_length > high_chain ) 
{
high_chain = chain_length;
high_num = curr_num;
}
}


printf("The number with the longest chain under %d is %d\n", LIMIT, high_num);
return 1;
}