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

Reset to default
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.