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

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ If the number is too large to write out in decimal, how can I possibly write it out in binary, though? $\endgroup$
    – user51819
    Dec 9, 2012 at 16:17
  • $\begingroup$ @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 ;) $\endgroup$
    – N. S.
    Dec 9, 2012 at 16:19
  • $\begingroup$ Is there a way to move along the binary of the number without writing it all out at one time? $\endgroup$
    – user51819
    Dec 9, 2012 at 16:20
  • $\begingroup$ @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.... $\endgroup$
    – N. S.
    Dec 9, 2012 at 16:25
  • $\begingroup$ 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) $\endgroup$
    – user51819
    Dec 9, 2012 at 16:27
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .