What solution do you think the author had in mind? He did hint to use define and use interleaveStreams and to avoid checking divisibility testing.
Recall the famous haskell fibonacci:
fib = 0 : 1 : some_function_of fib
Mathematically speaking, what fractal property does the ruler sequence observe that you could similarly exploit?
As for your solution, I don't doubt for a minute it's correct (I probably could have worded what I said better). The hope is that a proof would be interesting/delightful in that ineffable math-y way.