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.


$r = [nil, 1]
$s = [nil, 2]
 
def buildSeq(n)
  current = [ $r[-1], $s[-1] ].max
  while $r.length <= n || $s.length <= n
    idx = [ $r.length, $s.length ].min - 1
    current += 1
    if current == $r[idx] + $s[idx]
      $r << current
    else
      $s << current
    end
  end
end
 
def ffr(n)
  buildSeq(n)
  $r[n]
end
 
def ffs(n)
  buildSeq(n)
  $s[n]
end
 
require 'set'
require 'test/unit'
 
class TestHofstadterFigureFigure < Test::Unit::TestCase
  def test_first_ten_R_values
    r10 = 1.upto(10).map {|n| ffr(n)}
    assert_equal(r10, [1, 3, 7, 12, 18, 26, 35, 45, 56, 69])
  end
 
  def test_40_R_and_960_S_are_1_to_1000
    rs_values = Set.new
    rs_values.merge( 1.upto(40).collect  {|n| ffr(n)} )
    rs_values.merge( 1.upto(960).collect {|n| ffs(n)} )
    assert_equal(rs_values, Set.new( 1..1000 ))
  end
end