# Revision history [back]

I am not sure about your precise question. Here is some hint anyway:

If you write your number in base 2, the last digit tells you whether the number is even (it is a "0"), or odd (it is a "1").

Now, if your number is even, dividing by 2 corresponds to removing the last "0".

If your number is odd, removing 1 corresponds to replacing the last "1" by a "0".

Hence, to reach 0 from your initial number n, the number of time you will get an odd number in your procedure is the number of "1" in the binary representation of your number n, and the number of time you will get an even number in your procedure is the length of the binary representation of your number n minus 1 (note that the binary representation of 0 has length 1).

Let us consider your last example:

sage: n = 40930
sage: s = n.str(base=2)
sage: s
'1001111111100010'
sage: s.count('1')
10
sage: len(s) - 1
15


Hence, in your procedure, you will have to remove 10 times a 1, and you will have to divide by 2 15 times to reach the number 0.