# How many digits in base 2 do I need to represent any odd integer from 1 to $\sqrt{N}$?

$$\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?)

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$$.
• $\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. – Luitpold Ambre Dec 3 '18 at 13:34
• 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.$ – B. Goddard Dec 3 '18 at 16:52