1

Preceding the proposed recurrence solution 1.9 we have the very clear table and I understand that we can group by powers of two, that $J(n)$ is always 1 at the start of the group, and it increases by 2 within a group.

I'm having trouble understanding what is meant by "what's left" in this sentence

So if we write $n$ in the form of $n = 2^m + l$, where $2^m$ is the largest power of 2 not exceeding $n$ and where $l$ is what's left, the solution to our recurrence seems to be ...

Does the author mean what's left of the power-of-two group? Or what's left of the people involved in the elimination circle?

Friedrich 'Fred' Clausen
  • 387
  • 2
  • 12

1 Answers1

2

$\ell$ is $n-2^m$. That is, the difference between $n$ and the largest power of $2$ not exceeding $n$.

(I think "what's left" is the author's way of informally referring to the portion of $n$ that is not 'contained' in some power of $2$. )

Air Conditioner
  • 1,872
  • Thank you. With your help stepping through $m=3$ i.e. $n=8$ cemented this understanding: $l=0$ is $J(2^3 + 0) = 2(0) + 1 = 1$, $l=1$ is $J(2^3+1) = 2(1) + 1 = 3$, $l=2$ is $J(2^3 + 2) = 2(2) + 1 = 5$ – Friedrich 'Fred' Clausen Nov 25 '19 at 04:12