Search code examples
cperformancerecurrence

Is there a closed form for f(n) = n + f(floor(n/2))?

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?

Solution

  • 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.