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.


#include <stdio.h>
#include <stdlib.h>
 
// simple extensible array stuff
typedef unsigned long long xint;
 
typedef struct {
	size_t len, alloc;
	xint *buf;
} xarray;
 
xarray rs, ss;
 
void setsize(xarray *a, size_t size)
{
	size_t n = a->alloc;
	if (!n) n = 1;
 
	while (n < size) n <<= 1;
	if (a->alloc < n) {
		a->buf = realloc(a->buf, sizeof(xint) * n);
		if (!a->buf) abort();
		a->alloc = n;
	}
}
 
void push(xarray *a, xint v)
{
	while (a->alloc <= a->len)
		setsize(a, a->alloc * 2);
 
	a->buf[a->len++] = v;
}
 
 
// sequence stuff
void RS_append(void);
 
xint R(int n)
{
	while (n > rs.len) RS_append();
	return rs.buf[n - 1];
}
 
xint S(int n)
{
	while (n > ss.len) RS_append();
	return ss.buf[n - 1];
}
 
void RS_append()
{
	int n = rs.len;
	xint r = R(n) + S(n);
	xint s = S(ss.len);
 
	push(&rs, r);
	while (++s < r) push(&ss, s);
	push(&ss, r + 1); // pesky 3
}
 
int main(void)
{
	push(&rs, 1);
	push(&ss, 2);
 
	int i;
	printf("R(1 .. 10):");
	for (i = 1; i <= 10; i++)
		printf(" %llu", R(i));
 
	char seen[1001] = { 0 };
	for (i = 1; i <=  40; i++) seen[ R(i) ] = 1;
	for (i = 1; i <= 960; i++) seen[ S(i) ] = 1;
	for (i = 1; i <= 1000 && seen[i]; i++);
 
	if (i <= 1000) {
		fprintf(stderr, "%d not seen\n", i);
		abort();
	}
 
	puts("\nfirst 1000 ok");
	return 0;
}