Question: How to optimise Lisp

puzzle

(defun expotential-divisors (n expot)
  (reverse (loop
              for y from 1 upto n
              for x = 1 then (* x expot )
              collect x)))

(defun expot-len (n)
  (1- (expt 2 n)))

(defun calc-base (n divs a b)
  (loop for d in divs
     sum (if (zerop (floor (/ n d)))
                     a
                     b)
     do (if (>= n d) (setf n (rem n d)))))

(defun puzzle (n a b)
  (let* ((divs (expotential-divisors n 2))
         (res) (found))
    (loop for x from 0 to (expot-len n)
       do (progn
            (setf res (calc-base x divs a b))
            (unless (search (list res) found)
              (push res found)
              (format t "~a " res ))))))

(defun find-values (n a b)
  (puzzle (1- n) a b)
  (terpri))

;;; running 
(find-values 3 2 1)
;;; should give:
4 3 2 

;;; there are problems with values of n above 20
;;; (find-values 25 2 1)
;;; Lisp begins to choke

(unless (search (list res) found) (push res found) ... ) -> (pushnew res found)

Anyway, use MEMBER instead of SEARCH.

In https://gist.github.com/dimitri/d5120b069e601edc312a you will find a solution that does not choke at all on your problem size:

MANASA-AND-STONES> (time (solve (make-manasa :stones 25 :a 2 :b 1)))
Evaluation took:
  0.000 seconds of real time
  0.000015 seconds of total run time (0.000014 user, 0.000001 system)
  100.00% CPU
  30,055 processor cycles
  0 bytes consed

(24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48)