numbers.el

(require 'cl)

(defun find-missing (source)
  "Given a function, SOURCE, that returns a series of numbers
between 1 and n, missing one number and terminating by returning
nil, return the missing number. Runs in O(n) time and O(1) space,
provided you staty within the integer limits of your
platform (n=95533 on 32-bit)."
  (let ((sum 0)
        (max 1)
        (x 0))
    (while (setf x (funcall source))
      (incf sum x)
      (setf max (max max x)))
    (- (/ (* max (1+ max)) 2) sum)))

(defun sample-source (n)
  "Creates a number source function which outputs all of the
numbers from 1 to N in random order, then emits nil."
  (lexical-let ((list (number-sequence 1 n)))
    ;; Shuffle
    (setf list (map 'list 'identity
                    (shuffle-vector (apply 'vector list))))
    (lambda ()
      (let ((ret (car list)))
        (setf list (cdr list))
        ret))))

;;; Example Usage

(setq source (sample-source 95533))
(funcall source) ;; Remove one number and see what it is
(find-missing source)