6
$\begingroup$

I'm a professional programmer working through the CLRS exercises for fun and I've come across 4.6-1, where I got stuck. It asks to find a simpler expression for $n_j$ when $b$ is a positive integer (and not an arbitrary real number) in the following formula:

$$ n_j = \begin{cases} n & \text{if } j = 0,\\ \lceil n_{j-1}/b \rceil & \text{if } j > 0. \end{cases}$$

I'm uncertain how to approach this. After some poking, I came up with:

$$ n_j = \lceil n / b^j \rceil $$

I did not prove this, I just guessed. I can't see why this would hold for integers, but not for reals, which makes me doubt it is the correct solution.

Any help would be appreciated!

| cite | improve this question | |
$\endgroup$
7
$\begingroup$

It is the correct solution - possibly with a special case $n_0 = n$ if $n$ is not an integer.

If $a$ and $b$ are positive integers, and $x$ an arbitrary real number, then we have

$$\left\lceil \frac{x}{a}\right\rceil - 1 < \frac{x}{a} \leqslant \left\lceil \frac{x}{a} \right\rceil,$$

and dividing that by $b$ yields

$$\frac{1}{b}\left(\left\lceil\frac{x}{a}\right\rceil-1\right) < \frac{x}{ab} \leqslant \frac{1}{b}\left\lceil \frac{x}{a}\right\rceil.$$

Now, $P := \left\lceil \dfrac{x}{a}\right\rceil$ is an integer, hence we can write $P = q\cdot b - r$, with an integer $0 \leqslant r < b$. Then from $P > (q-1)\cdot b$ we conclude $P-1 \geqslant (q-1)\cdot b$, and thus

$$q-1 \leqslant \frac{P-1}{b} < \frac{x}{ab} \leqslant \frac{P}{b} \leqslant q,$$

which says

$$\left\lceil \frac{x}{ab}\right\rceil = \left\lceil \frac{1}{b}\left\lceil \frac{x}{a}\right\rceil\right\rceil.$$

It should be clear that that generalises to more than two successive divisions (and to $\lfloor\,\cdot\,\rfloor$ in place of $\lceil\,\cdot\,\rceil$, but of course you can't in general mix), so indeed

$$n_j = \left\lceil\frac{n_{j-1}}{b}\right\rceil = \left\lceil \frac{1}{b}\left\lceil \frac{n}{b^{j-1}}\right\rceil\right\rceil = \left\lceil \frac{n}{b^j}\right\rceil.$$

It does not work when dividing by arbitrary (positive) real numbers, because then you cannot conclude $P-1 \geqslant (q-1)\cdot b$ from $P > (q-1)\cdot b$, you need the granularity of integers for that.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this answer! $\endgroup$ – Stefan Kanev Oct 1 '13 at 7:57
  • $\begingroup$ What is q here? I did not understand, how you came up with P=q.b-r. $\endgroup$ – V K May 12 at 5:40
  • 1
    $\begingroup$ @VK $q$ is $\bigl\lceil\frac{P}{b}\bigr\rceil$. Since we're dealing with $\lceil\,\cdot\,\rceil$ and not with $\lfloor\,\cdot\,\rfloor$, instead of the usual division algorithm I use the variant that for $b$ a positive integer, every integer $k$ can be uniquely written in the form $k=q\cdot b-r$ with $0\leqslant r<b$. (The usual division algorithm gives a unique representation $k=\tilde{q}\cdot b+\tilde{r}$ with $0\leqslant\tilde{r} < b$. If $\tilde{r}=0$, let $q=\tilde{q}$ and $r=\tilde{r}$. Otherwise let $q=\tilde{q}+1$ and $r=b-\tilde{r}$.) $\endgroup$ – Daniel Fischer♦ May 12 at 11:54
  • $\begingroup$ Also how did you conclude from $$q-1 \leqslant \frac{P-1}{b} < \frac{x}{ab} \leqslant \frac{P}{b} \leqslant q,$$ the result. We can only conclude that the middle three terms in that are either q,q-1 or some fraction between these. $\endgroup$ – V K May 13 at 4:21
  • 1
    $\begingroup$ We have a strict inequality in the middle, so we know that $\bigl\lceil \frac{x}{ab}\bigr\rceil = \bigl\lceil \frac{P}{b}\bigr\rceil = q$, since the two fractions are stricty larger than $q-1$, and less than or equal to $q$. $\endgroup$ – Daniel Fischer♦ May 13 at 12:07

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.