Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits?

Question

Let $x,N$ be positive integers.

I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using $$\lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

bits.

Equivalently, does the following hold: $$\log\left\lfloor \frac{N}{x} + 1\right\rfloor \leq \lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

Obviously, this holds for $x=1$, what about general $x$?

Answer 1

This is indeed possible.

First, notice that for storing $\left\lfloor\frac{N}{x}+1\right\rfloor$ values ($0,1,2,\ldots,\left\lfloor\frac{N}{x}\right\rfloor$), you need $\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil$ bits (which might be larger than $\log\left\lfloor\frac{N}{x}+1\right\rfloor$). This won't stop us though :).

---

We first notice that for every $$\forall 1<x,N\in\mathbb N:\left\lfloor\frac{N}{x}+1\right\rfloor\leq\left\lceil\frac{N+1}{x}\right\rceil$$ To see this, consider the case where $\frac{N}{x}\in \mathbb N$, and thus $$\left\lfloor\frac{N}{x}+1\right\rfloor = \frac{N}{x}+1=\frac{N}{x}+\left\lceil\frac{1}{x}\right\rceil=\left\lceil\frac{N+1}{x}\right\rceil$$ Otherwise, when $\frac{N}{x}\not \in \mathbb N$:$$\left\lfloor\frac{N}{x}+1\right\rfloor =\left\lceil\frac{N}{x}\right\rceil\leq\left\lceil\frac{N+1}{x}\right\rceil$$

Another useful inequality is $\forall r\geq 1:\log\left\lceil r\right\rceil\leq\left\lceil\log r\right\rceil$.

To see this, let $k\in \mathbb N$ such that $2^{k-1}<r\leq2^{k}$.

Now $k-1<\log r\leq k$, and therefore $\left\lceil\log r\right\rceil =k$. Now $\log\left\lceil r\right\rceil\leq k=\left\lceil\log r\right\rceil$.

Finally, we conclude that: $$\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil\leq\left\lceil\log\left\lceil\frac{N+1}{x}\right\rceil\right\rceil\leq\left\lceil\left\lceil\log\frac{N+1}{x}\right\rceil\right\rceil$$ $$=\left\lceil\log(N+1)-\log(x)\right\rceil$$ $$\leq\left\lceil\log(N+1)\right\rceil-\left\lfloor\log(x)\right\rfloor$$