/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.

Oh, ten million.

Ok that doesn't overflow on the brute force one with longs (and it takes 72.4 seconds), but it does cause Java to run out of heap pretty quickly on my Hashtable one. I can't seem to find the necessary combination of switches to give the JVM more memory to work in though.

Here's some more code (longs+hashtable):

import java.util.Hashtable;

public class World4ChProgPuzzleOpt2 {

  static Hashtable<Long, Integer> LengthCache = new Hashtable<Long, Integer>();

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

        while (!(n==1||CachedLength!=null)) {
          CachedLength = LengthCache.get(n);
          if (CachedLength != null) {
            Length = Length + CachedLength - 1;
          } else {
            if (n%2==0) {
              n /= 2;
            } else {
              n = 3*n+1;
            }
            ++Length;
          }
        }
        LengthCache.put((long)start, Length);
        return Length;
      }
    }
  }

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

    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)");


  }

}