I have the following recurrence formula:
f(0) = 0
f(1) = 1
f(n) = n + f(floor(n/2))
which can be expressed in code as:
int f(int n) {
int s = 0;
for (; n; n >>= 1)
s += n;
return s;
}
Is there a closed-form that will allow me to compute f(n)
in one step?
If not, is there anything else I could do to compute f(n)
more quickly?
Searching on OEIS gives this series:
A005187: a(n) = a([n/2]) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.
So the second parts gives the formula of 2*n - bitcount(2*n)
. You can calculate this with some efficient bitcount implementation, such as gcc's __builtin_popcount
.