Hofstadter Figure-Figure sequences

Hofstadter Figure-Figure sequences is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

These two sequences of positive integers are defined as:

${\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)$ is further defined as the sequence of positive integers not present in $R(n)$.

Sequence R starts: 1, 3, 7, 12, 18, ...
Sequence S starts: 2, 4, 5, 6, 8, ...

Task:

1. 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).
2. No maximum value for n should be assumed.
3. Calculate and show that the first ten values of R are: 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69
4. 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.

Common Lisp

<lang lisp>;;; 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")</lang>output<lang>First of R: (1 3 7 12 18 26 35 45 56 69) Ok</lang>

Python

<lang python>def ffr(n):

   if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
   try:
       return ffr.r[n]
   except IndexError:
       r, s = ffr.r, ffs.s
       ffr_n_1 = ffr(n-1)
       lastr = r[-1]
       # extend s up to, and one past, last r 
       s += list(range(s[-1] + 1, lastr))
       if s[-1] < lastr: s += [lastr + 1]
       # access s[n-1] temporarily extending s if necessary
       len_s = len(s)
       ffs_n_1 = s[n-1] if len_s > n else (n - len_s) + s[-1]
       ans = ffr_n_1 + ffs_n_1
       r.append(ans)
       return ans

ffr.r = [None, 1]

def ffs(n):

   if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")
   try:
       return ffs.s[n]
   except IndexError:
       r, s = ffr.r, ffs.s
       for i in range(len(r), n+2):
           ffr(i)
           if len(s) > n:
               return s[n]
       raise Exception("Whoops!")

ffs.s = [None, 2]

if __name__ == '__main__':

   first10 = [ffr(i) for i in range(1,11)]
   assert first10 == [1, 3, 7, 12, 18, 26, 35, 45, 56, 69], "ffr() value error(s)"
   print("ffr(n) for n = [1..10] is", first10)
   #
   bin = [None] + [0]*1000
   for i in range(40, 0, -1):
       bin[ffr(i)] += 1
   for i in range(960, 0, -1):
       bin[ffs(i)] += 1
   if all(b == 1 for b in bin[1:1000]):
       print("All Integers 1..1000 found OK")
   else:
       print("All Integers 1..1000 NOT found only once: ERROR")</lang>

Output

ffr(n) for n = [1..10] is [1, 3, 7, 12, 18, 26, 35, 45, 56, 69]
All Integers 1..1000 found OK