# Is there a way to determine if half of an even number will be odd or even?

For example 100 is even and 100/2= 50 is also even

But 30 is also even but 30/2=15 is odd

Now let's say I have a number as large as 10^10000000000...

I want to know how many steps are involved in cutting this number in half. When the number is even, I divide it by 2. When it's odd, I subtract 1. I continue this process until I hit 0.

However, when the number is too high, I can't actually manipulate it directly (elaboration: too big to write out, and too big to fit into memory on a computer), so I am curious if there's a way for me to do this by just knowing the even/odd attributes along the chain.

I hope this makes sense!

Example: If n=100, I have the following chain

100, 50, 25, 24, 12, 6, 3, 2, 1, 0

Which is a total of 9 "splitting steps" (10 if you count the original number) And the following parities

Even, Even, Odd, Even, Even, Even, Odd, Even, Odd, Even

I am asking if, given n=10, there is a way to get this parity chain

-

Yes you can get the chain for $n=10$, but for large numbers it is not easy.

Write your number $n$ in binary. What you are doing is the following:

• If the last digit is 0, you erase it.
• If the last digit is 1, you make it a zero.

For $n=10$ in binary you have $n=1010$. Thus your string is

$$1010 \to 101 \to 100 \to 10 \to 1 \to 0$$

In total, the number of digits is exactly the number of digits in binary (which is exactly $\log_2 n$ rounded up) plus the number of 1 in the binary representation

-
If the number is too large to write out in decimal, how can I possibly write it out in binary, though? –  user51819 Dec 9 '12 at 16:17
@user51819 That is exactly what I meant by not easy for large numbers. Anyhow, it is easy to see that finding a method to solve this problem is equivalent to writing the number in binary; so if you cannot write the number in binary you cannot solve the problem ;) –  N. S. Dec 9 '12 at 16:19
Is there a way to move along the binary of the number without writing it all out at one time? –  user51819 Dec 9 '12 at 16:20
@user51819 Yes, but it is either the process you described, or you can do the following: Find the largest $m$ such that $2^m \leq n$ and subtract $n-2^m$. Repeat....A better approach would be to pick some $0 < < 2^m < < n$ and find the quotient and reminder when $n$ is divided by $2^m$, $q$ gives you the first many digits, $r$ gives the last few... You can repeat.... –  N. S. Dec 9 '12 at 16:25
Do you have an example using, say, n=10^100? How do I know the 2^m or the quotient if I can't actually manipulate the full decimal value of n directly? (in this case I can with that level of n but for the sake of experiment assume I can't) –  user51819 Dec 9 '12 at 16:27

Your sequence corresponds quirte directly with the binary representation of the original number: Starting form the least significant binary digit, each $0$ corresponds to "even, dide by two" and each $1$ corresponds to "odd, subtract one; even, divide by two". For your example $n=100$, which is $1100100$ in binary we thus obtain

Even, divide by two; even, divide by two; odd, subtract one, then even, divide by two; even, divide by two; even, divide by two; odd, subtract one, then even, divide by two; odd, subtract one. Finally zero is even.

Thus determining your even/odd sequence is equivalent to determinig the binary representation of the given number.

-