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.
recursion need a closed form
2
$\begingroup$
algorithms
discrete-mathematics
recurrence-relations
-
1Are you sure that there is a simpler method than counting the number of $1$s in the binary expansion? – 2011-12-03
-
1A 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