>>164 Common Lisp

(defun f (n)
(let* ((l (reverse (list 0 1 2 3 6 12 23)))
(llen (length l))
(a 1) (b 2))
(loop for i from 0 below (- n llen)
do (push (- (* (car l) 2) b) l) (let ((c a)) (setq a b) (setq b (+ b c))))
(if (< n llen) (nth (1- n) (reverse l)) (car l))))

(loop for i from 1 to 10 collect (f i))
(0 1 2 3 6 12 23 44 85 165)

(length (format nil "~A" (f 100)))
30
(f 100)
178263365792396611930180634305

(length (format nil "~A" (f 1000)))
301
(f 1000)
15068089788556884200837227252406275461019755164609
06635467773983645806165644441422256060220226175048
15438210583985091319581712489295286782219515928380
05401737218723110358276833903488019327945469306820
43784151439006799226471757474685843965850035847511
56061127007446991905868118479501067774407042212650
5

(length (format nil "~A" (f 10000)))
3010