2
$\begingroup$

Is there a closed formula to the problem $f(1)=1, f(2n)=f(n), f(2n+1)=f(2n)+1$. So far i have found a solution for $n$, which is the number of power of $2$'s needed to add up to the number starting with the greatest power of $2$. Also $n=$ the number of $1$'s needed to represent $n$ in binary form. So for example $f(12)=2, 2^3 + 2^2 = 12$, $12$ in binary is represented as $1100$, two $1$'s so $n=2$. My problem is i know the process but can't find a simple formula to this problem.

  • 1
    A related function is ["fusc", a name coined by Dijkstra](http://www.cs.utexas.edu/~EWD/transcriptions/EWD05xx/EWD578.html). See also [here](http://www.cut-the-knot.org/blue/FuscProperty.shtml).2011-12-03

3 Answers 3

5

There is no known closed form solution for the number of ones in the binary representation of a number, also known as the Hamming weight of the number. You may want to check out this related question on efficient ways to compute f(n): https://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

1

It's obvious that f(n) = number of 1s in n's binary representation

# the following python code would do f = lambda x:str(bin(x)).count('1') f(5)  # 2 f(8)  # 1 f(15) # 4 

And for efficiency, the following code in C was given in chapter 5.1 of Hacker's Delight

/* returns number of 1s in x's binary reperesantation */ static inline int cnt1(int x) {     x = (x & 0x55555555) + ((x >> 1) & 0x55555555);     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);     x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);     x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);     x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);     return x; } 

EDIT: If you want a more mathematical representation, f[x_] := Sum[Floor[Mod[x, 2^(i + 1)]/2^i], {i, 0, Infinity}] in Mathematica looks like a ordinary sum formula. But for a closed form solution, sadly I don't think there exist one.

  • 0
    @Sean I've edited my answer to add a mathematical looking formula. But a closed form solution may not exist :-(2011-12-03
0

http://en.wikipedia.org/wiki/Hamming_distance

there is not close formula, but the algorithm can be known review the works of Richard Hamming.