I like how instead of giving a procedure to produce the whole answer he created an induction-style algorithm that, given part of an answer, produces the next output.
Looks like "The mathematician's solution to Fizz Buzz"
Is this really an "induction-style" algorithm? (I haven't actually heard that term before.) I usually associate induction with taking some large input and shrinking it at each step until you hit some base case. This is really the opposite of induction--it starts with a base case (1) and grows the output, which makes this sound a bit more like co-induction.
Another way to think about it would be that he defined a little finite-state automaton to compute the answer. You just run the automaton for as many steps as you want, noting down what it outputs each time. I think this is actually very much like what a programmer would write if tasked with solving FizzBuzz in an online streaming fashion (rather than for some bounded n).
Maybe it's just my bias towards functional programming showing, but I actually think this approach is fairly intuitive. In fact, I would have probably come up with something structurally similar (differing only in details).
You're right, it looks like co-induction the term for what I was thinking.
Is it a common FP technique to do local-state-less looping like that? I would expect a tail-recursion solution to pass the next or previous value rather than re-deriving it from reading the output.
In other words, this person seems to be expressing a tail-recursive solution? Interesting. I would agree that tail-recursion is probably more intuitive than stateful iteration to a mathematician as well.
Another way to think about it would be that he defined a little finite-state automaton to compute the answer. You just run the automaton for as many steps as you want, noting down what it outputs each time. I think this is actually very much like what a programmer would write if tasked with solving FizzBuzz in an online streaming fashion (rather than for some bounded n).
Maybe it's just my bias towards functional programming showing, but I actually think this approach is fairly intuitive. In fact, I would have probably come up with something structurally similar (differing only in details).