These two sequences of positive integers are defined as:

 







R
(
1
)



=
1
 
;
 
S
(
1
)
=
2




R
(
n
)



=
R
(
n
−
1
)
+
S
(
n
−
1
)
,

n
>
1.






{\displaystyle {\begin{aligned}R(1)&=1\ ;\ S(1)=2\\R(n)&=R(n-1)+S(n-1),\quad n>1.\end{aligned}}}




The sequence 



S
(
n
)


{\displaystyle S(n)}

 is further defined as the sequence of positive integers not present in 



R
(
n
)


{\displaystyle R(n)}

.

Sequence 



R


{\displaystyle R}

 starts:

   1, 3, 7, 12, 18, ...

Sequence 



S


{\displaystyle S}

 starts:

   2, 4, 5, 6, 8, ...



Task

 Create two functions named ffr and ffs that when given n return R(n) or S(n) respectively.
(Note that R(1) = 1 and S(1) = 2 to avoid off-by-one errors).
 No maximum value for n should be assumed.
 Calculate and show that the first ten values of R are:
 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69
 Calculate and show that the first 40 values of ffr plus the first 960 values of ffs include all the integers from 1 to 1000 exactly once.


References

 Sloane's A005228 and A030124.
 Wolfram MathWorld
 Wikipedia: Hofstadter Figure-Figure sequences.


;;; equally doable with a list
(flet ((seq (i) (make-array 1 :element-type 'integer
			      :initial-element i
			      :fill-pointer 1
			      :adjustable t)))
  (let ((rr (seq 1)) (ss (seq 2)))
    (labels ((extend-r ()
		       (let* ((l (1- (length rr)))
			      (r (+ (aref rr l) (aref ss l)))
			      (s (elt ss (1- (length ss)))))
			 (vector-push-extend r rr)
			 (loop while (<= s r) do
			       (if (/= (incf s) r)
				 (vector-push-extend s ss))))))
      (defun seq-r (n)
	(loop while (> n (length rr)) do (extend-r))
	(elt rr (1- n)))
 
      (defun seq-s (n)
	(loop while (> n (length ss)) do (extend-r))
	(elt ss (1- n))))))
 
(defun take (f n)
  (loop for x from 1 to n collect (funcall f x)))
 
(format t "First of R: ~a~%" (take #'seq-r 10))
 
(mapl (lambda (l) (if (and (cdr l)
			   (/= (1+ (car l)) (cadr l)))
		    (error "not in sequence")))
      (sort (append (take #'seq-r 40)
		    (take #'seq-s 960))
	    #'<))
(princ "Ok")