How to solve recursive equations when there are two different conditions on recursion?

Question

This was a problem asked in a coding competition at CodeChef and I asked it before on math stack exchange but unknowingly during the competition as I was not aware of the norms before. As the contest is now over and I still don't get how to do it,I want to find the solution to this and how to solve this recursive equation. Let $f(x)=y$ be a function that takes input $x$ and returns $y$.

$f(x) = (x/2)+f(x/2)$ if $x$ is even.

$f(x) = (x*(x-1))/2$ if $x$ is odd.

$f(0) = 0$ How to find all the values of $x$ for a given $y$ ? For eg: for $y=3$ $x$ can be $3$ and $4$

Answer 1

Hint: Write $x = 2^m\cdot n$, where $m, n$ are natural numbers and $n$ is odd.

Answer 2

By following the proposed indication.

Let m be the largest integer such that $2^m$ divides x. There exists n such that $x = 2^m.n$

We have

f(x)=(x/2)+f(x/2)

f(x/2)=(x/4)+f(x/4)

...

$f(x/2^{m-1})=(x/2^m)+f(x/2^m)$

(m relations)

Hence, by replacing

$f(x)=(x/2)+...+(x/2^m)+f(n)$

However n is odd then $f(n)=n(n-1)/2$

Hence

$f(x)=(x/2)+...+(x/2^m)+n(n-1)/2$

We can simplify, because we recognize a geometric sum of ratio 1/2:

$(x/2)+...+(x/2^m)=x.\sum_{k=1}^{m} \left(\frac12\right)^k$

$=x.\frac12.\frac{1-\left(\frac12\right)^m}{1-\frac12}$

$=x-(x/2^m)=x-n$

Finally

$f(x)=x+n(n-3)/2$