Isn't this only true if you save all the R values, which makes the space complexity O(n) again?
No. My implementation does not need nor store any R values other than the last one. The S sequence generates itself. The only non-scalar in the entire computation is the 'groups' list, which is just a touch over O(sqrt(n)).