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.


package require Tcl 8.5
package require struct::set
 
# Core sequence generator engine; stores in $R and $S globals
set R {R:-> 1}
set S {S:-> 2}
proc buildSeq {n} {
    global R S
    set ctr [expr {max([lindex $R end],[lindex $S end])}]
    while {[llength $R] <= $n || [llength $S] <= $n} {
	set idx [expr {min([llength $R],[llength $S]) - 1}]
	if {[incr ctr] == [lindex $R $idx]+[lindex $S $idx]} {
	    lappend R $ctr
	} else {
	    lappend S $ctr
	}
    }
}
 
# Accessor procedures
proc ffr {n} {
    buildSeq $n
    lindex $::R $n
}
proc ffs {n} {
    buildSeq $n
    lindex $::S $n
}
 
# Show some things about the sequence
for {set i 1} {$i <= 10} {incr i} {
    puts "R($i) = [ffr $i]"
}
puts "Considering {1..1000} vs {R(i)|i\u2208\[1,40\]}\u222a{S(i)|i\u2208\[1,960\]}"
for {set i 1} {$i <= 1000} {incr i} {lappend numsInSeq $i}
for {set i 1} {$i <= 40} {incr i} {
    lappend numsRS [ffr $i]
}
for {set i 1} {$i <= 960} {incr i} {
    lappend numsRS [ffs $i]
}
puts "set sizes: [struct::set size $numsInSeq] vs [struct::set size $numsRS]"
puts "set equality: [expr {[struct::set equal $numsInSeq $numsRS]?{yes}:{no}}]"