excerpt from "nifty-funs.lisp"

nifty-funs.lisp

(defun euler-totient (n)
  "Returns the euler-totient, and the coprimes that count the totient
   for any number n"
  (let ((coprimes (loop for x from 1 to n when (= 1 (gcd x n)) collect x)))
    (values (length coprimes) coprimes)))

(defun part-k-n (k n)
  (let ((cache (make-hash-table :test #'equal)))
    (labels ((aux (k n cache)
	       (multiple-value-bind (val win) (gethash (list k n) cache)
		 (if win
		     val
		     (setf (gethash (list k n) cache)
			   (cond ((> k n) 0)
				 ((= k n) 1)
				 (t (+ (part-k-n (+ k 1) n) (part-k-n k (- n k))))))))))
    (aux k n cache))))