% 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 IX 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 changes that correct all known errors in the eighth printing (October 1992) of {\sl Concrete Mathematics\/} by Graham, Knuth, and Patashnik. (The ninth printing, spring 1993, was identical to the eighth. Differences between the eighth printing and earlier printings can be found in separate lists.) With these changes, the book should be perfect. The second edition (February 1994) incorporates these corrections and also makes a number of changes to historical and bibliographic items, not listed here. The second edition also includes an extended index, updates to the research problems, new material about Zeilberger's important extension of Gosper's algorithm, and general improvements here and there. If you find any anomalies in the second edition, 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} \vskip1in \bugonpage 132, line 10 from the bottom (5 Feb 93) Now suppose we pair up each number between $1$~and~$p-1$ with its inverse. \bugonpage 166, marginal note (31 Aug 93) \noindent \g(Well, it's actually ${}\kern2pt\half\sqrt\pi (1+\mathop{\rm erf}\alpha)$, a constant plus a multiple of the ``"error function"'' of~$\alpha$, if we're willing to accept that as a closed form.)\g \bugonpage 213, line 3 from the bottom (29 Jul 93) \noindent tions. If we replace $x$ by $-n-\epsilon$ and let $\epsilon\to0$, two applications of \equ(5.87)\cutpar \bugonpage 214, line 10 (29 Jul 93) \vskip-20pt \begindisplay \qquad=(-1)^n{(2n)!\over n!} {(a+b+2n-1)\_^n\over a\_^n\,b\_^n}\,,\qquad\hbox{integer $n\ge0$}. \enddisplay \bugonpage 241, line 9 (21 Jan 93) \vskip-20pt \begindisplay \openup3pt &\hyp{\half a,\,\half a+\half,\,1+a-b-c}{1+a-b,\,1+a-c}{{-4z\,\over(1-z)^2}}\cr \enddisplay \bugonpage 300, lines 5 and 6 from the bottom (29 Jul 93) \itemitem{b}Prove that ${p-1\brack k}\=1$ \tmod p, for $1\le k
2$.
\bugonpage 304, line 18 from the bottom (27 Sep 93)
\item{83}
Let $\alpha$ be an irrational number in $(@0\dts1)$ and let $a_1$, $a_2$,
$a_3$,~\dots\ be the\cutpar
\bugonpage 365, line 19 (28 Jun 93)
\unitlength=3pt
\def\Domh{\beginpicture(3,1)(-.5,0) % horizontal, stand-alone
\put(2,0){\line(0,1){1}}
\put(0,0){\line(0,1){1}}
\put(0,0){\line(1,0){2}}
\put(0,1){\line(1,0){2}}
\endpicture}
\def\Domv{\beginpicture(2,2)(-.5,0) % vertical, stand-alone
\put(0,0){\line(0,1){2}}
\put(1,0){\line(0,1){2}}
\put(0,0){\line(1,0){1}}
\put(0,2){\line(1,0){1}}
\endpicture}
\vskip-20pt
\begindisplay
2^{mn/2}\prod\twoconditions{1\le j\le m}{1\le k\le n}
\biggl(\Bigl(\cos^2{j\pi\over m+1}\Bigr)\Domv^2
+\Bigl(\cos^2{k\pi\over n+1}\Bigr)\Domh^2\biggr)^{1/4}
\enddisplay
\parindent=30pt % for the Answers
\bugonpage 485, bottom line, and top line of 486 (5 Feb 93)
\noindent
corresponds to transferring the top $m-k$, then using only
three pegs to move the bottom~$k$, then finishing with the top $m-k$.)
The stated relation\cutpar
\bugonpage 490, line 2 from the bottom (5 Feb 93)
\textindent{2.30}%
$\sum_a^b x\,\delta x=\half(b\_2-a\_2)=\half(b-a)(b+a-1)$.
So we have
\bugonpage 491, line 11 from the bottom (5 Feb 93)
\vskip-20pt
\begindisplay
\sum_{k\in K}a_k=\sum_ka_k\[k\in K]\qquad\qquad
\quad\longleftrightarrow\quad
\bigwedge_{k\in K}a_k=\bigwedge_ka_k\cdt\infty^{[k\notin K]}\cr
\enddisplay
\bugonpage 493, line 2 (24 Sep 93)
\noindent
integers satisfying
$a