7
$\begingroup$

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

2 Answers 2

2

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

  • 0
    @user51819 I don't know any general method... $10^{100}$ is probably easy because is a large power of an even number, but given an arbitrary large number I don't know of any way to approach the problem.. Someone else might know ;)2012-12-09
0

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.