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.


with javascript_semantics
sequence F = {1,3,7},
         S = {2,4,5,6}
integer fmax = 3 -- (ie F[3], ==7, already in S)
 
forward function ffs(integer n)
 
function ffr(integer n)
    integer l = length(F)
    while n>l do
        F &= F[l]+ffs(l)
        l += 1
    end while
    return F[n]
end function
 
function ffs(integer n)
    while n>length(S) do
        fmax += 1
        if fmax>length(F) then {} = ffr(fmax) end if
        S &= tagset(lim:=F[fmax]-1,start:=F[fmax-1]+1)
        -- ie/eg if fmax was 3, then F[2..3] being {3,7} 
        --       ==> tagset(lim:=6,start:=4), ie {4,5,6}.
    end while
    return S[n]
end function
 
{} = ffr(10)    -- (or collect one by one)
printf(1,"The first ten values of R: %v\n",{F[1..10]})
{} = ffr(40)    -- (not actually needed)
{} = ffs(960)
if sort(F[1..40]&S[1..960])=tagset(1000) then
    puts(1,"test passed\n")
else
    puts(1,"some error!\n")
end if
