My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
CollatzProjectWiki  
Updated Jun 11, 2011 by modx...@gmail.com

Introduction

Given two positive integers specifying an inclusive range, this program computes the maximum cycle length of integers within that range. For example, given integers i and j, the range specified is [min(i,j) max(i,j)].

The Collatz cycle begins with a positive integer x and begins recursively mapping the previous integer (call it n) in the cycle to: 3n+1 if n odd, and n/2 if n even. Given any positive integer x below 1,000,000, the cycle has been shown to terminate at 1 after finitely many steps. We call the number of steps it takes to terminate the Collatz cycle beginning at a number x the "Collatz cycle length of x."

Note: this function can compute the cycle length of any number whose cycle contains integers capable of being stored in a Java int (32-bit). In this particular case, the range of suitable integers is [1,113382]. Basic approach

The algorithm essentially loops through each number within the range and computes that number's Collatz cycle length. If that cycle length is larger than the maximum cycle length seen previously in the loop, the output variable (storing the total maximum cycle length) is updated to reflect this new number.

To compute the Collatz cycle length for a given number x, the algorithm starts with x, computes the next number in the cycle (as stated in the Introduction), and iterates the cycle length counter by 1. Details

Three major optimizations have been made to the somewhat naive approach outlined above:

  • if the specified range is [i,j] and i < j/2 then the maximum cycle length of [i,j] will be the same as [j/2,j]. This allows us to narrow our range of interest a bit and save some loop iterations.
  • while iterating through the collatz cycle for a certain number x, if x is odd then two steps may be performed at once: the next number is (3*x+1)/2 and the cycle counter is thus incremented by 2.
  • a cache of pre-computed cycle lengths for all integers within [107000,113382]. If the specified range in the input contains any number within this range, the collatz cycle length for those numbers is immediately accessible, thus speeding up computational time given a range including larger integers. The cache was constrained by the fact that UVa allows source files up to 40kb, and this cache was the largest possible given that fact. I chose to store cycle lengths for larger integers since those numbers tend to have larger cycle lengths (and thus take more time to compute).
Powered by Google Project Hosting