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.


link printf,ximage 
 
procedure main()
   printf("Hofstader ff sequences R(n:= 1 to %d)\n",N := 10)
   every printf("R(%d)=%d\n",n := 1 to N,ffr(n))
 
   L := list(N := 1000,0)
   zero := dup := oob := 0
   every n := 1 to (RN := 40) do 
      if not L[ffr(n)] +:= 1 then    # count R occurrence
         oob +:= 1                   # count out of bounds
 
   every n := 1 to (N-RN) do 
      if not L[ffs(n)] +:= 1 then    # count S occurrence 
         oob +:= 1                   # count out of bounds  
 
   every zero +:= (!L = 0)           # count zeros / misses
   every dup  +:= (!L > 1)           # count > 1's / duplicates
 
   printf("Results of R(1 to %d) and S(1 to %d) coverage is ",RN,(N-RN))
   if oob+zero+dup=0 then 
      printf("complete.\n")
   else 
      printf("flawed\noob=%i,zero=%i,dup=%i\nL:\n%s\nR:\n%s\nS:\n%s\n",
             oob,zero,dup,ximage(L),ximage(ffr(ffr)),ximage(ffs(ffs)))
end
 
procedure ffr(n)             
static R,S
initial {
   R := [1]
   S := ffs(ffs)               # get access to S in ffs
   }
 
   if n === ffr then return R  # secret handshake to avoid globals :)
 
   if integer(n) > 0 then 
      return R[n] | put(R,ffr(n-1) + ffs(n-1))[n]
end
 
procedure ffs(n)
static R,S
initial {
   S := [2] 
   R := ffr(ffr)               # get access to R in ffr
   }
 
   if n === ffs then return S  # secret handshake to avoid globals :)
 
   if integer(n) > 0 then {
      if S[n] then return S[n]
      else {
         t := S[*S]  
         until *S = n do 
            if (t +:= 1) = !R then next # could be optimized with more code
            else return put(S,t)[*S]    # extend S
         }
   }
end