% Chapter 3 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib
\pageno=67
\beginchapter 3 Integer Functions
WHOLE NUMBERS constitute the backbone of discrete mathematics,
"!integer functions"
and we often need to convert from fractions or arbitrary real numbers
to integers. Our goal in this chapter is to gain familiarity and fluency
with such conversions and to learn some of their remarkable properties.
\beginsection 3.1 Floors and Ceilings
We start by covering the "floor" ("greatest integer")
"!entier, \string\see floor"
and "ceiling" ("least integer") functions,
\tabref|nn:floor|\tabref|nn:ceil|%
which are defined for all real~$x$ as follows:
\begindisplay \openup3pt
\eqalign{\lfloor x \rfloor
&=\hbox{the greatest integer less than or equal to $x\,$;}\cr
\lceil x \rceil
&=\hbox{the least integer greater than or equal to $x\,$.}\cr}
\eqno\eqref|f-c-def|
\enddisplay
Kenneth E. "Iverson" introduced this "notation", as well as the names ``floor''
and ``ceiling,\qback'' early in the 1960s~[|APL|, page~12]. He
found that typesetters could handle the symbols
by shaving the tops and bottoms off of
`$\mskip2mu[\mskip2mu$' and `$\mskip2mu]\mskip2mu$'.
His notation has become sufficiently popular that
floor and ceiling brackets can now be used
in a technical paper without an explanation of what they mean.
Until recently, people had most often been writing
`$[x]$' for the greatest integer $\le x$, without a
good equivalent for the least integer function.
Some authors had even tried to use `$@]x[@$'\dash---%
\g )Ouch.(\g
with a predictable lack of success.
Besides variations in notation,
there are variations in the functions themselves.
For example,
some "pocket calculators" have an "INT" function, defined as $\lfloor x \rfloor$
when $x$~is positive and $\lceil x \rceil$ when $x$~is negative.
The designers of these "calculators" probably wanted
their INT function to satisfy the identity
$\hbox{INT}(-x) = -\hbox{INT}(x)$. But we'll stick to our floor and ceiling
functions, because they have even nicer properties than this.
One good way to become familiar with the floor and ceiling functions is
to understand their graphs, which form staircase-like patterns
above and below the line $f(x)=x$:
\begindisplay
\unitlength=2pt
\beginpicture(100,80)(-50,-40)
\put(-45,0){\vector(1,0){90}}
\put(41,-6){\hbox{$x$}}
\put(0,-40){\vector(0,1){80}}
\put(2,36){\hbox{$f(x)$}}
\put(-40,-40){\line(1,1){80}}
\put(41,36){\hbox{$f(x)=x$}}
\multiput(-40,-30)(10,10){7}{%
\beginpicture(20,0)(-10,0)
\put(0,0){\disk{1.5}}
\multiput(-9.25,0)(1.5,0){6}{\disk1}
\linethickness=.6\unitlength
\put(0,0){\line(1,0){10}}
\endpicture
}
\put(-30,-1){\line(0,1){2}}
\put(-20,-1){\line(0,1){2}}
\put(-10,-1){\line(0,1){2}}
\put(10,-1){\line(0,1){2}}
\put(20,-1){\line(0,1){2}}
\put(30,-1){\line(0,1){2}}
\put(-30,-6){\hbox to0pt{\hss\llap{$-$}$3$\hss}}
\put(-20,-6){\hbox to0pt{\hss\llap{$-$}$2$\hss}}
\put(-10,-6){\hbox to0pt{\hss\llap{$-$}$1$\hss}}
\put(10,-6){\hbox to0pt{\hss$1$\hss}}
\put(20,-6){\hbox to0pt{\hss$2$\hss}}
\put(30,-6){\hbox to0pt{\hss$3$\hss}}
\put(-2,30){\vbox to0pt{\vss\llap{$3$}\vss}}
\put(-2,20){\vbox to0pt{\vss\llap{$2$}\vss}}
\put(-2,10){\vbox to0pt{\vss\llap{$1$}\vss}}
\put(2,-6){\hbox{$0$}}
\put(2,-10){\vbox to0pt{\vss\hbox{$-1$}\vss}}
\put(2,-20){\vbox to0pt{\vss\hbox{$-2$}\vss}}
\put(2,-30){\vbox to0pt{\vss\hbox{$-3$}\vss}}
\put(41,14){\hbox{$\lceil x\rceil=\,\,
\beginpicture(10,5)(0,-1.5)
\put(10,0){\disk{1.5}}
\multiput(0.75,0)(1.5,0){6}{\disk1}
\endpicture$}}
\put(41,6){\hbox{$\lfloor x\rfloor=\,\,
\beginpicture(10,5)(0,-1.5)
\put(0,0){\disk{1.5}}
\linethickness=.6\unitlength
\put(0,0){\line(1,0){10}}
\endpicture$}}
\put(27.1828,-40){\line(0,1){80}}
\put(29,-38){\hbox{$\,x = e$}}
\put(-27.1828,-40){\line(0,1){80}}
\put(-29,36){\llap{$x = -e\,$}}
\endpicture
\enddisplay
We see from the graph that, for example,
\begindisplay
\eqalign{\lfloor e \rfloor &=2 \,,\cr \lceil e \rceil &=3 \,,}\qquad
\eqalign{\lfloor -e \rfloor &=-3 \,,\cr \lceil -e \rceil &=-2 \,,}
\enddisplay
since $e=2.71828\ldots\,\,$.
By staring at this illustration we can observe
several facts about floors and ceilings.
First, since the floor function lies on or below the diagonal line $f(x)=x$,
we have $\lfloor x \rfloor \leq x$;
similarly $\lceil x \rceil \geq x$.
(This, of course, is quite obvious from the definition.)
The two functions are equal precisely at the integer points:
\begindisplay
\lfloor x \rfloor = x
\quad \iff \quad \hbox{$x$ is an integer}
\quad \iff \quad \lceil x \rceil = x\,.
\enddisplay
(We use the notation `$\Longleftrightarrow$' to mean ``"if and only if"\/.\qback'')
"!$\iff$ (alphabetize at the end)"
Furthermore, when they differ the ceiling is exactly $1$~higher than the floor:
\begindisplay
\lceil x\rceil-\lfloor x\rfloor=\[\hbox{$x$ is not an integer}]\,.
\eqno\eqref|c-f|
\enddisplay
\g\vskip-29pt Cute.\par By Iverson's bracket
convention, this is a complete equation.\g
If we shift the diagonal line down one unit, it lies
completely below the floor function, so
$x-1 < \lfloor x \rfloor$;
similarly $x+1 > \lceil x \rceil$.
Combining these observations gives us
\begindisplay
x-1 < \lfloor x \rfloor
\leq x
\leq \lceil x \rceil
< x+1 \,.
\eqno\eqref|f-c-interval|
\enddisplay
Finally, the functions are reflections of each other about both axes:
\begindisplay
\lfloor -x \rfloor
= - \lceil x \rceil\,;\qquad
\lceil -x \rceil
= - \lfloor x \rfloor\,.
\eqno\eqref|f-c-reflection|
\enddisplay
Thus each is easily expressible in terms of the other.
This fact helps to ex\-plain why the ceiling function once had no
"notation" of its own.
But we see ceilings often enough to warrant giving them special symbols,
just as we have adopted special notations for rising powers as well as
falling powers. Mathematicians have long had both sine and cosine,
tangent and cotangent, secant and cosecant, max and min; now we also
\g Next week we're getting walls.\g
have both floor and ceiling.
To actually prove properties about the floor and ceiling functions,
rather than just to observe such facts graphically,
the following four rules are especially useful:
\begindisplay
\vcenter{\halign{$#$&$\quad{}\iff\quad#$\hfil&\qquad(#)\hfil\cr
\lfloor x \rfloor = n & n \leq x < n+1 \,, &a\cr
\lfloor x \rfloor = n & x-1 < n \leq x \,, &b\cr
\lceil x \rceil = n & n-1 < x \leq n \,, &c\cr
\lceil x \rceil = n & x \leq n < x+1 \,. &d\cr}}
\eqno\eqref|alt-f-c-def|
\enddisplay
(We assume in all four cases that $n$ is an integer and that $x$ is real.)
Rules (a) and~(c) are immediate consequences of definition \eq(|f-c-def|);
rules (b) and~(d) are the same but with the inequalities rearranged so that
$n$ is in the middle.
It's possible to move an integer term in or out of a floor (or ceiling):
\begindisplay
\lfloor x+n \rfloor
= \lfloor x \rfloor + n \,,
\qquad\hbox{integer $n$.}
\eqno\eqref|n-in/out|
\enddisplay
(Because rule \eq(|alt-f-c-def|\rm(a)) says that this assertion
is equivalent to the
inequalities $\lfloor x\rfloor +n\le x+n<\lfloor x\rfloor +n+1$.)
But similar operations, like moving out a constant factor, cannot be
done in general. For example,
we have $\lfloor nx\rfloor \ne n\lfloor x\rfloor $ when $n=2$ and $x=1/2$.
This means that floor and ceiling brackets are comparatively inflexible.
We are usually happy if we can get rid of them or if we can prove
anything at all when they are present.
It turns out that there are many situations in which floor and ceiling
brackets are redundant, so that we can insert or delete them at will.
For example, any inequality between a real and an integer is
equivalent to a floor or ceiling inequality between integers:
\begindisplay
\vcenter{\halign{$#$&$\quad{}\iff\quad#$\hfil&\qquad(#)\hfil\cr
x < n & \lfloor x \rfloor < n \,, &a\cr
n < x & n < \lceil x \rceil \,, &b\cr
x \leq n & \lceil x \rceil \leq n \,, &c\cr
n \leq x & n \leq \lfloor x \rfloor \,. &d\cr}}
\eqno\eqref|f-c-in/out|
\enddisplay
These rules are easily proved. For example, if $x0$.
Alternatively, a similar derivation yields the answer $\lceil @
\lg(n+1) \rceil$;
this formula holds for $n=0$ as well, if we're willing to say that it takes
zero~bits to write $n=0$ in binary.
\looseness=-1
Let's look next at expressions with several floors or ceilings.
What is $\bigl\lceil \lfloor x \rfloor \bigr\rceil$?
Easy\dash---since $\lfloor x \rfloor$ is an integer,
$\bigl\lceil \lfloor x \rfloor \bigr\rceil$ is just $\lfloor x \rfloor$.
So is any other expression with an innermost $\lfloor x \rfloor$
surrounded by any number of floors or ceilings.
Here's a tougher problem:
Prove or disprove the assertion
\begindisplay\advance\abovedisplayskip-3pt\advance\belowdisplayskip-3pt
\bigl\lfloor \mskip-1mu\sqrt{\lfloor x \rfloor} \bigr\rfloor
= \lfloor \sqrt{x} \rfloor \,, \qquad\hbox{real $x \geq 0$.}
\eqno\eqref|floor-in-sqrt|
\enddisplay
Equality obviously holds when $x$~is an integer, because $x=\lfloor x \rfloor$.
\g (Of course $\pi$, $e$, and $\phi$ are the obvious first real
numbers to try, aren't they?)\g
And there's equality in the special cases $\pi = 3.14159\ldots\,$,
$e = 2.71828\ldots\,$, and $\phi = (1+\sqrt5@)/2=1.61803\ldots\,$,
because we get $1=1$.
Our failure to find a counterexample suggests that equality holds in general,
so let's try to prove it.
Incidentally, when we're faced with a ``prove or disprove,\qback''
we're usually better off trying first to disprove with a counterexample,
\g "Skepticism" is healthy only to a limited extent. Being skeptical
"!philosophy"
about proofs and programs (particularly your own) will probably keep
your grades healthy and your job fairly secure. But applying that much
skepticism will probably also keep you shut away working all the time,
instead of letting you get out for exercise and relaxation.\par
Too much skepticism is an open invitation to the
state of rigor mortis, where you become so worried about being
correct and rigorous that you never get anything finished.\par
\hfill\dash---A skeptic\g
for two reasons: A disproof is
potentially easier (we need just one counterexample); and
nit-picking arouses our creative juices.
Even if the given assertion is true, our
search for a counterexample
often leads us to a proof, as soon as we see why a counterexample
is impossible. Besides, it's healthy to be skeptical.
If we try to prove that
$\bigl\lfloor \mskip-1mu\sqrt{\lfloor x \rfloor} \bigr\rfloor
= \lfloor \sqrt{x} \rfloor$ with the help of calculus, we
might start by decomposing~$x$
into its integer and fractional parts $\lfloor x \rfloor + \{x\}
=n+\theta$
and then expanding the square root using the binomial theorem:
$(n + \theta)^{1/2} =
n^{1/2} + n^{-1/2} \theta / 2
- n^{-3/2} \theta^2 \!/ 8 + \cdots\,$.
But this approach gets pretty messy.
It's much easier to use the tools we've developed.
Here's a possible strategy:
Somehow strip off the outer floor and square root of
$\bigl\lfloor \mskip-1mu \sqrt{\lfloor x \rfloor} \bigr\rfloor$,
then remove the inner floor,
then add back the outer stuff to get
$\lfloor \sqrt{x} \rfloor$.
OK\null. We let $m =
\smash{\bigl\lfloor \mskip-1mu \sqrt{\lfloor x \rfloor} \bigr\rfloor}$
and invoke~\eq(|alt-f-c-def|\rm(a)),
giving $m \leq \smash{\sqrt{\lfloor x \rfloor}} < m+1$.
That removes the outer floor bracket without losing any information.
Squaring, since all three expressions are nonnegative,
we have $m^2 \leq \lfloor x \rfloor < (m+1)^2 \bex$.
That gets rid of the square root.
Next we remove the floor,
using~\eq(|f-c-in/out|\rm(d)) for the left inequality
and~\eq(|f-c-in/out|\rm(a)) for the right:
$m^2 \leq x < (m+1)^2 \bex$.
It's now a simple matter to retrace our steps,
taking square roots to get $m \leq \sqrt{x} < m+1$
and invoking~\eq(|alt-f-c-def|\rm(a))
to get $m = \lfloor \sqrt{x} \rfloor$.
Thus $\bigl\lfloor \mskip-1mu \sqrt{\lfloor x \rfloor} \bigr\rfloor = m
= \lfloor \sqrt{x} \rfloor$; the assertion is true. Similarly, we can
prove that
\begindisplay
\bigl\lceil \mskip-1mu\sqrt{\lceil x \rceil}@ \bigr\rceil
= \lceil \sqrt{x}\, \rceil \,, \qquad\hbox{real $x \geq 0$.}
\enddisplay
The proof we just found
doesn't rely heavily on the properties of square roots.
A closer look shows that we can generalize the ideas and prove much more:
Let $f(x)$ be any continuous,
monotonically increasing function with the property that
\begindisplay
f(x)={\rm integer}\qquad\Longrightarrow\qquad x={\rm integer}\,.
\enddisplay
(The symbol `$\Longrightarrow$' means ``"implies".\qback'')
"!$\Longrightarrow$ (alphabetize at the end)"
Then we have
\begindisplay
\lfloor f(x)\rfloor =\lfloor f(\lfloor x\rfloor )\rfloor \qquad\hbox{and}\qquad
\lceil f(x)\rceil =\lceil f(\lceil x\rceil )\rceil ,\,
\eqno
\enddisplay
whenever $f(x)$, $f(\lfloor x\rfloor )$, and $f(\lceil x\rceil )$ are defined.
\g\vskip-35pt(This observation
was made by R.~J. "McEliece" when he was an undergrad.)\g
Let's prove this general property for ceilings, since we did floors
earlier and since the proof for floors is almost the same. If $x=\lceil
x\rceil $, there's nothing to prove. Otherwise $x<\lceil x\rceil $, and
$f(x) \lfloor m\alpha \rfloor$.
Thus $\spec(\beta)$ has fewer than $m$~elements $\le\lfloor m\alpha\rfloor$,
while $\spec(\alpha)$ has at least~$m$.
Spectra have many beautiful properties.
\g \noindent\llap{``}If\/ $x$ be an incommensurable number less than unity, one of the
series of quantities\/ $m/x$, $m/(1-x)$, where\/ $m$~is a whole number,
can be found which shall lie between any given consecutive integers, and
but one such quantity can be found.''\par\hfill\dash---Rayleigh~[|rayleigh|]\g
For example, consider the two multisets
\begindisplay \openup2pt
\spec(\sqrt{2} \,)
&= \{ 1,2,4,5,7,8,9,11,12,14,15,16,18,19,21,22,24,\ldots\, \} \,,\cr
\spec(2+\sqrt{2} \,)
&= \{ 3,6,10,13,17,20,23,27,30,34,37,40,44,47,51,\ldots\, \} \,.
\enddisplay
It's easy to calculate $\spec(\sqrt2\,)$ with a pocket calculator, and
the $n$th element of $\spec(2+\sqrt2\,)$ is just $2n$ more than the $n$th element
of $\spec(\sqrt2\,)$, by \eq(|n-in/out|). A closer look shows that these
two spectra are also related in a much more surprising way:
It seems that any number missing from one is in the other,
but that no number is in both!
And it's true:
The positive integers are the disjoint union of
$\spec(\sqrt{2} \,)$ and $\spec(2+\sqrt{2} \,)$. We say that
these spectra form a {\it"partition"\/} of the positive integers.
To prove this assertion, we will count how many of the elements of
$\spec(\sqrt2\,)$ are $\le n$, and how many of the elements of
$\spec(2+\sqrt2\,)$ are $\le n$. If the total is~$n$, for each~$n$,
\g Right, because exactly one of the counts must increase when $n$
increases by~$1$.\g
these two spectra do indeed partition the integers.
Let $\alpha$ be positive.
The number of elements in $\spec(\alpha)$ that are $\le n$ is
\begindisplay \openup1pt
N(\alpha,n)&=\sum_{k>0}\bigi[\lfloor k\alpha\rfloor\le n\bigr]\cr
&=\sum_{k>0}\bigi[\lfloor k\alpha\rfloor0}\[k\alpha0$ instead of $k\ge1$, because $(n+1)/\alpha$
might be less than~$1$ for certain $n$ and~$\alpha$. If we had tried to
apply
\eq(|ints-in-interval|) to determine the number of integers in
$[1\dts(n+1)/\alpha)$, rather than the number of integers in $(0\dts(n+1)/\alpha)$, we
would have gotten the right answer; but our derivation would have been
faulty because the conditions of applicability wouldn't have been met.
Good, we have a formula for $N(\alpha,n)$. Now we can test whether or not
$\spec(\sqrt2\,)$ and
$\spec(2+\sqrt2\,)$ partition the positive integers, by testing whether
or not $N(\sqrt2,n)+N(2+\sqrt2,n)=n$ for all integers $n>0$, using
\eq(|N-alpha-n|):
\begindisplay \openup4pt \advance\abovedisplayskip-2pt
&\left\lceil n+1\over\sqrt2\right\rceil-1+
\left\lceil n+1\over2+\sqrt2\right\rceil-1=n\cr
&\iff\enspace\left\lfloor n+1\over\sqrt2\right\rfloor+
\left\lfloor n+1\over2+\sqrt2\right\rfloor=n\,,
&\quad\hbox{by \eq(|c-f|);}\cr
&\iff\enspace{n+1\over\sqrt2}-\left\{n+1\over\sqrt2\right\}+
{n+1\over2+\sqrt2}-\left\{n+1\over2+\sqrt2\right\}=n\,,
&\quad\hbox{by \eq(|brace|).}\cr
\enddisplay
Everything simplifies now because of the neat identity
\begindisplay
{1\over\sqrt2}+{1\over2+\sqrt2}=1\,;
\enddisplay
our condition reduces to testing whether or not
\begindisplay
\left\{n+1\over\sqrt2\right\}+\left\{n+1\over2+\sqrt2\right\}=1\,,
\enddisplay
for all $n>0$. And we win, because these are the fractional parts of
two noninteger numbers that add up to the integer $n+1$.
A partition it is.
\beginsection 3.3 Floor/Ceiling Recurrences
Floors and ceilings add an interesting new dimension to the
study of "recurrence" relations. Let's look first at the recurrence
\begindisplay
\eqalign{K_0 &=1 \,;\cr
K_{n+1} &=1 \,+\, \min (2 K_{\lfloor n/2 \rfloor} ,
3 K_{\lfloor n/3 \rfloor}) \,,
\qquad\hbox{for $n \geq 0$.}\cr}
\eqno\eqref|knuth-numbers|
\enddisplay
Thus, for example, $K_1$ is $1 + \min (2 K_0, 3 K_0)=3$;
the sequence begins $1$,~$3$, $3$, $4$, $7$, $7$, $7$, $9$, $9$,~$10$,~$13$,
\dots\thinspace.
One of the authors of this book has modestly decided to call these the
"Knuth numbers".
\goodbreak
Exercise |knuth-no-ex| asks for a proof or disproof
that $K_n\ge n$, for all $n\ge0$.
The first few $K$'s just listed do satisfy the inequality,
so there's a good chance that it's true in general.
Let's try an induction proof:
The basis $n=0$ comes directly from the defining recurrence.
For the induction step,
we assume that the inequality holds
for all values up through some fixed nonnegative~$n$,
and we try to show that $K_{n+1} \geq n+1$.
From the recurrence we know that
$K_{n+1} = 1 + \min (2 K_{\lfloor n/2 \rfloor} , 3 K_{\lfloor n/3 \rfloor})$.
The induction hypothesis tells us that
$2K_{\lfloor n/2 \rfloor} \geq 2\lfloor n/2 \rfloor$ and
$3K_{\lfloor n/3 \rfloor} \geq 3\lfloor n/3 \rfloor$.
However, $2\lfloor n/2\rfloor$ can be as small as $n-1$, and
$3 \lfloor n/3 \rfloor$ can be as small as $n-2$. The most we can conclude
from our induction hypothesis is that $K_{n+1} \geq 1 + (n-2)$;
this falls far short of $K_{n+1} \geq n+1$.
We now have reason to worry about the truth of
$K_n\ge n$, so let's try to disprove it. If we can find an $n$ such that
either $2K_{\lfloor n/2\rfloor}1$, is to divide them into two
"!halving"
approximately equal parts, one of size $\lceil n/2\rceil$ and the
other of size $\lfloor n/2\rfloor$. (Notice, incidentally, that
\begindisplay
n=\lceil n/2\rceil +\lfloor n/2\rfloor \,;
\eqno\eqref|half-split|
\enddisplay
this formula comes in handy rather often.) After each part has been sorted
separately (by the same method, applied recursively), we can merge the
records into their final order by doing at most $n-1$ further comparisons.
Therefore the total number of comparisons performed is at most $f(n)$, where
\begindisplay
\eqalign{f(1) &=0 \,;\cr
f(n) &=f(\lceil n/2\rceil )+f(\lfloor n/2\rfloor )+n-1\,,
\qquad\hbox{for $n > 1$.}\cr}
\eqno\eqref|merge-sort-rec|
\enddisplay
A solution to this recurrence appears in exercise~|merge-sol|.
The "Josephus problem" of Chapter 1 has a similar recurrence, which can be
cast in the form
\begindisplay
J(1)&=1\,;\cr
J(n)&=2J(\lfloor n/2\rfloor )-(-1)^n\,,\qquad\hbox{for $n>1$.}
\enddisplay
We've got more tools to work with than we had in Chapter~1, so let's consider
the more authentic Josephus problem in which every third person is eliminated,
instead of every second. If we apply the methods that worked in Chapter~1
to this more difficult problem, we wind up with a recurrence like
\begindisplay
J_3(n)=\textstyle\Bigl\lceil {3\over2}J_3\bigl(\lfloor{2\over3}n\rfloor\bigr)
+a_n\Bigr\rceil \bmod n+1\,,
\enddisplay
where `mod' is a function that we will be studying shortly, and where we have
$a_n=-2$, $+1$, or~$-\half $ according as $n\bmod3=0$, $1$, or~$2$.
But this recurrence is too horrible to pursue.
There's another approach to the Josephus problem that gives a much better
setup. Whenever a person is passed over, we can assign a new number.
Thus, $1$ and~$2$ become $n+1$ and~$n+2$, then $3$~is executed;
$4$ and~$5$ become $n+3$ and~$n+4$, then $6$~is executed; \dots;
$3k+1$ and~$3k+2$ become $n+2k+1$ and~$n+2k+2$, then $3k+3$~is executed;
\dots~then $3n$~is executed (or left to survive).
For example, when $n=10$ the numbers are
\begindisplay \def\preamble{&$\hfil##\hfil$\kern1.5em}
1&2&3&4&5&6&7&8&9&10\cr
11&12&&13&14&&15&16&&17\cr
18&&&19&20&&&21&&22\cr
&&&23&24&&&&&25\cr
&&&26&&&&&&27\cr
&&&28\cr
&&&29\cr
&&&30\cr
\enddisplay
The $k$th person eliminated ends up with number $3k$. So we can figure out who
the survivor is if we can figure out the original number of person number~$3n$.
If $N>n$, person number $N$ must have had a previous number,
and we can find it as follows: We have $N=n+2k+1$ or $N=n+2k+2$, hence
$k=\lfloor (N-n-1)/2\rfloor $;
the previous number was $3k+1$ or $3k+2$, respectively.
That is, it was $3k+(N-n-2k)=k+N-n$.
Hence we can calculate the survivor's number
$J_3(n)$ as follows:
\begindisplay
&N:=3n\,;\cr
&\hbox{{\bf while} \ $N>n$ \ {\bf do} \
$\displaystyle N:=\left\lfloor N-n-1\over2\right\rfloor+N-n\,$;}\cr
&J_3(n):=N\,.
\enddisplay
\g\vskip-13pt\noindent\llap{``}Not too slow,\par not too fast.''\par
\hfill\dash---L. "Armstrong"\g
This is not a closed form for $J_3(n)$; it's not even a recurrence. But at
least it tells us how to calculate the answer reasonably fast, if $n$~is
large.
Fortunately there's a way to simplify this algorithm if we use the variable
$D=3n+1-N$ in place of~$N$. (This change in notation
corresponds to assigning numbers from
$3n$ down to~$1$, instead of from $1$ up to~$3n$; it's sort of like a
countdown.) Then the complicated assignment to~$N$ becomes
\begindisplay \openup4pt
D&:=3n+1-\left(\left\lfloor (3n+1-D)-n-1\over2\right\rfloor +(3n+1-D)-n\right)\cr
&\mathrel{\phantom:}=
n+D-\left\lfloor 2n-D\over2\right\rfloor =D-\left\lfloor -D\over2\right\rfloor
=D+\left\lceil D\over2\right\rceil
=\textstyle\bigl\lceil {3\over2}D\bigr\rceil \,,\cr
\enddisplay
and we can rewrite the algorithm as follows:
\begindisplay
&D:=1\,;\cr
&\hbox{{\bf while} \ $D\le2n$ \ {\bf do} \
$D:=\bigl\lceil{3\over2}D\bigr\rceil\,$;}\cr
&J_3(n):=3n+1-D\,.
\enddisplay
Aha! This looks much nicer, because $n$ enters the calculation in a very
simple way. In fact, we can show by the same reasoning that the survivor
$J_q(n)$ when every $q$th person is eliminated can be calculated as follows:
\begindisplay
&D:=1\,;\cr
&\hbox{{\bf while} \ $D\le(q-1)n$ \ {\bf do} \
$D:=\bigl\lceil{q_{\null}\over q-1}D\bigr\rceil\,$;}\eqno\eqref|m-josephus|\cr
&J_q(n):=qn+1-D\,.
\enddisplay
In the case $q=2$ that we know so well,
%\g We're $2$ familiar.\g
this makes $D$ grow to $2^{m+1}$
when $n=2^m+l$; hence $J_2(n)=2(2^m+l)+1-2^{m+1}=2l+1$. Good.
The recipe in \thiseq\ computes a sequence of integers that can be
defined by the following recurrence:
\begindisplay
\eqalign{D_0^{(q)}&=1\,;\cr
D_n^{(q)}&=\Bigl\lceil {q\over q-1}D_{n-1}^{(q)}\Bigr\rceil \,
\qquad\hbox{for $n>0$}.\cr}
\eqno\eqref|dm-rec|
\enddisplay
"!Josephus numbers"
These numbers don't seem to relate to any familiar functions in a simple
way, except when $q=2$; hence they probably don't have a nice closed form.
But if we're willing to accept the sequence $D_n^{(q)}$ as ``known,\qback''
\g``Known'' like, say, harmonic numbers.
A.\thinspace M. "Odlyzko" and\par
H.\thinspace S. "Wilf" have shown [|odl-wilf|] that
\smallskip
$D_n^{(3)}=\lfloor({3\over2})^nC\rfloor$,
\smallskip
where
\smallskip
$C\approx1.622270503.$\g
then it's easy to describe the solution to the generalized Josephus
problem: The survivor $\smash{J_q(n)}$ is $qn+1-D_k^{(q)}$, where $k$ is as
small as possible such that $D_k^{(q)}>(q-1)n$.
\beginsection 3.4 `mod': The Binary Operation
The "quotient" of $n$ divided by $m$ is $\lfloor n/m\rfloor$, when
$m$ and~$n$ are positive integers. It's handy to have a simple "notation"
also for the "remainder" of this
division, and we call it `$n\bmod m$'.
\tabref|nn:mod|"!mod, binary operation"
The basic formula
\begindisplay
n = m \underbrace{\lfloor n/m \rfloor}_{
\hbox to0pt{\hss\sevenrm quotient\hss}}
\;+\; \underbrace{n \bmod m}_{
\hbox to0pt{\hss\sevenrm remainder\hss}}
\enddisplay
tells us that we can express $n\bmod m$ as $n-m\lfloor n/m\rfloor$. We can
generalize this to negative integers, and in fact to arbitrary real numbers:
\begindisplay
x \bmod y
= x \,-\, y \lfloor x/y \rfloor \,,
\qquad\hbox{for $y \neq 0$.}
\eqno\eqref|bmod-def|
\enddisplay
This defines `mod' as a binary operation,
just as addition and subtraction are binary operations.
\g Why do they call it `mod': The Binary Operation?
Stay tuned to find out in the next, exciting, chapter!\g
Mathematicians have used mod this way informally for a long time,
taking various quantities mod~$10$, mod~$2\pi$, and so on,
but only in the last twenty years has it caught on formally.
Old notion, new notation.
We can easily grasp
the intuitive meaning of $x\bmod y$, when $x$ and $y$ are positive real
numbers, if we imagine a circle of circumference~$y$
whose points have been assigned real numbers in the interval $[@0\dts y)$.
If we travel a distance~$x$ around the circle, starting at~$0$,
we end up at $x\bmod y$. (And the number of times we encounter~$0$ as
we go is $\lfloor x/y\rfloor$.)
When $x$ or $y$ is negative, we need to look at the definition carefully
in order to see exactly what it means.
\g Beware of computer languages that use another definition.\g
Here are some integer-valued examples:
\begindisplay
5 \bmod 3 &=5 - 3 \lfloor 5/3 \rfloor &=2 \,;\cr
5 \bmod -3 &=5 - (-3) \lfloor 5/(-3) \rfloor &=-1 \,;\cr
-5 \bmod 3 &=-5 - 3 \lfloor -5/3 \rfloor &=1 \,;\cr
-5 \bmod -3 &=-5 - (-3) \lfloor -5/(-3) \rfloor &=-2 \,.
\enddisplay
The number after `mod' is called the {\it "modulus"\/}; nobody has
\g How about calling the other number the modumor?\g
yet decided what to call the number before `mod'. In applications,
the modulus is usually
positive, but the definition makes perfect sense when
the modulus is negative.
In both cases the value of $x\bmod y$ is between $0$~and the modulus:
\begindisplay
0 \leq x \bmod y < y\,, &\qquad \hbox{for $y > 0$;} \cr
0 \geq x \bmod y > y\,, &\qquad \hbox{for $y < 0$.}
\enddisplay
What about $y=0$? Definition~\eq(|bmod-def|) leaves this case undefined,
in order to avoid division by zero, but to be complete we can define
\begindisplay
x \bmod 0
= x \,.
\eqno\eqref|mod0|
\enddisplay
This convention preserves the property that $x\bmod y$ always differs from~$x$
by a multiple of~$y$. (It might seem more natural to make the function
continuous at~$0$, by defining
$x\bmod0=\lim_{y\to0}x\bmod y=0$. But we'll see in Chapter~4 that this
"!mod~$0$"
would be much less useful. Continuity is not an important aspect of
the mod operation.)
We've already seen one special case of mod in disguise,
when we wrote $x$ in terms of its integer and fractional parts,
$x = \lfloor x \rfloor + \{x\}$.
The fractional part can also be written $x\bmod1$, because we have
\begindisplay
x = \lfloor x \rfloor \,+\, x \bmod 1 \,.
\enddisplay
Notice that parentheses aren't needed in this formula; we take
mod to bind more tightly than addition or subtraction.
The floor function has been used to define mod, and the ceiling function
hasn't gotten equal time. We could perhaps
use the ceiling to define a mod analog like
\begindisplay
x \mathbin{\rm mumble} y
= y \lceil x/y \rceil - x \,;
\enddisplay
in our circle analogy this represents the distance the traveler needs
\g There was a time in the 70s when `mod' was the fashion.
Maybe the new "mumble" function should be called `punk'?\medskip
No\dash---I \undertext{like} \hbox{`mumble'}.\g
"!notation, need for new"
to continue, after going a distance~$x$, to get back to the starting point~$0$.
But of course we'd need a better name than `mumble'.
If sufficient applications come along, an appropriate name will
probably suggest itself.
The "distributive law" is mod's most important algebraic property: We have
\begindisplay
c(x \bmod y)
= (cx) \bmod (cy)
\eqno\eqref|mod-dist|
\enddisplay
for all real $c$, $x$, and $y$. (Those
who like mod to bind less tightly than multiplication
may remove the parentheses from the right side here, too.)
It's easy to prove this law from definition~\eq(|bmod-def|), since
\begindisplay
c(x \bmod y)
= c(x - y \lfloor x/y \rfloor)
= cx - cy \lfloor cx/cy \rfloor
= cx \bmod cy \,,
\enddisplay
if $cy\ne0$; and the zero-modulus cases are trivially true.
Our four examples using $\pm 5$ and $\pm 3$ illustrate this law twice,
with $c=-1$. An identity like \thiseq\ is reassuring, because it gives
us reason to believe that `mod' has not been defined improperly.
In the remainder of this section,
\g The remainder, eh?\g
we'll consider an application in which `mod' turns out to be helpful although
it doesn't play a central role. The problem
arises frequently in a variety of situations: We want to "partition"
$n$~things into $m$~groups as equally as possible.
Suppose, for example,
that we have $n$~short lines of text that we'd like to arrange in
$m$~columns. For \ae{}sthetic reasons, we want the columns to be
arranged in decreasing order of length (actually nonincreasing order); and the
lengths should be approximately the same\dash---no two columns should differ by
more than one line's worth of text. If 37 lines of text are being divided
into five columns, we would therefore prefer the arrangement on the right:
\begindisplay \def\\{\kern9pt}
\vbox{\baselineskip6pt\halign{&\fiverm line\kern1pt #\hfil\\\cr
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$5$\hfil\\\cr
\noalign{\vskip4pt}
1&9&17&25&33\cr
2&10&18&26&34\cr
3&11&19&27&35\cr
4&12&20&28&36\cr
5&13&21&29&37\cr
6&14&22&30\cr
7&15&23&31\cr
8&16&24&32\cr}}
\qquad\quad
\vbox{\baselineskip6pt\halign{&\fiverm line\kern1pt #\hfil\\\cr
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$7$\hfil\\&
\omit\hfil$7$\hfil\\&
\omit\hfil$7$\hfil\\\cr
\noalign{\vskip4pt}
1&9&17&24&31\cr
2&10&18&25&32\cr
3&11&19&26&33\cr
4&12&20&27&34\cr
5&13&21&28&35\cr
6&14&22&29&36\cr
7&15&23&30&37\cr
8&16\cr}}
\enddisplay
Furthermore we want to distribute the lines of text columnwise\dash---first deciding
how many lines go into the first column and then moving on to the second,
the third, and so on\dash---because that's the way people read.
Distributing row by row would give us the correct number
of lines in each column, but the ordering would be wrong. (We would get
something like the arrangement on the right, but column~1 would contain
lines 1,~6, 11, \dots,~36, instead of lines 1,~2, 3, \dots,~8 as desired.)
A row-by-row distribution strategy can't be used,
but it does tell us how many lines
to put in each column. If $n$ is not a multiple of~$m$,
the row-by-row procedure makes it clear
that the long columns should each contain $\lceil n/m\rceil$
lines, and the short columns should each contain $\lfloor n/m\rfloor$.
There will be exactly $n\bmod m$ long columns (and, as it turns out,
there will be exactly $\mathsurround=1pt n\mathbin{\rm mumble}m$ short ones).
Let's generalize the terminology and talk about `things' and `groups' instead
of `lines' and `columns'. We have just decided that the first group should contain
$\lceil n/m\rceil$ things; therefore the following sequential distribution
scheme ought to work: To distribute $n$ things into $m$ groups, when $m>0$,
put $\lceil n/m \rceil$ things into one group, then use the same procedure
recursively to put the remaining $n'=n-\lceil n/m\rceil$ things into $m'=m-1$
additional groups.
For example, if $n=314$ and $m=6$, the distribution goes like this:
\begindisplay \def\preamble{&$\hfil##\hfil$\quad} \openup-2pt
\rm remaining\ things&\rm remaining\ groups&\lceil\rm things/groups\rceil\cr
\noalign{\vskip3pt}
314& 6& 53\cr
261& 5& 53\cr
208& 4& 52\cr
156& 3& 52\cr
104& 2& 52\cr
\phantom052&1& 52\cr
\enddisplay
It works. We get groups of approximately the same size, even though the
divisor keeps changing.
Why does it work? In general we can suppose that $n=qm+r$,
where $q=\lfloor n/m\rfloor$
and $r=n\bmod m$. The process is simple if $r=0$: We put
$\lceil n/m\rceil=q$ things into
the first group and replace $n$ by~$n'=n-q$,
leaving $n'=qm'$ things to put into the remaining
$m'=m-1$ groups. And if $r>0$, we put $\lceil n/m\rceil=q+1$
things into the first group and
replace $n$ by~$n'=n-q-1$, leaving $n'=qm'+r-1$ things for subsequent
groups. The new remainder is $r'=r-1$, but $q$ stays the same.
It follows that there will be $r$ groups with $q+1$ things, followed
by $m-r$ groups with $q$ things.
How many things are in the $k$th group? We'd like a formula that gives
$\lceil n/m\rceil$ when $k\le n\bmod m$, and $\lfloor n/m\rfloor$ otherwise.
It's not hard to verify that
\begindisplay
\left\lceil n-k+1\over m\right\rceil
\enddisplay
has the desired properties, because this reduces to $q+\lceil(r-k+1)/
m\rceil$ if we write $n=qm+r$ as in the preceding paragraph; here
$q=\lfloor n/m\rfloor$. We have
$\lceil(r-k+1)/m\rceil=\[k\le r]$, if $1\le k\le m$ and $0\le r 0$,} \quad\hbox{integer $n$.}
\enddisplay
Finding a closed form for this sum
is tougher than what we've done so far (except perhaps for the
discrepancy problem we just looked at).
\g Be forewarned: This is the beginning of a pattern, in that the last
part of the chapter consists of the solution of some long, difficult
problem, with little more motivation than curiosity.\par
\hfill\dash---Students\par\bigskip
Touch\'e. But c'mon, gang, do you always need to be told about
applications before you can get interested in something?
This sum arises, for example, in the study of random number
generation and testing. But mathematicians looked at it long before
computers came along, because they found it natural to ask if there's a
way to sum arithmetic progressions that have been ``floored.\qback''\par
\hfill\dash---Your instructor\g
But it's instructive,
so we'll hack away at it for the rest of this chapter.
As usual, especially with tough problems,
we start by looking at small cases.
The special case $n=1$ is \eq(|f-replicative|), with $x$ replaced
by~$x/m$:
\begindisplay
\left\lfloor {x\over m} \right\rfloor
+ \left\lfloor {1+x\over m} \right\rfloor
+ \cdots
+ \left\lfloor {m-1+x\over m} \right\rfloor
= \lfloor x \rfloor \,.
\enddisplay
And as in Chapter~1, we find it useful to get more data by
generalizing downwards to the case $n=0$:
\begindisplay
\left\lfloor {x\over m} \right\rfloor
+ \left\lfloor {x\over m} \right\rfloor
+ \cdots
+ \left\lfloor {x\over m} \right\rfloor
= m \left\lfloor {x\over m} \right\rfloor \,.
\enddisplay
Our problem has two parameters, $m$~and~$n$;
let's look at some small cases for~$m$.
When $m=1$ there's just a single term in the sum
and its value is~$\lfloor x \rfloor$.
When~$m=2$ the sum is $\lfloor x/2 \rfloor + \lfloor (x+n)/2 \rfloor$.
We can remove the interaction between $x$ and~$n$
by removing~$n$ from inside the floor function,
but to do that we must consider even and odd~$n$ separately.
If $n$ is even, $n/2$~is an integer, so we can remove it from the floor:
\begindisplay
\left\lfloor {x\over 2} \right\rfloor
+ \left( \left\lfloor {x\over 2} \right\rfloor
+ {n\over 2} \right)
= 2 \left\lfloor {x\over 2} \right\rfloor + {n\over 2} \,.
\enddisplay
If $n$ is odd, $(n-1)/2$~is an integer so we get
\begindisplay
\left\lfloor {x\over 2} \right\rfloor
+ \left( \left\lfloor {x+1\over 2} \right\rfloor
+ {n-1\over 2} \right)
= \lfloor x \rfloor + {n-1\over 2} \,.
\enddisplay
The last step follows from~\eq(|f-replicative|) with~$m=2$.
These formulas for even and odd~$n$
slightly resemble those for $n=0$~and~$1$,
but no clear pattern has emerged yet; so we had better continue exploring
some more small cases. For~$m=3$ the sum is
\begindisplay
\left\lfloor {x\over 3} \right\rfloor
+ \left\lfloor {x+n\over 3} \right\rfloor
+ \left\lfloor {x+2n\over 3} \right\rfloor \,,
\enddisplay
and we consider three cases for~$n$: Either
it's a multiple of~$3$, or it's $1$~more than a multiple, or it's $2$~more.
That is, $n \bmod 3 =$~$0$, $1$, or~$2$.
If $n \bmod 3 = 0$ then $n/3$ and $2n/3$ are integers, so the sum is
\begindisplay
\left\lfloor {x\over 3} \right\rfloor
+ \left( \left\lfloor {x\over 3} \right\rfloor
+ {n\over 3} \right)
+ \left( \left\lfloor {x\over 3} \right\rfloor
+ {2n\over 3} \right)
= 3 \left\lfloor {x\over 3} \right\rfloor + n \,.
\enddisplay
If $n \bmod 3 = 1$ then $(n-1)/3$ and $(2n-2)/3$ are integers, so we have
\begindisplay
\left\lfloor {x\over 3} \right\rfloor
+ \left( \left\lfloor {x+1\over 3} \right\rfloor
+ {n-1\over 3} \right)
+ \left( \left\lfloor {x+2\over 3} \right\rfloor
+ {2n-2\over 3} \right)
= \lfloor x \rfloor + n - 1 \,.
\enddisplay
Again this last step follows from~\eq(|f-replicative|),
this time with~$m=3$.
And finally, if $n \bmod 3 = 2$ then
\begindisplay
\left\lfloor {x\over 3} \right\rfloor
+ \left( \left\lfloor {x+2\over 3} \right\rfloor
+ {n-2\over 3} \right)
+ \left( \left\lfloor {x+1\over 3} \right\rfloor
+ {2n-1\over 3} \right)
= \lfloor x \rfloor + n - 1 \,.
\enddisplay
The left hemispheres of our brains have finished the case~$m=3$,
\g\noindent\llap{``}Inventive genius requires pleasurable mental activity as a condition
for its vigorous exercise. `Necessity is the mother of invention'
is a silly proverb. `Necessity is the mother of futile dodges' is
much nearer to the truth. The basis of the growth of modern invention is
science, and science is almost wholly the outgrowth of pleasurable
intellectual curiosity.''\par"!philosophy"
\hfill\dash---A.\thinspace N. "!Whitehead"White-\par
\hfill head [|whitehead-aims|]\g
but the right hemispheres still can't recognize the pattern,
so we proceed to~$m=4$:
\begindisplay
\left\lfloor {x\over 4} \right\rfloor
+ \left\lfloor {x+n\over 4} \right\rfloor
+ \left\lfloor {x+2n\over 4} \right\rfloor
+ \left\lfloor {x+3n\over 4} \right\rfloor \,.
\enddisplay
At least we know enough by now to consider cases based on $n\bmod m$.
If $n \bmod 4 = 0$ then
\begindisplay
\left\lfloor {x\over 4} \right\rfloor
+ \left( \left\lfloor {x\over 4} \right\rfloor
+{n\over 4} \right)
+ \left( \left\lfloor {x\over 4} \right\rfloor
+{2n\over 4} \right)
+ \left( \left\lfloor {x\over 4} \right\rfloor
+{3n\over 4} \right)
= 4 \left\lfloor {x\over 4} \right\rfloor+{3n\over 2} \,.
\enddisplay
And if $n \bmod 4 = 1$,
\begindisplay \openup3pt
\hbox to3.1in{$\displaystyle
\left\lfloor {x\over 4} \right\rfloor
+ \left( \left\lfloor {x{+}1\over 4} \right\rfloor
+ {n{-}1\over 4} \right)
+ \left( \left\lfloor {x{+}2\over 4} \right\rfloor
+ {2n{-}2\over 4} \right)
+ \left( \left\lfloor {x{+}3\over 4} \right\rfloor
+ {3n{-}3\over 4} \right)\hss$}\cr
&= \lfloor x \rfloor + {3n\over 2} - {3\over 2} \,.
\enddisplay
The case $n\bmod4=3$ turns out to give the same answer. Finally,
in the case $n \bmod 4 = 2$ we get something a bit different, and this
turns out to be an important clue to the behavior in general:
\begindisplay \openup3pt
\hbox to.75in{$\displaystyle
\left\lfloor {x\over 4} \right\rfloor
+ \left( \left\lfloor {x{+}2\over 4} \right\rfloor
+ {n{-}2\over 4} \right)
+ \left( \left\lfloor {x\over 4} \right\rfloor
+ {2n\over 4} \right)
+ \left( \left\lfloor {x{+}2\over 4} \right\rfloor
+ {3n{-}2\over 4} \right) \hss$}\cr
&= 2 \left( \left\lfloor {x\over 4} \right\rfloor
+ \left\lfloor {x+2\over 4} \right\rfloor \right)
\,+\, {3n\over 2} \,-\, 1
= 2 \left\lfloor {x\over 2} \right\rfloor
+ {3n\over 2} - 1 \,.
\enddisplay
This last step simplifies something of the form
$\lfloor y/2 \rfloor + \lfloor (y+1)/2 \rfloor$,
which again is a special case of~\eq(|f-replicative|).
To summarize, here's the value of our sum for small~$m$:
{\parindent=0pt
\begindisplay \def\preamble{\biggstrut\hfil$##$\ &\vrule##%
&&\quad$\displaystyle##$\hfil} \lineskip=0pt \postdisplaypenalty=-200
\omit\bigstrut\hfil$m$\ &&
n \bmod m = 0& n \bmod m = 1 & n \bmod m = 2 & n \bmod m = 3 \cr
\noalign{\hrule}
\omit\bigstrut\vbox to14pt{}\hfil$1$\ &&
\phantom1\,\,\big\lfloor x \big\rfloor\cr
2&& 2 \left\lfloor {x\over 2} \right\rfloor
+ {n\over 2}
& \lfloor x \rfloor + {n\over 2} - {1\over 2}\cr
3&& 3 \left\lfloor {x\over 3} \right\rfloor +\, n
& \lfloor x \rfloor +\, n \,- 1
& \phantom1\,\,\lfloor x \rfloor +\, n \,- 1 \cr
4&& 4 \left\lfloor {x\over 4} \right\rfloor + {3n\over 2}
& \lfloor x \rfloor + {3n\over 2} - {3\over 2}
& 2 \left\lfloor {x\over 2} \right\rfloor + {3n\over 2} - 1
& \lfloor x \rfloor + {3n\over 2} - {3\over 2}\cr
\enddisplay}
It looks as if we're getting something of the form
\begindisplay
a \left\lfloor {x\over a} \right\rfloor + bn + c \,,
\enddisplay
where $a$,~$b$, and~$c$ somehow depend on $m$~and~$n$.
Even the myopic among us can see that $b$~is probably $(m-1)/2$.
It's harder to discern an expression for~$a$;
but the case $n \bmod 4 = 2$ gives us a hint
that $a$ is probably $\gcd(m,n)$,
the "greatest common divisor" of $m$~and~$n$.
This makes sense because $\gcd(m,n)$ is the factor we remove from $m$ and~$n$
when reducing the fraction $n/m$ to lowest terms, and our sum
involves the fraction $n/m$. (We'll look carefully at gcd operations
in Chapter~4.)
The value of~$c$ seems more mysterious,
but perhaps it will drop out of our proofs for $a$~and~$b$.
In computing the sum for small~$m$, we've effectively
rewritten each term of the sum as
\begindisplay
\left\lfloor {x+kn\over m} \right\rfloor
= \left\lfloor {x + kn \bmod m\over m} \right\rfloor
+ {kn\over m} - {kn \bmod m\over m} \,,
\enddisplay
because $({kn-kn\bmod m})/m$ is an integer that can be removed from inside
the floor brackets. Thus the original
sum can be expanded into the following tableau:
\begindisplay\def\preamble{&\hfil${}\;##\;{}$&%
$\displaystyle\hfil##\hfil$}\openup5pt
&\left\lfloor {x\over m} \right\rfloor
&+& {0\over m}&-& {0 \bmod m\over m}\cr
+&\left\lfloor {x + n \bmod m\over m} \right\rfloor
&+&{n\over m}&-& {n \bmod m\over m}\cr
+&\left\lfloor {x + 2n \bmod m\over m} \right\rfloor
&+&{2n\over m} &-& {2n \bmod m\over m}\cr
\noalign{\vskip-3pt}
& \vdots&& \vdots&& \vdots\cr
+& \left\lfloor {x + (m-1)n \bmod m\over m} \right\rfloor
&+&{(m-1)n\over m}&-& {(m-1)n \bmod m\over m} \rlap{$\,.$}
\enddisplay
When we experimented with small values of $m$,
these three columns led respectively to $a\lfloor x/a\rfloor$,
$bn$, and $c$.
In particular, we can see how $b$~arises.
The second column is an arithmetic progression, whose sum we know\dash---it's
the average of the first and last terms, times the number of terms:
\begindisplay
{1\over 2} \left( 0 + {(m-1)n\over m} \right)\cdot m
= {(m-1)n\over 2} \,.
\enddisplay
So our guess that $b=(m-1)/2$ has been verified.
The first and third columns seem tougher;
to determine $a$~and~$c$ we must take a closer look at the sequence of numbers
\begindisplay
0 \bmod m,\; n \bmod m,\; 2n \bmod m,\; \dots,\; (m-1)n \bmod m.
\enddisplay
Suppose, for example, that $m=12$ and $n=5$.
If we think of the sequence as times on a clock,
the numbers are $0$~o'clock (we take $12$~o'clock to be $0$~o'clock),
then $5$~o'clock,
$10$~o'clock, $3$~o'clock ($=15$~o'clock), $8$~o'clock, and so on.
It turns out that we hit every hour exactly once.
Now suppose $m=12$ and $n=8$.
The numbers are $0$~o'clock, $8$~o'clock, $4$~o'clock ($=16$~o'clock),
but then $0$,~$8$, and~$4$ repeat.
Since both $8$~and~$12$ are multiples of~$4$,
and since the numbers start at~$0$ (also a multiple of~$4$),
there's no way to break out of this pattern\dash---%
they must all be multiples of~$4$.
In these two cases we have $\gcd(12,5) = 1$ and $\gcd(12,8) = 4$.
The general rule, which we will prove next chapter,
\g Lemma now,\newline dilemma later.\g
states that if $d = \gcd(m,n)$ then
we get the numbers $0$,~$d$, $2d$, \dots, $m-d$ in some order,
followed by $d-1$~more copies of the same sequence.
For example, with $m=12$ and $n=8$ the pattern $0$,~$8$,~$4$ occurs
four~times.
The first column of our sum now makes complete sense.
It contains $d$~copies of the terms
$\lfloor x/m \rfloor$, $\lfloor (x+d)/m \rfloor$, \dots,
$\lfloor (x+m-d)/m \rfloor$, in some order, so its sum is
\begindisplay \openup3pt
\hbox to 2em{$\displaystyle
d \left( \left\lfloor {x\over m} \right\rfloor
+ \left\lfloor {x+d\over m} \right\rfloor
+ \cdots
+ \left\lfloor {x+m-d\over m} \right\rfloor \right)
\hss$}\cr
&= d \left( \left\lfloor {x/d\over m/d} \right\rfloor
+ \left\lfloor {x/d \,+\, 1\over m/d} \right\rfloor
+ \cdots
+ \left\lfloor {x/d \,+\, m/d \,-\, 1\over m/d} \right\rfloor
\right) \cr
&= d \left\lfloor {x\over d} \right\rfloor \,.
\enddisplay
This last step is yet another application of~\eq(|f-replicative|).
Our guess for~$a$ has been verified:
\begindisplay
a
= d
= \gcd(m,n) \,.
\enddisplay
Also, as we guessed, we can now compute~$c$, because the third column has
become easy to fathom.
It contains $d$~copies of the arithmetic progression
$0/m$, $d/m$, $2d/m$, \dots, $(m-d)/m$, so its sum is
\begindisplay
d \Biggl( {1\over 2} \biggl( 0 + {m-d\over m} \biggr) \cdot{m\over d}
\Biggr)
= {m-d\over 2} \,;
\enddisplay
the third column is actually subtracted, not added, so we have
\begindisplay
c
= {d-m\over 2} \,.
\enddisplay
End of mystery, end of quest. The desired closed form is
\begindisplay
\sum_{0 \leq k < m} \left\lfloor {nk+x\over m} \right\rfloor
= d \left\lfloor {x\over d} \right\rfloor
\,+\, {m-1\over 2}@ n
\,+\, {d-m\over 2} \,,
\enddisplay
where $d = \gcd(m,n)$.
As a check, we can make sure this works in the special cases $n=0$
and $n=1$ that we knew before:
When $n=0$ we get $d = \gcd(m,0) = m$;
the last two terms of the formula are zero
so the formula properly gives $m \lfloor x/m \rfloor$.
And for $n=1$ we get $d = \gcd(m,1) = 1$;
the last two terms cancel nicely, and the sum is just $\lfloor x\rfloor$.
By manipulating the closed form a bit,
we can actually make it symmetric in $m$~and~$n$:
\begindisplay
\sum_{0 \leq k < m} \! \left\lfloor {nk+x\over m} \right\rfloor
&= d \left\lfloor {x\over d} \right\rfloor
\,+\, {m-1\over 2}@ n
\,+\, {d-m\over 2} \cr
&= d \left\lfloor {x\over d} \right\rfloor
\,+\, {(m-1)(n-1)\over 2}
\,+\, {m-1\over 2} \,+\, {d-m\over 2}\cr
\noalign{\vskip6pt}
&= d \left\lfloor {x\over d} \right\rfloor
\,+\, {(m-1)(n-1)\over 2}
\,+\, {d-1\over 2} \,.
\eqno\eqref|f-progression|
\enddisplay
\g Yup, I'm floored.\g
This is astonishing,
because there's no algebraic reason to suspect that such a sum
should be symmetrical. We have proved a ``"reciprocity law",\qback''
\begindisplay
\sum_{0 \leq k < m} \left\lfloor {nk+x\over m} \right\rfloor
= \sum_{0 \leq k < n} \left\lfloor {mk+x\over n} \right\rfloor
\,,\qquad\hbox{integers $m, n > 0$.}
\enddisplay
For example, if $m=41$ and $n=127$,
the left sum has 41~terms and the right has~127;
"!Seaver, George Thomas"
but they still come out equal, for all real~$x$.
\beginexercises
\subhead \kern-.05em Warmups
\ex:
When we analyzed the "Josephus problem" in Chapter~1, we represented an
arbitrary positive integer~$n$ in the form $n=2^m+l$, where $0\le l<2^m$.
Give explicit formulas for $l$ and~$m$ as functions of~$n$, using
floor and/or ceiling brackets.{\clubpenalty=10000\par}
\answer $m=\lfloor \lg n\rfloor $; \ $l=n-2^m=n-2^{\lfloor \lg n\rfloor }$.
\ex:\exref|rounding|%
What is a formula for the "nearest integer" to a given real number~$x$?
In case of ties, when $x$~is exactly halfway between two integers,
give an expression that rounds
(a)~up\dash---that is, to $\lceil x \rceil$;
(b)~down\dash---that is, to~$\lfloor x \rfloor$.
\answer (a) $\lfloor x+.5\rfloor$. (b) $\lceil x-.5\rceil$.
\ex:\exref|irrat-div|%
Evaluate $\bigl\lfloor\lfloor m\alpha\rfloor n/\alpha\bigr\rfloor$,
when $m$ and $n$ are positive integers and $\alpha$ is an irrational
number greater than~$n$.
\answer This is $\lfloor mn-\{m\alpha\}n/\alpha\rfloor
=mn-1$, since $0<\{m\alpha\}<1$.
\ex:
The text describes problems at "levels" 1 through 5. What is a level~0 problem?
"!questions" "!generalize downwards"
(This, by the way, is {\it not\/} a level~0 problem.)
\answer Something where no proof is required, only a lucky guess (I guess).
\ex:
Find a necessary and sufficient condition that $\lfloor nx\rfloor=
n\lfloor x\rfloor$, when $n$ is a positive integer.
(Your condition should involve $\{x\}$.)
\answer We have $\lfloor nx\rfloor =
\bigl\lfloor n\lfloor x\rfloor+n\{x\}\bigr\rfloor=n\lfloor x\rfloor+
\bigl\lfloor n\{x\}\bigr\rfloor$ by \equ(3.|brace|) and \equ(3.|n-in/out|).
Therefore $\lfloor nx\rfloor=n\lfloor x\rfloor\iff
\bigl\lfloor n\{x\}\bigr\rfloor=0\iff
0\le n\{x\}<1\iff \{x\}<1/n$, assuming that $n$ is a positive integer.
(Notice that $n\lfloor x\rfloor\le\lfloor nx\rfloor$ for all~$x$ in this case.)
\ex:
Can something interesting be said about $\lfloor f(x)\rfloor$
when $f(x)$ is a continuous,
monotonically {\it decreasing\/} function that takes integer values only when
$x$~is an integer?
\answer $\lfloor f(x)\rfloor =\lfloor f(\lceil x\rceil )\rfloor $.
\source{Ernst "Mayr", 1982 homework.}
\ex:
Solve the recurrence
\begindisplay
X_n&=n\,,&\qquad\hbox{for $0\le nq$.
\source{"Chace" [|rhind|]; "Fibonacci" [|fibonacci|, pp.~77--83].}
\subhead Basics
\ex: Show that the expression
\begindisplay
\left\lceil 2x+1\over2\right\rceil
-\left\lceil 2x+1\over4\right\rceil
+\left\lfloor 2x+1\over4\right\rfloor
\enddisplay
is always either $\lfloor x\rfloor$ or $\lceil x\rceil$. In what circumstances
does each case arise?
\answer $\lceil x+\half\rceil-\bigi[\hbox{$(2x+1)/4$ is not an integer}\bigr]$
is the nearest integer to~$x$, if $\{x\}\ne\half$;
otherwise it's the nearest even integer.
"!unbiased rounding" "!rounding, unbiased"
(See exercise |rounding|.) Thus the formula gives an ``unbiased'' way to round.
\ex:
Give details of the proof alluded to in the text, that the open interval
$(\alpha\dts\beta)$
contains exactly $\lceil \beta\rceil -\lfloor \alpha\rfloor -1$ integers when
$\alpha<\beta$. Why does the case $\alpha=\beta$ have to be excluded in
order to make the proof correct?
\answer If $n$ is an integer,
$\alphaa]$. We would therefore
get the wrong answer if $\alpha=\beta=\rm integer$.
\ex:\exref|rational-f-to-s|%
Prove that
\begindisplay
\left\lceil n\over m\right\rceil=\left\lfloor n+m-1\over m\right\rfloor\,,
\enddisplay
for all integers $n$ and all positive integers $m$.
[This identity gives us another way to convert ceilings to floors and vice versa,
instead of using the reflective law \eq(|f-c-reflection|).]
\answer Subtract $\lfloor n/m\rfloor$ from both sides, by \equ(3.|n-in/out|),
getting $\lceil(n\bmod m)/m\rceil=\lfloor (n\bmod m+m-1)/m\rfloor$.
Both sides are now equal to $\[n\bmod m>0]$, since $0\le n\bmod m1$
such that
\begindisplay
\lfloor \log_b x \rfloor
= \bigl\lfloor \log_b \lfloor x \rfloor \bigr\rfloor
\enddisplay
for all real~$x \geq 1$.
\answer If and only if
$b$ is an integer. (If $b$ is an integer, $\log_b x$ is a
continuous, increasing function that takes integer values only at
integer points. If $b$ is not an integer, the condition fails
when $x=b$.)
\source{[|knuth1|, exercise 1.2.4--34].}
\ex:
Find the sum of all multiples of $x$ in the closed interval $[\alpha\dts\beta@]$,
when $x>0$.
\answer We have $\sum_k kx\[\alpha\le kx\le\beta]
=x\sum_k k\bigi[\lceil\alpha/x\rceil\le k\le\lfloor\beta/x\rfloor\bigr]$,
which sums to
$\half x\bigl(\lfloor\beta/x\rfloor\lfloor\beta/x+1\rfloor
-\lceil\alpha/x\rceil\lceil\alpha/x-1\rceil\bigr)$.
\ex:
How many of the numbers $2^m$, for $0\le m\le M$, have leading digit~$1$
in decimal notation?
\answer If $10^n\le2^M<10^{n+1}$, there are exactly $n+1$ such powers of~$2$,
because there's exactly one such $k$-digit power of~$2$ for each~$k$.
Therefore the answer is $1+\lfloor M\log 2\rfloor$.\par
Note: The number of powers of~$2$ with leading digit~$l$ is more difficult,
%when $l>1$; it's $\sum_{0\le n1$; it's $\sum_{0\le n\le M}\bigl(\lfloor n\log2-\log l@\rfloor
-\lfloor n\log2-\log(l+1)\rfloor\bigr)$.
\source{1975 midterm.}
\ex:\exref|2-power-floors|%
Evaluate the sums $S_n=\sum_{k\ge1}\bigl\lfloor n/2^k+\half\bigr\rfloor$
and $T_n=\sum_{k\ge1}2^k\bigl\lfloor n/2^k+\half\bigr\rfloor{}^2$.
\answer All terms are the same for $n$ and $n-1$ except the $k$th, where
$n=2^{k-1}q$ and $q$~is odd; we have $S_n=S_{n-1}+1$ and
$T_n=T_{n-1}+2^kq$. Hence $S_n=n$ and $T_n=n(n+1)$.
\ex:
Show that the $n$th element of the sequence
\begindisplay
1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,\ldots
\enddisplay
is $\bigl\lfloor\sqrt{2n}+\half\bigr\rfloor$. (The
sequence contains exactly $m$ occurrences of~$m$.)
\answer $X_n=m\iff\half m(m-1)1$, because $1/\alpha+(\alpha-1)/\alpha=1$.
Find (and prove) an interesting relation between the two multisets
$\spec(\alpha)$ and $\spec\bigl(\alpha/(\alpha+1)\bigr)$,
when $\alpha$ is any positive real number.
\answer Let $\beta=\alpha/(\alpha+1)$. Then the number of times the nonnegative
integer $m$ occurs in $\spec(\beta)$ is exactly one more than the number of times
it occurs in $\spec(\alpha)$. Why? Because $N(\beta,n)=N(\alpha,n)+n+1$.
\ex:\exref|knuth-no-ex|%
Prove or disprove that the "Knuth numbers",
defined by~\eq(|knuth-numbers|),
satisfy $K_n \geq n$ for all nonnegative~$n$.
\answer Continuing the development in the text, if we could find a value
of~$m$ such that $K_m\le m$,
\g \noindent\llap{``}In trying to devise a proof by mathematical "induction", you may fail
for two opposite reasons. You may fail because you try to prove too much:
Your $P(n)$ is too heavy a burden. Yet you may also fail because you
try to prove too little: Your $P(n)$ is too weak a support. In general, you
"!philosophy"
have to balance the statement of your theorem so that the support
is just enough for the burden.''\par\hfill\dash---G. "P\'olya" [|polya|]\g % p119
we could violate the stated inequality at $n+1$ when $n=2m+1$.
(Also when $n=3m+1$ and $n=3m+2$.)
But the existence of such an $m=n'+1$ requires that $2K_{\lfloor n'/2\rfloor}
\le n'$ or $3K_{\lfloor n'/3\rfloor}\le n'$, i.e., that
\begindisplay
K_{\lfloor n'/2\rfloor}\le\lfloor n'/2\rfloor\qquad\hbox{or}\qquad
K_{\lfloor n'/3\rfloor}\le\lfloor n'/3\rfloor\,.
\enddisplay
Aha. This goes down further and further, implying that $K_0\le0$;
but $K_0=1$.\par
What we really want to prove is that $K_n$ is strictly {\it greater\/}
than $n$, for all $n>0$. In fact, it's easy to prove this by induction,
although it's a stronger result than the one we couldn't prove!\par
(This exercise teaches an important lesson. It's more an exercise about the
nature of induction than about properties of the floor function.)
\ex:
Show that the auxiliary "Josephus numbers" \eq(|dm-rec|) satisfy
\begindisplay
\left(q\over q-1\right)^n\le D_n^{(q)}\le q\left(q\over q-1\right)^n\,,
\qquad\hbox{for $n\ge0$}.
\enddisplay
\answer Induction, using the stronger hypothesis
\begindisplay
D_n^{(q)}\le (q-1)\biggl(\left(q\over q-1\right)^{n+1}-1\biggr)\,,
\qquad\hbox{for $n\ge0$}.
\enddisplay
\ex:
Prove that infinitely many of the numbers $D_n^{(3)}$ defined by
\eq(|dm-rec|) are even, and that infinitely many are odd.
\answer If $D_n^{(3)}=2^mb-a$, where $a$ is $0$ or~$1$,
then $D_{n+m}^{(3)}=3^mb-a$.
\ex: Solve the recurrence
\begindisplay
a_0&=1\,;\cr
a_n&=a_{n-1}+\lfloor\sqrt{a_{n-1}}\rfloor,\qquad\hbox{for $n>0$.}\cr
\enddisplay
\answer The key observation is that $a_n=m^2$ implies
$a_{n+2k+1}=(m+k)^2+m-k$ and
$a_{n+2k+2}=(m+k)^2+2m$, for $0\le k\le m$; hence
$a_{n+2m+1}=(2m)^2$. The solution can be written in a nice form discovered
by Carl "Witty":
\begindisplay
a_{n-1}=2^l+\biggl\lfloor\left(n-l\over2\right)^{\!2}\biggr\rfloor\,,
\qquad\hbox{when $2^l+l\le n<2^{l+1}+l+1$.}
\enddisplay
\source{"Brown" [|t-c-brown|].}
\ex:
Show that, in addition to \equ(3.|discrep-rec|), we have
"!discrepancy"
\g There's a discrepancy between this formula and \eq(|discrep-rec|).\g
\begindisplay
D(\alpha,n)\ge D\bigl(\alpha',\lfloor\alpha n\rfloor\bigr)-\alpha^{-1}-2\,.
\enddisplay
\answer $D\bigl(\alpha',\lfloor\alpha n\rfloor\bigr)$ is at most the maximum
of the right-hand side of
\begindisplay
s\bigl(\alpha',\lfloor n\alpha\rfloor,\nu'\bigr)
=-s(\alpha,n,\nu)+S-\epsilon-\{\hbox{$@0$ or $1$}\}-\nu'+\{\hbox{$@0$ or $1$}\}\,.
\enddisplay
\ex:\exref|doubly-exponential-rec|%
Show that the recurrence
"!recurrence, doubly exponential"
\begindisplay
X_0&=m\,,\cr
X_n&=X_{n-1}^2-2\,,\qquad\hbox{for $n>0$},\cr
\enddisplay
has the solution $X_n=\lceil\alpha^{2^n}\rceil$, if $m$ is an integer greater
than~$2$, where
$\alpha+\alpha^{-1}=m$ and $\alpha>1$. For example, if $m=3$ the solution is
\begindisplay
X_n=\lceil\phi^{2^{n+1\,}}\rceil\,,\qquad \phi={1+\sqrt5\over2}\,,
\qquad \alpha=\phi^2\,.
\enddisplay
\answer $X_n=\alpha^{2^n}+\alpha^{-2^n}$, by induction; and $X_n$ is
an integer.
\source{"Aho" and "Sloane" [|aho-sloane|].}
\ex:
Prove or disprove: $\lfloor x\rfloor+\lfloor y\rfloor+\lfloor x+y\rfloor\le
\lfloor2x\rfloor+\lfloor2y\rfloor$.
\answer Here's an ``elegant,\qback'' ``impressive'' proof that gives no
\g This logic is seriously floored.\g
clue about how it was discovered:
\begindisplay \openup2pt
\lfloor x\rfloor+\lfloor y\rfloor+\lfloor x+y\rfloor&=
\bigl\lfloor x+\lfloor y\rfloor\bigr\rfloor+\lfloor x+y\rfloor\cr
&\le\textstyle\bigl\lfloor x+\half\lfloor2y\rfloor\bigr\rfloor+
\bigl\lfloor x+\half\lfloor2y\rfloor+\half\bigr\rfloor\cr
&=\bigl\lfloor2x+\lfloor2y\rfloor\bigr\rfloor=\lfloor2x\rfloor+\lfloor2y\rfloor\,.
\enddisplay
But there's also a simple, graphical proof based on the observation that
we need to consider only the case $0\le x,y<1$. Then the functions look like
this in the plane:
\begindisplay
\unitlength=1pt
\vcenter{\hbox{\beginpicture(40,40)(0,0)
\put(0,0){\line(0,1){40}}
\put(0,0){\line(1,0){40}}
\put(40,0){\line(0,1){40}}
\put(0,40){\line(1,0){40}}
\put(40,0){\line(-1,1){40}}
\put(10,10){\makebox(0,0){$0$}}
\put(30,30){\makebox(0,0){$1$}}
\endpicture}}
\;\le\;
\vcenter{\hbox{\beginpicture(40,40)(0,0)
\put(0,0){\line(0,1){40}}
\put(0,0){\line(1,0){40}}
\put(40,0){\line(0,1){40}}
\put(0,40){\line(1,0){40}}
\put(0,20){\line(1,0){40}}
\put(20,0){\line(0,1){40}}
\put(10,10){\makebox(0,0){$0$}}
\put(10,30){\makebox(0,0){$1$}}
\put(30,10){\makebox(0,0){$1$}}
\put(30,30){\makebox(0,0){$2$}}
\endpicture}}
\;.
\enddisplay
A slightly stronger result is possible, namely
\begindisplay
\lceil x\rceil+\lfloor y\rfloor+\lfloor x+y\rfloor\le\lceil2x\rceil
+\lfloor2y\rfloor\,;
\enddisplay
but this is stronger only when $\{x\}=\half$. If we replace $(x,y)$ by
$(-x,x+y)$ in this identity and apply the reflective law \equ(3.|f-c-reflection|),
we get
\begindisplay
\lfloor y\rfloor+\lfloor x+y\rfloor+\lfloor2x\rfloor\le
\lfloor x\rfloor+\lfloor2x+2y\rfloor\,.
\enddisplay
\source{"Greitzer" [|olympiads1|, problem 1972/3, solution 2].}
\ex:
Let $\Vert x\Vert=\min\bigl(x-\lfloor x\rfloor,\lceil x\rceil-x\bigr)$ denote the
distance from $x$ to the nearest integer. What is the value of
\begindisplay
\sum_k 2^k\bigl\Vert x/2^k\bigr\Vert^2\,?
\enddisplay
(Note that this sum can be "doubly infinite".
For example, when $x=1/3$ the terms are
nonzero as $k\to-\infty$ and also as $k\to+\infty$.)
\answer Let $f(x)$ be the sum in question. Since $f(x)=f(-x)$, we may assume
that $x\ge0$. The terms are bounded by $2^k$ as $k\to-\infty$ and by
$x^2\!/2^k$ as $k\to+\infty$, so the sum exists for all real~$x$.\par
We have $f(2x)=2\sum_k2^{k-1}\Vert x/2^{k-1}\Vert^2=2f(x)$.
Let $f(x)=l(x)+r(x)$ where $l(x)$ is the sum for $k\le0$ and $r(x)$ is the
sum for $k>0$. Then $l(x+1)=l(x)$, and $l(x)\le1/2$ for all~$x$.
When $0\le x<1$, we have $r(x)=x^2\!/2+x^2\!/4+\cdots=x^2$, and $r(x+1)=
(x-1)^2\!/2+(x+1)^2\!/4+(x+1)^2\!/8+\cdots=x^2+1$. Hence $f(x+1)=f(x)+1$,
when $0\le x<1$.\par
We can now prove by induction that $f(x+n)=f(x)+n$ for all integers $n\ge0$,
when $0\le x<1$. In particular, $f(n)=n$. Therefore in general, $f(x)=
2^{-m}f(2^mx)=2^{-m}\lfloor2^mx\rfloor+2^{-m}f\bigl(\{2^mx\}\bigr)$. But
$f\bigl(\{2^mx\}\bigr)=l\bigl(\{2^mx\}\bigr)+r\bigl(\{2^mx\}\bigr)\le
\half+1$; so $\bigl\vert f(x)-x\bigr\vert\le\bigl\vert2^{-m}\lfloor2^mx\rfloor
-x\bigr\vert+2^{-m}\cdt{3\over2}\le2^{-m}\cdt{5\over2}$ for all
integers~$m$.\par
The inescapable conclusion is that $f(x)=\vert x\vert$ for all real~$x$.
\source{[|graham-knuth|].}
\subhead Exam problems
\ex:
A circle, $2n-1$ units in diameter, has been drawn symmetrically on a
$2n\times2n$ chessboard, illustrated here for $n=3$:
\begindisplay
\unitlength=8pt
\beginpicture(6,6)(0,0)
\multiput(0,0)(1,0){7}{\line(0,1){6}}
\multiput(0,0)(0,1){7}{\line(1,0){6}}
\thicklines
\put(3,3){\circle{5}}
\endpicture
\enddisplay
\itemitem{a}How many cells of the board contain a segment of the circle?
\itemitem{b}Find a function $f(n,k)$ such that exactly $\sum_{k=1}^{n-1}f(n,k)$
cells of the board lie entirely within the circle.
\answer Let $r=n-\half$ be the radius of the circle. (a)~There are $2n-1$
horizontal lines and $2n-1$ vertical lines between cells of the board, and the
circle crosses each of these lines twice. Since $r^2$ is not an integer, the
"Pythagorean theorem" tells us that the circle doesn't pass through the
corner of any cell. Hence the circle passes through as many cells as there
are crossing points, namely $8n-4=8r$. (The same formula gives
the number of cells
at the edge of the board.)
(b)~$f(n,k)=4\lfloor\sqrt{r^{2\mathstrut}-k^2}\rfloor$.\par
It follows from (a) and (b) that
\begindisplay
{\textstyle{1\over4}}\pi r^2-2r\le\sum_{01]$,
for $j\ge1$.
\source{1970 midterm.}
\ex: Simplify the formula $\bigl\lfloor(n+1)^2n!\mskip2mue\bigr\rfloor\bmod n$.
\g Simplify it, but don't change the value.\g
\answer $(n+1)^2n!\mskip2mue=A_n+(n+1)^2+(n+1)+B_n$, where
\begindisplay
A_n&={(n+1)^2n!\over0!}
+{(n+1)^2n!\over1!}+\cdots
+{(n+1)^2n!\over(n-1)!}
\enddisplay
is a multiple of $n$ and
\begindisplay \openup3pt
B_n&={(n+1)^2n!\over(n+2)!}
+{(n+1)^2n!\over(n+3)!}+\cdots\cr
&={n+1\over n+2}\biggl(1+{1\over n+3}+{1\over(n+3)(n+4)}+\cdots\,\biggr)\cr
&<{n+1\over n+2}\biggl(1+{1\over n+3}+{1\over(n+3)(n+3)}+\cdots\,\biggr)\cr
&={(n+1)(n+3)\over(n+2)^2}
\enddisplay
is less than $1$. Hence the answer is $2\bmod n$.
\source{1975 midterm.}
\ex:
Assuming that $n$~is a nonnegative integer, find a closed form for the sum
\begindisplay
\sum_{1< k < 2^{2^n}}
{1\over 2^{\lfloor \lg k \rfloor}4^{\lfloor \lg\lg k \rfloor}}\,.
\enddisplay
\answer The sum is
\begindisplay \openup3pt
&\sum_{k,l,m}2^{-l}4^{-m}\bigi[m=\lfloor\lg l\rfloor\bigr]
\bigi[l=\lfloor\lg k\rfloor\bigr]\[11$.\par
But the argument just given relies on a difficult theorem
about uniform distribution.
An elementary proof is possible, sketched here for $n=2$: Let $P_m$
be the point $\bigl(\{mx\},\{my\}\bigr)$. Divide the unit square $0\le x,y<1$
into triangular regions $A$ and~$B$ according as $x+y<1$ or $x+y\ge1$.
We want to show that $P_m\in B$ for some~$m$, if $\{x\}$ and $\{y\}$ are
nonzero. If $P_1\in B$, we're done. Otherwise there is a disk~$D$ of
radius $\epsilon>0$ centered at~$P_1$ such that $D\subseteq A$. By
Dirichlet's box principle, the sequence $P_1$, \dots,~$P_N$ must contain
two points with $\vert P_k-P_j\vert<\epsilon$ and $k>j$, if $N$~is large
enough.
\begindisplay
\unitlength=1pt
\beginpicture(100,60)(-10,0)
\put(0,0){\line(0,1){60}}
\put(0,0){\line(1,0){60}}
\put(60,0){\line(0,1){60}}
\put(0,60){\line(1,0){60}}
\put(60,0){\line(-1,1){60}}
\put(10,40){\circle{10}}
\put(10,40){\disk{1}}
\put(0,0){\line(1,4){10}}
\put(-10,40){\makebox(0,0){$P_1$}}
\put(50,20){\circle{10}}
\put(50,20){\disk{1}}
\put(60,60){\line(-1,-4){10}}
\put(85,20){\makebox(0,0){$(1,1)-P_1$}}
\put(25,15){\makebox(0,0){$A$}}
\put(35,45){\makebox(0,0){$B$}}
\endpicture
\enddisplay
It follows that $P_{k-j-1}$ is within $\epsilon$ of $(1,1)-P_1$;
hence $P_{k-j-1}\in B$.
\source{1974 midterm.}
\ex:
Prove that the double sum
$\sum_{0 \leq k \leq \log_b \! x} \sum_{0 < j < b}
\lceil (x + jb^k)/b^{k+1} \rceil$
equals $(b-1)\bigl(\lfloor \log_b x \rfloor + 1\bigr) + \lceil x \rceil - 1$,
for every real number~$x \geq 1$ and every integer~$b>1$.
\answer Replace $j$ by $b-j$ and add the term $j=0$ to the sum, so
that exercise |c-replicative| can be used for the sum on~$j$. The
result,
\begindisplay
\textstyle \lceil x/b^k\rceil-\lceil x/b^{k+1}\rceil+b-1\,,
\enddisplay
telescopes
when summed on~$k$.
\source{1971 midterm.}
\ex:
The "spiral function"~$\sigma(n)$, indicated in the diagram below,
maps a nonnegative integer~$n$ onto an ordered pair of
integers~$\bigl(x(n),y(n)\bigr)$.
For example, it maps $n=9$ onto the ordered pair~$(1,2)$.
\g\vskip30pt People in the southern hemisphere use a different spiral.\g
\begindisplay
\unitlength=2pt
\beginpicture(74,74)(-37,-35)
\put(-37,0){\vector(1,0){74}}
\put(37,-5){\hbox{$x$}}
\put(0,-37){\vector(0,1){74}}
\put(2,37){\hbox{$y$}}
\multiput(-30,-30)(10,0){7}{%
\makebox(0,0){%
\beginpicture(0,0)(0,0)
\multiput(0,0)(0,10){7}{\disk{1.5}}
\endpicture
}
}
\put(1,-3){\makebox(4,5){$0$}}
\put(1,10){\makebox(4,0){$1$}}
\put(-15,10){\makebox(4,0){$2$}}
\put(-15,-3){\makebox(4,5){$3$}}
\put(-15,-13){\makebox(4,5){$4$}}
\put(1,-13){\makebox(4,5){$5$}}
\put(10,-13){\makebox(4,5){$6$}}
\put(11,-3){\makebox(4,5){$7$}}
\put(11,10){\makebox(4,0){$8$}}
\put(11,20){\makebox(4,0){$9$}}
\thicklines
\put(0,0){\line(0,1){10}}
\put(0,10){\line(-1,0){10}}
\put(-10,10){\line(0,-1){20}}
\put(-10,-10){\line(1,0){20}}
\put(10,-10){\line(0,1){30}}
\put(10,20){\line(-1,0){30}}
\put(-20,20){\line(0,-1){40}}
\put(-20,-20){\line(1,0){40}}
\put(20,-20){\line(0,1){50}}
\put(20,30){\line(-1,0){50}}
\put(-30,30){\line(0,-1){60}}
\put(-30,-30){\line(1,0){60}}
\put(30,-30){\vector(0,1){67}}
\endpicture
\enddisplay
\itemitem{a}Prove that if $m=\lfloor\sqrt n\rfloor$,
\begindisplay
x(n)=(-1)^m\Bigl(\bigl(n-m(m+1)\bigr)\cdt\bigi[\lfloor2\sqrt n\rfloor
\hbox{ is even}\bigr]+\lceil\textstyle\half m\rceil\Bigr)\,,
\enddisplay
and find a similar formula for $y(n)$. \Hint: Classify the spiral
into segments $W_k$, $S_k$, $E_k$, $N_k$ according as $\lfloor2\sqrt n\rfloor
=4k-2$, $4k-1$, $4k$, $4k+1$.
\itemitem{b}Prove that, conversely, we can determine $n$ from $\sigma(n)$ by a
formula of the form
\begindisplay
n=(2k)^2\pm\bigl(2k+x(n)+y(n)\bigr)\,,\quad k=\max\bigl(\vert x(n)\vert,
\vert y(n)\vert\bigr).
\enddisplay
Give a rule for when the sign is $+$ and when the sign is $-$.
\answer Let $\lfloor2\sqrt n\rfloor=4k+r$ where $-2\le r<2$, and let
$m=\lfloor\sqrt n\rfloor$. Then the following
relationships can be proved by induction:
{\parindent=0pt
\begindisplay
%\ifodd\pageno\kern-7pc\fi\vbox{\offinterlineskip
\vbox{\offinterlineskip
\halign{&\bigstrut\hfil$#$\hfil&\ \vrule#\ \cr
\rm segment&&r&&m&&x&&y&&\hbox{if and only if}\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit\cr
W_k&&-2&&2k{-}1&&m(m{+}1)-n-k&&k&&(2k{-}1)(2k{-}1)\le n\le(2k{-}1)(2k)\cr
S_k&&-1&&2k{-}1&&-k&&m(m{+}1)-n+k&&(2k{-}1)(2k)< n<(2k)(2k)\cr
E_k&&0&&2k&&n-m(m{+}1)+k&&-k&&(2k)(2k)\le n\le(2k)(2k{+}1)\cr
N_k&&1&&2k&&k&&n-m(m{+}1)-k&&(2k)(2k{+}1)< n<(2k{+}1)(2k{+}1)\cr}}
\enddisplay}% cancel the zero parindent
Thus, when $k\ge1$, $W_k$ is a segment of length~$2k$ where the path travels
west and $y(n)=k$; $S_k$~is a segment of length~$2k-2$ where the path
travels south and $x(n)=-k$; etc. (a)~The desired formula is therefore
\begindisplay
y(n)=(-1)^m\Bigl(\bigl(n-m(m+1)\bigr)\cdt\bigi[\lfloor2\sqrt n\rfloor
\hbox{ is odd}\bigr]-\lceil\textstyle\half m\rceil\Bigr)\,.
\enddisplay
(b) On all segments, $k=\max\bigl(\vert x(n)\vert,\vert y(n)\vert\bigr)$.
On segments $W_k$ and $S_k$ we have $x0$. Prove that
$f(n)=\lfloor n\phi\rfloor$ and $g(n)=\lfloor n\phi^2\rfloor$,
where $\phi=(1+\sqrt5\,)/2$.
\answer Since $1/\phi+1/\phi^2=1$, the stated sequences do partition the
positive integers. Since the condition $g(n)=f\bigl(f(n)\bigr)+1$ determines
$f$ and $g$ uniquely, we need only show that
$\bigl\lfloor\lfloor n\phi\rfloor\phi\bigr\rfloor+1=\lfloor n\phi^2\rfloor$
for all $n>0$. This follows from exercise |irrat-div|, with $\alpha=\phi$
and $n=1$.
\source{"Klamkin" [|olympiads2|, problem 1978/3].}
\ex:
Do there exist real numbers $\alpha$, $\beta$, and $\gamma$ such that
"!spectrum"
$\spec(\alpha)$, $\spec(\beta)$, and $\spec(\gamma)$ together partition
the set of positive integers?
\answer No; an argument like the analysis of the two-spectrum
case in the text and in exercise |nasc-spec-part| shows that a tripartition
occurs if and only if $1/\alpha+1/\beta+1/\gamma=1$ and
\begindisplay
\left\{n+1\over\alpha\right\}+\left\{n+1\over\beta\right\}
+\left\{n+1\over\gamma\right\}=1\,,
\enddisplay
for all $n>0$. But the average value of $\bigl\{(n+1)/\alpha\bigr\}$ is $1/2$
if $\alpha$ is irrational, by the theorem on uniform distribution.
The parameters can't all be rational, and if $\gamma=m/n$ the average
is $3/2-1/(2n)$. Hence $\gamma$ must be an integer, but this doesn't
work either.
(There's also a proof of impossibility that uses only simple principles,
without the theorem on uniform distribution; see [|young-ron|].)
\source{"Uspensky" [|uspensky|].}
\goodbreak
\ex:
Find an interesting interpretation of the "Knuth numbers", by "unfolding" the
recurrence \eq(|knuth-numbers|).
\answer One step of unfolding the recurrence for $K_n$ gives the minimum
of the four numbers $1+a+a\cdt b\cdt K_{\lfloor(n-1-a)/(a\cdt b)\rfloor}$,
where $a$ and~$b$ are each $2$ or~$3$. (This simplification involves
an application of \equ(3.|rational-in/out|) to remove floors within floors,
together with the identity $x+\min(y,z)=\min(x+y,x+z)$.
We must omit terms with negative subscripts; i.e., with $n-1-a<0$.)\par
Continuing along such lines now leads to the following interpretation:
$K_n$ is the least number $>n$ in the multiset~$S$ of all numbers of the form
\begindisplay
1+a_1+a_1a_2+a_1a_2a_3+\cdots+a_1a_2a_3\ldots a_m\,,
\enddisplay
where $m\ge0$ and each $a_k$ is $2$ or $3$. Thus,
\begindisplay
S=\{1,3,4,7,9,10,13,15,19,21,22,27,28,31,31,\ldots\,\}\,;
\enddisplay
the number $31$ is in~$S$ ``twice'' because it has two representations
$1+2+4+8+16=1+3+9+18$.
(Incidentally, Michael "Fredman" [|fredman-thesis|] has shown that
$\lim_{n\to\infty}K_n/n=1$, i.e., that $S$ has no enormous gaps.)
\ex:
Show that there are integers $a_n^{(q)}$ and $d_n^{(q)}$ such that
\begindisplay
a_n^{(q)}={D_{n-1}^{(q)}+d_n^{(q)}\over q-1}
={D_n^{(q)}+d_n^{(q)}\over q}\,,\qquad\hbox{for $n>0$,}
\enddisplay
when $D_n^{(q)}$ is the solution to \eq(|dm-rec|). Use this fact to obtain
another form of the solution to the generalized "Josephus problem":
\begindisplay
J_q(n)=1+d_k^{(q)}+q(n-a_k^{(q)}),
\qquad\hbox{for $a_k^{(q)}\le n0$},\cr
\enddisplay
if $m$ is a positive integer.
\answer Let $\alpha>1$ satisfy $\alpha+1/\alpha=2m$.
\g Too easy.\g
Then we find
$2Y_n=\alpha^{2^n}+\alpha^{-2^n}$, and it follows that
$Y_n=\bigl\lceil\alpha^{2^n}\!/2\bigr\rceil$.
\source{"Aho" and "Sloane" [|aho-sloane|].}
\ex:
Prove that if
$n=\bigl\lfloor\bigl(\sqrt 2^{\,l}+\sqrt 2^{\,l-1}\bigr)m\bigr\rfloor$, where
$m$ and $l$ are nonnegative integers, then
$\bigl\lfloor\sqrt{2n(n+1)}\bigr\rfloor=
\bigl\lfloor\bigl(\sqrt 2^{\,l+1}+\sqrt 2^{\,l}\bigr)m\bigr\rfloor$. Use this
remarkable property to find a closed form solution to the recurrence
\begindisplay\openup3pt
L_0&=a\,,&\qquad\hbox{integer $a>0$;}\cr
L_n&=\bigl\lfloor\,\sqrt{2L_{n-1}(L_{n-1}+1)}\,\bigr\rfloor\,,
&\qquad\hbox{for $n>0$.}\cr
\enddisplay
\Hint: $\bigl\lfloor\sqrt{2n(n+1)}\bigr\rfloor=
\bigl\lfloor\sqrt 2(n+\half)\bigr\rfloor$.
\answer The hint follows from \equ(3.|floor-in-sqrt|), since $2n(n+1)=
\bigl\lfloor2(n+\half)^2\bigr\rfloor$. Let
$n+\theta=\bigl(\sqrt 2^{\,l}+\sqrt 2^{\,l-1}\bigr)m$ and
$n'+\theta'=\bigl(\sqrt 2^{\,l+1}+\sqrt 2^{\,l}\bigr)m$,
where $0\le \theta,\theta'<1$.
Then $\theta'=2\theta\bmod1=2\theta-d$, where $d$~is $0$ or~$1$.
We want to prove that $n'=\bigl\lfloor\sqrt 2(n+\half)\bigr\rfloor$;
this equality holds if and only if
\begindisplay
0\le \theta'(2-\sqrt2\,)+\sqrt2(1-d)<2\,.
\enddisplay
To solve the recurrence, note that $\spec(1+1/\sqrt2\,)$ and
$\spec(1+\sqrt2\,)$ partition the positive integers; hence any positive
integer~$a$ can be written uniquely in the form
$a=\bigl\lfloor\bigl(\sqrt 2^{\,l}+\sqrt 2^{\,l-1}\bigr)m\bigr\rfloor$,
where $l$ and~$m$
are integers with $m$~odd and $l\ge0$. It follows that
$L_n=\bigl\lfloor(\sqrt 2^{\,l+n}+\sqrt 2^{\,l+n-1})m\bigr\rfloor$.
\source{"Graham" and "Pollak" [|graham-pollak|].}
\ex:
The function $f(x)$ is said to be {\it "replicative"\/} if it satisfies
\begindisplay
f(mx)
= f(x) + f \Bigl( x + {1\over m} \Bigr) + \cdots
+ f \Bigl( x + {m-1\over m} \Bigr)
\enddisplay
for every positive integer~$m$.
Find necessary and sufficient conditions on the real number~$c$ for the
following functions to be replicative:
\smallskip
\itemitem{a}$f(x)=x+c$.
\smallskip
\itemitem{b}$f(x)=[x+c$ is an integer$]$.
\smallskip
\itemitem{c}$f(x)=\max\bigl(\lfloor x\rfloor,c\bigr)$.
\smallskip
\itemitem{d}$f(x)=x+c\lfloor x\rfloor-\half[x$ is not an integer$]$.
\answer (a) $c=-\half$. (b)~$c$ is an integer. (c)~$c=0$.
(d)~$c$~is arbitrary. See the answer to exercise 1.2.4--40 in
[|knuth1|] for more general results.
\ex:
Prove the identity
\begindisplay
x^3=3x\bigl\lfloor x\lfloor x\rfloor\bigr\rfloor
+3\{x\}\bigl\{x\lfloor x\rfloor\bigr\}
+\{x\}^3
-3\lfloor x\rfloor\bigl\lfloor x\lfloor x\rfloor\bigr\rfloor
+\lfloor x\rfloor^3\,,
\enddisplay
and show how to obtain similar formulas for $x^n$ when $n>3$.
\answer \def\:#1{^{{:}#1}}Let $x\:0=1$ and $x\:{(k+1)}=x\lfloor x\:k\rfloor$;
also let $a_k=\{x\:k\}$ and $b_k=\lfloor x\:k\rfloor$, so that the stated
identity reads $x^3=3x\:3+3a_1a_2+a_1^3-3b_1b_2+b_1^3$. Since $a_k+b_k=
x\:k=xb_{k-1}$ for $k\ge0$, we have $(1-xz)(1+b_1z+b_2z^2+\cdots)=
1-a_1z-a_2z^2-\cdots\,$; thus
\begindisplay
{1\over 1-xz}={1+b_1z+b_2z^2+\cdots\over1-a_1z-a_2z^2-\cdots}\,.
\enddisplay
Take the logarithm of both sides, to separate the $a$'s from the $b$'s. Then
differentiate with respect to~$z$, obtaining
\begindisplay
{x\over1-xz}=
{a_1+2a_2z+3a_3z^2+\cdots\over1-a_1z-a_2z^2-\cdots}+
{b_1+2b_2z+3b_3z^2+\cdots\over1+b_1z+b_2z^2+\cdots}\,.
\enddisplay
The coefficient of $z^{n-1}$ on the left is $x^n$; on the right it is
a formula that matches the given identity when $n=3$.
\par Similar identities for the more general product $x_0x_1\ldots x_{n-1}$
can also be derived~[|haaland-knuth|].
\source{"H{\aa}land" and "Knuth" [|haaland-knuth|].}
\ex:
Find a necessary and sufficient condition on the
real numbers $0\le\alpha<1$ and $\beta\ge0$ such that we can determine
$\alpha$ and $\beta$ from the infinite multiset of values
\begindisplay
\bigl\{\,\lfloor n\alpha\rfloor+\lfloor n\beta\rfloor\bigm\vert
\hbox{$n>0$}\,\bigr\}\,.
\enddisplay
\answer (Solution by Heinrich "Rolletschek".) We can replace $(\alpha,\beta)$
\g A more interesting (still unsolved) problem: Restrict both $\alpha$
and $\beta$ to be $<1$, and ask when the given multiset determines the
unordered pair~$\{\alpha,\beta\}$.\g
by $(\{\beta\},\allowbreak{\alpha+\lfloor\beta\rfloor})$
without changing $\lfloor n\alpha
\rfloor+\lfloor n\beta\rfloor$. Hence the condition $\alpha=\{\beta\}$ is
necessary. It is also sufficient: Let $m=\lfloor\beta\rfloor$ be the least
element of the given multiset, and let $S$ be the multiset obtained from the
given one by subtracting $mn$ from the $n$th smallest element, for all~$n$.
If $\alpha=
\{\beta\}$, consecutive elements of~$S$ differ by either $0$ or~$2$, hence
the multiset $\half S=\spec(\alpha)$ determines $\alpha$.
\source{R.\thinspace L. "Graham" and D.\thinspace R. "Hofstadter".*}
\subhead Research problems
\ex:
Find a necessary and sufficient condition on the
nonnegative real numbers $\alpha$ and $\beta$ such that we can determine
$\alpha$ and $\beta$ from the infinite multiset of values
\begindisplay
\bigl\{\,\bigl\lfloor\lfloor n\alpha\rfloor\beta\bigr\rfloor\bigm\vert
\hbox{$n>0$}\,\bigr\}\,.
\enddisplay
\answer According to unpublished notes of William~A. "Veech", it is sufficient
to have $\alpha\beta$, $\beta$, and~$1$ linearly independent
over the rationals.
\ex:
Let $x$ be a real number $\ge\phi=\half(1+\sqrt5@)$.
The solution to the recurrence
\begindisplay
Z_0(x)&=x\,,\cr
Z_n(x)&=Z_{n-1}(x)^2-1\,,\qquad\hbox{for $n>0$},\cr
\enddisplay
can be written $Z_n(x)=\bigl\lceil f(x)^{2^n}\bigr\rceil$, if $x$ is an integer,
where
\begindisplay
f(x)=\lim_{n\to\infty}Z_n(x)^{1/2^n}\,,
\enddisplay
"!recurrence, doubly exponential"
because $Z_n(x)-1