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.


figfig = cluster is ffr, ffs
    rep = null
    ai = array[int]
    own R: ai := ai$[1]
    own S: ai := ai$[2]
 
    % Extend R and S until R(n) is known
    extend = proc (n: int)
        while n > ai$high(R) do
            next: int := ai$top(R) + S[ai$high(R)]
            ai$addh(R, next)
            while ai$top(S) < next-1 do
                ai$addh(S, ai$top(S)+1)
            end
            ai$addh(S, next+1)
        end
    end extend
 
    ffr = proc (n: int) returns (int)
        extend(n)
        return(R[n])
    end ffr
 
    ffs = proc (n: int) returns (int)
        while n > ai$high(S) do
            extend(ai$high(R) + 1)
        end
        return(S[n])
    end ffs
end figfig
 
start_up = proc ()
    ai = array[int]
    po: stream := stream$primary_output()
 
    % Print R[1..10]
    stream$puts(po, "R[1..10] =")
    for i: int in int$from_to(1,10) do
        stream$puts(po, " " || int$unparse(figfig$ffr(i)))
    end
    stream$putl(po, "")
 
    % Count the occurrences of 1..1000 in R[1..40] and S[1..960]
    occur: ai := ai$fill(1, 1000, 0)
    for i: int in int$from_to(1, 40) do
        occur[figfig$ffr(i)] := occur[figfig$ffr(i)] + 1
    end
    for i: int in int$from_to(1, 960) do
        occur[figfig$ffs(i)] := occur[figfig$ffs(i)] + 1
    end
 
    % See if they all occur exactly once
    begin
        for i: int in int$from_to(1, 1000) do
            if occur[i] ~= 1 then exit wrong(i) end
        end
        stream$putl(po, 
            "All numbers 1..1000 occur exactly once in R[1..40] U S[1..960].")
    end except when wrong(i: int):
        stream$putl(po, "Error: " ||
            int$unparse(i) || " occurs " || int$unparse(occur[i]) || " times.")
    end
end start_up