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.

I listed two solutions to this problem in Common Lisp below. alt-euler-14 strictly follows the formula and computes the solution inefficiently. euler-14 stores computed values in a hash table so it never applies the formula to the same number more than once.

;;; *collatz-table* holds the number of terms for previously performed
;;; collatz calculations.  For example, say that we already found
;;; the number of terms to compute 10, which is 7.  If we compute
;;; the number of terms for 13, as in the example above, when it
;;; reaches 10 it will find this value in the table and add 7 to
;;; the current terms value to get the answer.
(defparameter *collatz-table* (make-hash-table))

(defun collatz (num)
  (cond ((= num 1) 1)
            ((gethash num *collatz-table*)
             (gethash num *collatz-table*))
            ((evenp num)
              (setf (gethash num *collatz-table*)
                      (1+ (collatz (/ num 2)))))
             (t (setf (gethash num *collatz-table*)
                         (1+ (collatz (1+ (* 3 num))))))))

(defun euler-14 ()
  (let ((answer 0)
          (max-terms 0))
    (do ((x 1 (1+ x)))
          ((>= x 1000000) answer)
      (let ((terms-of-x (collatz x)))
         (when (> terms-of-x max-terms)
           (setf max-terms terms-of-x
                   answer x))))))

(defun alt-collatz (num &optional (term 1))
  (cond ((= num 1) term)
            ((evenp num) (alt-collatz (/ num 2) (1+ term)))
            (t (alt-collatz (1+ (* 3 num)) (1+ term)))))

(defun alt-euler-14 ()
  (let ((answer 0)
         (max-terms 0))
    (do ((x 1 (1+ x)))
          ((>= x 1000000) answer)
      (let ((terms-of-x (alt-collatz x)))
        (when (> terms-of-x max-terms)
             (setf max-terms terms-of-x
                     answer x))))))

Alt-euler-14 took 8.5 seconds. euler-14's first run took 3 seconds, but the second run took 0.28 seconds. This speed came at a cost of more memory.