Thanks, Steve!

...

(1) How big can |f(n) - n/2| be? I suspect it's O(log n). (For n up through 500, f(n) - n/2 ranges between 0 and 7/2.)

It looks sort of log like, but if you graph those numbers above, there are very piecewise-linear features, which doesn't make me confident I know what it's doing.

Can you post the graph someplace so I can see what you mean?

But the best speedup is to keep the 2D table between calculations. The change between calculating f(n) and f(n+1) is to increment one entry on each row.

So successive visits to a 2D point go down to the right, next time left, next time right; right, left, right, etc. It's a rounder-router!

I remember noticing this, but it didn't occur to me to exploit this for computation. Good idea!

Guess you can do the whole calculation by keeping each count mod 3. Might be nice to plot in color.

Adding a particle to the 2D table and seeing how the colors update might make a fun visual. Jim