[VA] SRC #012c - Then and Now: Sum

[John Keith]

I wouldn't call f(n) an "unassuming series", it's really quite a complex and interesting series. Being recursive it can take some time to compute for larger numbers but there are some shortcuts we can use to speed up the computation.

First of all, d(n), the number of bits needed to represent n, is a very simple sequence that can be computed rapidly with a simple loop. Secondly, there is an underlying fractal pattern in f(n) and to compute k terms one need only compute approximately 2 * LOG2(k) terms recursively, and the rest can be filled in by a simple loop needing only 1 addition per term.

This is still basically brute force and I don't have a complete program ready yet but at least the germ of an idea.