2
$\begingroup$

$\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}$An example here seems best. How many digits in base 2 do I need to represent any odd integer from $1$ to $\sqrt{77}$, inclusive? It seems to be essentially half the digits required for $77$ --- in base 2. We can represent $77$ with $7$ digits in base 2. Half of that is $3.5$, so we need $4$ digits in base 2. So let's change "essentially half" to "exactly $\floor{n/2} + 1$, where $n$ is the number of digits in base 2 held by $N$.

Since I'm interested in the odd integers (from $1$ to $\sqrt{77}$), this means that the last digit must be $1$. But if $4$ is the number of bits, then I get the wrong list in base 2: $$0001_2 = 1_{10}, 0011_2 = 3_{10}, 0101_2 = 5_{10}, 0111_2 = 7_{10}, 1001_2 = 9_{10}, ...$$

That's wrong because $9 > \sqrt{77}$. So the number must be less than $4$ digits in base 2. When I try $3$, I get the correct list

$$001_2 = 1_{10}, 011_2 = 3_{10}, 101_2 = 5_{10}, 111_2 = 7_{10},$$

but I haven't found an argument to convince myself I'm right. (Will this always work? Why?)

$\endgroup$
1
$\begingroup$

The number of digits of a number $N$ in base $b$ is $\log_b N+1$. So the number of digits of $\sqrt{N}$ in base $2$ is

$$\log_2 \sqrt{N}+1 = \frac{1}{2}\log_2 N +1.$$

The $\frac{1}{2}$ shows why it takes half as many digits for $\sqrt{N}$ as $N$.

$\endgroup$
  • $\begingroup$ $\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}$I think you mean $\floor{\log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $\sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $\frac{1}{2}\floor{\log_b \sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens. $\endgroup$ – Luitpold Ambre Dec 3 '18 at 13:34
  • $\begingroup$ You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $\lceil \log_2 N \rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $\lceil \log_2 \lfloor \sqrt{N} \rfloor \rceil.$ $\endgroup$ – B. Goddard Dec 3 '18 at 16:52

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.