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.


using System;
using System.Collections.Generic;
using System.Linq;
 
namespace HofstadterFigureFigure
{
	class HofstadterFigureFigure
	{
		readonly List<int> _r = new List<int>() {1};
		readonly List<int> _s = new List<int>();
 
		public IEnumerable<int> R()
		{
			int iR = 0;
			while (true)
			{
				if (iR >= _r.Count)
				{
					Advance();
				}
				yield return _r[iR++];
			}
		}
 
		public IEnumerable<int> S()
		{
			int iS = 0;
			while (true)
			{
				if (iS >= _s.Count)
				{
					Advance();
				}
				yield return _s[iS++];
			}
		}
 
		private void Advance()
		{
			int rCount = _r.Count;
			int oldR = _r[rCount - 1];
			int sVal;
 
			// Take care of first two cases specially since S won't be larger than R at that point
			switch (rCount)
			{
				case 1:
					sVal = 2;
					break;
				case 2:
					sVal = 4;
					break;
				default:
					sVal = _s[rCount - 1];
					break;
			}
			_r.Add(_r[rCount - 1] + sVal);
			int newR = _r[rCount];
			for (int iS = oldR + 1; iS < newR; iS++)
			{
				_s.Add(iS);
			}
		}
	}
 
	class Program
	{
		static void Main()
		{
			var hff = new HofstadterFigureFigure();
			var rs = hff.R();
			var arr = rs.Take(40).ToList();
 
			foreach(var v in arr.Take(10))
			{
				Console.WriteLine("{0}", v);
			}
 
			var hs = new HashSet<int>(arr);
			hs.UnionWith(hff.S().Take(960));
			Console.WriteLine(hs.Count == 1000 ? "Verified" : "Oops!  Something's wrong!");
		}
	}
}
 