# Mathematical explanation of the output sequence

I have a recursive function that gives some sequence:

def f(n):
if n <= 0:
return 0
else:
return 1-(n%2)+f(n/2)


Which returns a number. So I need to say what's the logic in this number, and is some logical explanation to this numbers cause, for ex, the number from this function:

def f(n):
if n <= 0:
return 0
else:
return (n%2)+f(n/2)


is the sum of digits in the "n" number in binary numerical system representation: n = 12 == 1100 -> so f(12) return 2, cause 1+1+0+0 = 2. But what's the logic in the first function?

-

Another way to say it is that the second function is counting ones in the binary representation of $n$. Do a little experimenting with the first function:

$$\begin{array}{c|c|r} n&f(n)&n\text{ in binary}\\ \hline 0&0&0\\ 1&0&1\\ 2&1&10\\ 3&0&11\\ 4&2&100\\ 5&1&101\\ 6&1&110\\ 7&0&111\\ 8&3&1000 \end{array}$$

It does something very similar to the second function, and once you spot it, you should be able to convince yourself that it really does perform that operation.

-
Sorry, but i didn't understand what the first function gives. For ex: n = 3 in binary equals to "0011", but f(3) returns 0. Why? – 4lex1v May 14 '12 at 9:48
I think you've mixed up my functions =) – 4lex1v May 14 '12 at 9:51
@John: Sorry: I reversed first and second in my explanation. I’ve fixed it now. – Brian M. Scott May 14 '12 at 9:52
Ok, now i got it! Thank you very much – 4lex1v May 14 '12 at 9:59

Hint: Since (n%2) is being replaced by 1-(n%2), it replaces 1 with 0 and 0 with 1 in the binary representation of $n$.

-