Here is the epsilon data I promised. The columns of the table, in order, are:
1. The exponent k that yields n=10^k.
2. The value of R(10^k). Please verify the value of R(10^15) with other implementations.
3. The number of S-groups in the S sequence.
4. The ratio between column 3 and sqrt(n).
5. The number of S-groups used to generate the S sequence.
6. The ratio between column 5 and n^0.25.
1 69 4 1.264911 1 0.562341
2 5764 12 1.200000 3 0.948683
3 526334 41 1.296534 7 1.244796
4 50874761 133 1.330000 13 1.300000
5 5028514748 431 1.362942 25 1.405853
6 500918449417 1384 1.384000 47 1.486271
7 50029364025646 4416 1.396462 87 1.547103
8 5000934571821489 14039 1.403900 157 1.570000
9 500029664631299264 44534 1.408289 285 1.602673
10 50000940106333921280 141082 1.410820 512 1.619086
11 5000029765607020822528 446604 1.412286 920 1.636017
12 500000941936492081577984 1413120 1.413120 1647 1.647000
13 50000029798618762867376128 4470180 1.413595 2944 1.655533
14 5000000942529842273283211264 14138641 1.413864 5255 1.661777
15 500000029809255645132191956992 44715123 1.414016 9372 1.666603Three empirical conclusions can be drawn. Formal proof is left as an exercise for the reader.
I. The R values are increasingly good approximations of n*n/2 from above, as we would expect from a running sum. For example, for n=10^15 the distance is less than 6 parts in one hundred million.
II. The ratio in the fourth column will converge to a constant slightly above 1.4 but below 1.5. This means that the space consumption is bounded from above by a constant multiple of sqrt(n), so it is no worse than O(sqrt(n)) and the corresponding epsilon is zero.
III. The ratio in the sixth column will converge to a constant slightly above 1.6 but below 2. This means that the number of S-groups used to generate the S sequence is bounded from above by a constant multiple of n^0.25, so it is no worse than O(n^0.25) and the corresponding epsilon is zero.
I might write a faster version to get above R(10^15), if I find the time.