My favorites | Sign in
Project Home Downloads Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
DJCollatz  
Provides overview of the problem, and the proposed solution.
Updated Jun 12, 2009 by joys...@gmail.com

Introduction

The Collatz conjecture is as follows:

Given a series,

a(n) = a(n-1)/2 ; when a(n-1) is even

3a(n-1) + 1 ; when a(n-1) is odd

converges to '1' for all positive a(n).

The problem 3n+1 solved here is to compute the maximum cycle length (the # of oscillations before a(n) converges to 1) given a range of numbers.

Details

Solution Approach

We herein have used a cache, which stores the cycle length of each number (within the range) provided it is below a certain MAX_SIZE.

const int MAX_SIZE = 250000;  //defines the cache size
int cache[MAX_SIZE] = {0};    //constructs cache as array of MAX_SIZE
                              //initializes all elements to 0

The cycle length is then calculated recursively by calling cycleLength(k). If the cycle length of 'k' is already computed and stored in the cache, it is returned to the calling function; else the cache is populated with the cycle length of the new 'k' at the corresponding index 'k-1.'

/** 
 * computes cycle length
 * We have assumed that no operation will result into an overflow of 32-bit int.
 * NOTE: using 'long long int' will compile without '-pedantic' 
 * and will cover the range of all the cyclelengths for  1-999999
 * @param  int k which is the previously computed series value
 * @return int cycleLength for a given k > 0; else assertion fails
 */

int cycleLength( int k ) 
{
    int cyclen;
    
    /* if k <= MAX_SIZE and cache already contains cycle length for k */
    if ( ( k <= MAX_SIZE ) && cache[k - 1] != 0 )
    {
        return cache[k-1];
    }
    else			
    {
        if ( k == 1 )
        {
            cyclen = 1;
        }
        else
            if ( (k % 2) == 0 )
            {
                cyclen = cycleLength(k/2) + 1;		//recursive call
            }
            else
            {
                cyclen = cycleLength(3 * k + 1) + 1;
            }
             
        if ( k <= MAX_SIZE )
            cache[k - 1] = cyclen;					//populate cache
     
	return cyclen;
    }
}

Different Alternatives Considered

Preliminary Approach

The basic idea is to build a simple 'for loop' and calculate the cycle length of each number in the range given as the input.

Pros: Simple algorithm

Cons: Time inefficient

Eager Caching

Using a cache to store the powers of 2 upto 2^32, and using the (index + 1) as the cycle length.

Expected pros: Time efficient

Actual cons : Quite contrary -- UVa prompted "Time Exceeded"

Consequently, even being eager, we had to resort to the lazy caching approach described above!

Powered by Google Project Hosting