% Bugs (sigh) in Concrete Math

\input gkpmac
\preprintfalse
\raggedbottom
\def\rightcorner{\vbox to\folioht{\vfil}\relax}
\pageno=627

\def\today{\number\day\
  \ifcase\month\or
  Jan\or Feb\or Mar\or Apr\or May\or Jun\or
  Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi
  \ \number\year}

\def\cutpar{{\parfillskip=0pt\par}}

\beginchapter {} Concrete Math Errata VII

THIS IS A LIST
\g``And if you happen in reading to finde any more faultes not here
mentioned, as peraduenture you may, \dots\
I trust you will therefore impute no blame either vnto me or to the
Printer, but gently amend and correct them, accepting our good minde,
which was to haue had the booke passed to your handes vtterly
without fault, as touching the Printing.''\par
\hfill\dash---from the first\par
\hfill English edition\par
\hfill of Euclid [80]\g
 of all corrections made to the seventh printing (December 1991)
of {\sl Concrete Mathematics\/} by Graham, Knuth, and Patashnik.
(Differences between the seventh printing and earlier printings
can be found in separate lists.)
With these changes, the book should be perfect.

But you may disagree.
To claim a reward for any anomalies you spot that aren't shown here,
please send your comments to D.~E. Knuth, Computer Science Department,
Stanford University, Stanford CA 94305, as soon as possible.

\def\bugonpage#1(#2) \par{\bigbreak
  \vbox{\hrule width\hsize}
  \line{\lower3.5pt\vbox to13pt{}Page #1\hfil(#2)}%
  \nobreak\vskip-5pt
  \vbox{\hrule width\hsize}
  \nobreak\medskip}

\def\bib#1 {\noindent\hbox to\parindent{\bf#1\hss}\hangindent\parindent}

%\vskip.7in % reduce this if there's more before the marginal stuff

\bugonpage 18, bottom three lines (5 Aug 92)

\item{}$n$
different sizes of disks and exactly $m_k$ disks of size~$k$.
Determine $A(m_1,\ldots,m_n)$, the minimum number of moves needed to transfer
a tower when equal-size disks are considered to be indistinguishable.

\bugonpage 23, line 6 (27 Jul 92)

\noindent
divisible by~$p$.
Its value for large~$N$ is approximately $\ln\ln N+0.2614972128$;\cutpar

\bugonpage 44, lines 5 and 6 from the bottom (27 May 92)

\vskip-20pt \def\chapno{2} \eqcount=39
\begindisplay
\eqalign{R_0&=\alpha\,;\cr
   R_n	&= R_{n-1} + \beta + \gamma n+\delta n^2\,, \qquad\hbox{for $n>0$,}\cr
}\eqno
\enddisplay

\bugonpage 89, in four places (19 Aug 92)

\noindent[Change the notation `$[\hbox{$@0$ or $1$}]$' to
`$\{\hbox{$@0$ or $1$}\}$'.

\bugonpage 89, lines 14 and 15 (19 Aug 92)

\noindent
Here $\epsilon$ is a positive error of at most $v\alpha^{-1}$.
Exercise~18 proves that $S$ is, simi\-larly, between $0$
and~$\lceil v\alpha^{-1@}\rceil$. And we can remove the term
for $j=\lceil n\alpha\rceil-1=$\cutpar

\bugonpage 89, line 4 from the bottom (19 Aug 92)

\noindent
reduced to a similar sum
of at most $\lceil\alpha n\rceil$~terms. Everything else cancels out\cutpar

\bugonpage 96, line 7 from the bottom (19 Aug 92)

\excount=17
\ex:
Prove that the boundary-value error term $S$ in \equ(3.30) is
at most $\lceil\alpha^{-1}v\rceil$.\cutpar

\bugonpage 109, line 4 from the bottom (30 Apr 92)

\noindent
$216091$, and $756839$.

\bugonpage 202, line 6 from the bottom (19 Jan 92)

\noindent
which we haven't seen before; it satisfies the basic identity

\bugonpage 203, new graffito at top of page (19 Jan 92)

\noindent
\g The power series for $\Bscr_{1/2_{\mathstrut}}(z)^r
=(\sqrt{z^{2\mathstrut}+4}+z)^{2r}\!/4^r$
is noteworthy too.\g

\bugonpage 251, new graffito near {(6.18)} (10 Feb 92)

\noindent
\g$n^m(-1)^{n-m}{n\brack m}$\par
\vskip6pt
$\quad=\sum\limits_k\!{\,n\,\brack\, k\,}{-m\choose k-m}n^k\,.$\kern-10pt\null\g

\bugonpage 251, line 5 from the bottom (8 Feb 92)

\vskip-20pt \def\chapno{6} \eqcount=24
\begindisplay
\noalign{\g\vskip20pt Also,\par\vskip6pt
${n\choose m}(n-1)\_{n-m}$\par\vskip6pt
$\quad=\sum_k{\,n\,\brack\,k\,}{k\brace m}\,,$\par\vskip6pt
a generalization of~\equ(6.9).\g}
n\_{n-m}\,\[n\ge m]&=
\sum_k{n+1\brack k+1}{k\brace m}(-1)^{m-k}\,.\eqno
\enddisplay

\bugonpage 276, line 6 from the bottom (10 Feb 92)

\vskip-20pt \def\chapno{6} \eqcount=100
\begindisplay
{B_m\over m!}=-m\sigma_m(0)\,.
\eqno
\enddisplay

\bugonpage 331, line 10 from the bottom (10 Dec 91)

\noindent
of the denominator.
The easiest way to compute the coefficients of $\check C(z)$ is\cutpar

\bugonpage 332, line 2 (10 Dec 91)

\noindent
${\check C}_n=[z^n]\,\check C(z)$ as follows, when $n=10q+r$
and $0\le r<10$:

\bugonpage 435, bottom line in margin (19 Aug 92)

\g$n\le10$.\g

\bugonpage 472, lines 14 and 15 (6 Dec 89)

\noindent
Things are looking reasonably good, since we know how to approximate
${(n\pm k)}!$ when $n$ is large and $k$ is small.

\parindent=30pt % for the Answers

\bugonpage 492, lines 11--14 from the bottom (31 Dec 91)

\textindent{3.5}%
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.8) and \equ(3.6).
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.)

\bugonpage 493, lines 14--16 (19 Aug 92)

\noindent
value $m-1$ occurs in neither spectrum,
and $m$ occurs in both.
(However, "Golomb"~[121] has observed that the sets
$\{\lfloor n\alpha\rfloor\mid n\ge1\}$ and 
$\{\lceil n\beta\rceil-1\mid n\ge1\}$ always do form a partition,
when $1/\alpha+1/\beta = 1$.)

\bugonpage 494, lines 2 and 3 (19 Aug 92)

\noindent
there's exactly one such $k$-digit power of~$2$ for each~$k$.
Therefore the answer is $1+\lfloor M\log 2\rfloor$.\par

\bugonpage 494, line 7 from the bottom (31 Dec 91)

\textindent{3.27}%
If $D_n^{(3)}=2^mb-a$, where $a$ is $0$ or~$1$,
then $D_{n+m}^{(3)}=3^mb-a$.

\bugonpage 494, bottom line (19 Aug 92)

\vskip-20pt
\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

\bugonpage 555, line 4 from the bottom (6 Feb 92)

\noindent
$\Pr\pbigi((S-6)^2\ge94^2\bigr)\le 22/94^2\approx.0025$.
(c)~The second tail inequality says that\cutpar

\bugonpage 573, line 11 (7 Dec 91)

\noindent
giving a fairly sharp asymptotic estimate in terms of the quantity $\Theta$ in
\equ(9.93):

\let\,=\thinspace \frenchspacing
\parindent=22pt \tolerance=1000 % for the Bibliography


\parindent=30pt % for the Credits


\parindent=0pt % for the Index

\bugonpage 607, subentry under Bernoulli, Jakob (16 Jan 92)

\noindent\quad polynomials, 353--354, 456--461.

\bugonpage 609, subentry under Convolution (30 Jul 91)

\noindent\quad identities for, 202, 258, 359.

\bugonpage 611, left column (4 Jun 92)

\noindent
Euclid (= {\textfont1=\teni \mathchardef\varsigma=294 $E%
{\buildrel\,\smash{\hbox{\gmathtext,}}\over{\upsilon}}%
  \kappa\lambda\epsilon\acute\iota\delta\eta\varsigma$}), 107--108, 584.

\bugonpage 615, subentry under Iverson (17 Oct 91)

\noindent\quad convention, 24, 31, 34, 68, 75, 588.

\bugonpage 620, right column (8 Feb 92)

\noindent Sorting, 28, 79, 175, 340, 364, 434.

\bye
