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.


:- use_module(library(chr)).
 
:- chr_constraint ffr/2, ffs/2, hofstadter/1,hofstadter/2.
:- chr_option(debug, off).
:- chr_option(optimize, full).
 
% to remove duplicates
ffr(N, R1) \ ffr(N, R2) <=> R1 = R2 | true.
ffs(N, R1) \ ffs(N, R2) <=> R1 = R2 | true.
 
% compute ffr
ffr(N, R), ffr(N1, R1), ffs(N1,S1) ==>
         N > 1, N1 is N - 1 |
	 R is R1 + S1.
 
% compute ffs
ffs(N, S), ffs(N1,S1) ==>
         N > 1, N1 is N - 1 |
	 V is S1 + 1,
	 (   find_chr_constraint(ffr(_, V)) ->  S is V+1; S = V).
 
% init
hofstadter(N) ==>  ffr(1,1), ffs(1,2).
% loop
hofstadter(N), ffr(N1, _R), ffs(N1, _S) ==> N1 < N, N2 is N1 +1 |  ffr(N2,_), ffs(N2,_).
 
 