/prog/ Challenge

Hey, I've stolen this challenge from some website, it's pretty easy but I know most of you will fuck it up.

A sequence is defined by:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Find the longest sequence, with a starting number under one million.

Bonus points when you find the solution for ten million.

I just realised how stupid I was using a hashtable. I mean, what the fuck? Completely retarded data structure for this application. This next one just allocates a huge array instead.

Average 0.34 seconds for one million items and 4.0 seconds for ten million. Here's the code:

public class World4ChProgPuzzleOpt3 {

  static int[] LengthCache;
  static final int UpperLimit = 1000000;

  private static int calculateSequenceLength(int start) {
    switch(start) {
    case 1:
    case 2:
    case 4:
      return 3;
    default:
      {
        int Length = 1;
        int CachedLength = 0;
        long n = start;

        while (!(n==1||CachedLength!=0)) {
          if (n<=UpperLimit) {
            CachedLength = LengthCache[(int)n-1];
          }
          if (CachedLength != 0) {
            Length = Length + CachedLength - 1;
          } else {
            if (n%2==0) {
              n /= 2;
            } else {
              n = 3*n+1;
            }
            ++Length;
          }
        }
        LengthCache[start-1] = Length;
        return Length;
      }
    }
  }

  public static void main(String[] args) {
       
    int LongestSequenceLength = 0;
    int CurrentSequenceLength;
    long StartTime = System.currentTimeMillis();

    LengthCache = new int[UpperLimit];

    for (int n=1; n<=UpperLimit; n++) {
      CurrentSequenceLength = calculateSequenceLength(n);
      if (CurrentSequenceLength > LongestSequenceLength) {
        LongestSequenceLength = CurrentSequenceLength;
      }
    }
   
    long ElapsedTime = System.currentTimeMillis()-StartTime;

    System.out.println("Longest sequence for numbers up to " + UpperLimit + " is " +

LongestSequenceLength);
    System.out.println("(took "+ElapsedTime+"ms to run)");


  }

}