% CHANGES TO VOLUME 1 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2011, 2012, ..., 2021, 2022 by Donald E. Knuth % This file may be freely copied provided that no modifications are made. % All other rights are reserved. % % Three levels of changes to the books are distinguished here: % % "\bugonpage" introduces the correction of an error; % "\amendpage" introduces new material for future editions; % "\improvepage" introduces ameliorations of lesser importance. % % (Changes introduced by \improvepage do not appear in the hardcopy listing.) % % Also, "\planforpage" introduces some of the author's half-baked intentions. % % NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE % tex "\let\indexeject+ \input err1" \newif\ifall % \alltrue means show the trivial items too \relax % hook \def\vertical{|} \def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname} \catcode`|=\active \let|\inref \input \jobname.ref \catcode`|=12 \input taocpmac % use the format for TAOCP, with modifications below \def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change \def\bugonpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin {\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\amendpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\improvepage#1.#2 #3 (#4) {\ifall \medbreak\ninepoint \line{\kern-6pt{\sl Page #2\enspace #3\/} \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\noindent} \def\planforpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.} \nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent} \let\endchange=\fi \def\nl{\par\noindent} \def\nlh{\par\noindent\hangit} \def\hangit{\hangindent2em} \def\cutpar{{\parfillskip=0pt\par}} \def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy" #3 \ifcase#2\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 \ \ifnum #1<97 \hundred#1\else19#1\fi} \def\hundred{20} % the "century" for dates before '97 \def\ex #1. [#2]{\ninepoint \textindent{\bf#1.}[{\it#2\/}]\kern6pt} \def\EX #1. [#2]{\ninepoint \textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt} \def\foottext#1{\medskip \hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint \smallskip\textindent{#1}} \def\volheadline#1{\line{\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill}} \def\refin#1 {\let|\inref \input #1.ref \let|\crossref} \let\defaultpointsize=\tenpoint %%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{INTRODUCTION} \let\rhead=\lhead \titlepage \volheadline{THE ART OF COMPUTER PROGRAMMING} \bigskip \volheadline{ERRATA TO VOLUME 1 (after 2010)} \bigskip \noindent This document is a transcript of the notes that I have been making in my personal copy of {\sl The Art of Computer Programming}, Volume~1 (third edition, 27th printing), since it was first printed in 2011. Previous errata are recorded in another file `{\tt all1-pre.ps}'. \ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,'' and ``improvements''\dash---appear, indicated by four \else Three levels of updates\dash---``errors,'' ``amendments,'' and ``plans''\dash---appear, indicated by three \fi different typographic conventions: \begingroup\def\hundred{17} \bugonpage 0.666 line 1 (76.07.04) Technical or typographical errors (aka bugs) are the most critical items, so they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page number. The date on which I first was told about the bug is shown; this is the effective date on which I paid the finder's fee. The necessary corrections are indicated in a straightforward way. If,~for example, the book says `$n$' where it should have said `$n+1$', the change is shown thus: \smallskip $n$ \becomes $n+1$ \endchange \amendpage 0.666 line 2 (89.07.14) Amendments to the text appear in the same format as bugs, but without the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known about or thought of when I wrote the original text, so I added them later. The date is the date I drafted the new text. \endchange \def\hundred{19} \planforpage 0.666 line 3 (17.11.20) Plans for the future represent a third kind of item. In such notes I~sketched my intentions about things that I wasn't ready to flesh out further when I~wrote them down. You can identify these items because they're written in slanted type, and preceded by a bunch of dots `\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on which I recorded the plan in my files. \endchange \improvepage 0.666 line 4 (38.01.10) The fourth and final category\dash---indicated by page and line number in smaller, slanted type\dash---consists of minor corrections or improvements that most readers don't want to know about, because they are so trivial. You wouldn't even be seeing these items if you hadn't specifically chosen to print the complete errata list in all its gory details. Are you sure you wanted to do that? \endchange \endgroup \ifall\else\medskip\ninepoint My personal file of updates also includes a fourth category of items, not shown in this list. They are miscellaneous minor corrections or improvements that most readers don't want to know about, because they are so trivial. If you really want to see all of the gory details, you can download the full list from Internet webpage $$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$ by selecting the ``long form'' of the errata. \fi \medskip \tenpoint My shelves at home are bursting with preprints and reprints of significant research results that I want to digest and summarize, where appropriate, in the ultimate edition of Volume~1. I didn't do that in the third edition because I would surely have to do it over again later: New results continue to pour forth at a great rate, and I will have time to rewrite that volume only~once. Volumes 4 and~5 need to be finished first. So I've put most of my effort so far into writing up those parts of the total picture that seem to have converged to their near-final form. It follows, somewhat paradoxically, that the updates in this document are most current in the areas where there has been least activity. On the other hand I do believe that the changes listed here bring Volume~1 completely up to date in two respects: (1)~All of the research problems in the previous edition\dash---i.e., all exercises that were rated 46 and above\dash---have received new ratings of 45 or less whenever I learned of a solution; and in such cases, the answer now refers to that solution. (2)~All of the historical information about pioneering developments has been amended whenever new details have come to my attention. \beginconstruction The ultimate, glorious, 100\% perfect editions of Volumes 1--4A are works in progress. Please let me know of any improvements that you think I ought to make. Send your comments either by snail mail to D.~E. Knuth, Computer Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045, or by email to {\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions only, please\dash---all other correspondence is returned unread to the sender, or discarded, because I have no time to read ordinary email.) Although I'm working full time on Volume~4B these days, I~will try to reply to all such messages within a year of receipt. Current news about {\sl The Art of Computer Programming\/} is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, January 2011} \bigskip \bigskip {\quoteformat What happened? The subject took the bit in its teeth and ran away with it, that's what happened. I know now how Sir James Frazer felt when, after setting out to dash off a brief monograph on a single obscure rite, he found himself in the embarrassing possession of the 12 volumes of ``The Golden Bough.'' \author WAVERLEY ROOT (1974) % International Herald Tribune, 22 May 1974, p8 \bigskip No matter how many times you proofread your book, after publication there will be roughly one typo per page. \author JOSEPH H. SILVERMAN (2017) % "A tale of two books", Bull AMS 54 (2017), 593 \vfill\eject } \def\today{\number\day\space\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\year} %%%%%%%%%%%%%%% CHANGES FOR VOLUME 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO VOLUME 1: FUNDAMENTAL ALGORITHMS} \let\rhead=\lhead \titlepage \volheadline{FUNDAMENTAL ALGORITHMS} \bigskip \rightline{Copyright \copyright\ 2011, 2012, \dots, 2020, 2021, 2022 Addison\with Wesley} \rightline{Last updated \today} \bigskip \rightline{\sl Most of these corrections have already been made in recent printings.} \smallskip \let\defaultpointsize=\tenpoint \bugonpage 1.0 (on the back page of the dustcover, line 23) (12.09.10) {\eightss Whatever your backgound, \becomes Whatever your background,} \endchange \bugonpage 1.v line 8 (18.12.13) \eightssi McCall's Cookbook \becomes McCall's Cook Book \endchange \bugonpage 1.x line 14 (16.03.24) American Mathematical Monthly \becomes The American Mathematical Monthly \endchange \amendpage 1.xi new paragraph to follow line 20 (13.11.25) My efforts to extend and enhance these volumes have been enormously enhanced since 1980 by the wise guidance of Addison--Wesley's editor Peter Gordon. He has become not only my ``publishing partner'' but also a close friend, while continually nudging me to move in fruitful directions. Indeed, my interactions with dozens of Addison--Wesley people during more than three decades have been much better than any author deserves. The tireless support of managing editor John Fuller, whose meticulous attention to detail has maintained the highest standards of production quality in spite of frequent updates, has been particularly praiseworthy. \endchange \improvepage 1.xi line 5 before the author's signature (15.09.23) nobody noticed \becomes nobody else noticed \endchange \amendpage 1.xiv date of the Herbert quotation (19.11.26) {\eightss (1640)} \becomes {\eightss (1651)} \endchange \amendpage 1.xiv replacement for the Vauvenargues quotation (19.12.21) \vskip0pt % this actually helps {\quoteformat Les meilleurs auteurs parlent trop. \author VAUVENARGUES, {\sl Paradoxes, m\^el\'es % de R\'eflexions et Maximes}, 115 (1746) % "the best authors say too much" } \endchange \amendpage 1.xvi line 16 (11.06.16) a {\it 45\/} rating \becomes a {\it 40\/} rating \endchange \amendpage 1.xvi line 20 (13.01.30) creativity.\ \becomes creativity. All exercises with ratings of {\it46\/} or more are open problems for future research, rated according to the number of different attacks that they've resisted so far. \endchange \amendpage 1.1 the Epictetus quote (22.01.16) \vskip-1pt {\quoteformat \author EPICTETUS, {\sl Discourses\/} IV$\?$.$@$i (c.~\AD.~110) \par }\nl [also also move this quote up, above the one by Ada Augusta] \endchange \amendpage 1.2 line $-7$ (19.09.13) also usually appears \becomes often appears also \endchange \improvepage 1.6 lines 1--3 (13.03.13) $\{m,n\}$ \becomes $m$ and $n$ [twice]\nl $\{n,r\}$ \becomes $n$ and $r$ [twice] \endchange \improvepage 1.7 line $-5$ (21.02.22) $Q$ is a set containing subsets $I$ and $\Omega$, \becomes $Q$ is a set, $I$ and $\Omega$ are subsets of~$Q$, \endchange \improvepage 1.8 lines $-5$ and $-4$ (13.03.13) Such a computational method \dots\ it is also \becomes Every step of such a computational method is clearly effective, and experience shows that pattern-matching rules of this kind are also \endchange \improvepage 1.8 line $-11$ (19.07.30) for strings $\alpha$ and $\omega$ \becomes for some strings $\alpha$ and $\omega$ in~$A^*$. \endchange \amendpage 1.9 the rating of exercise 7 (14.04.05) \ninepoint {\it M21\/} \becomes {\it\HM21\/} \endchange \improvepage 1.11 lines 3--4 (15.05.06) An expansion \dots\ can \becomes A more leisurely presentation of much of the following material, together with related concepts, can \endchange \improvepage 1.13 line 3 after {\eq(3)} (21.02.06) $F_2=1<1.6<\phi^1$ \becomes $F_2=1<\phi^1$ \endchange \improvepage 1.15 line $-13$ (19.04.20) consists of proving \becomes constructs a proof \endchange \bugonpage 1.17 line 26 (13.12.15) {\bf11} (1838) \becomes {\bf12} (1838) \endchange \amendpage 1.18 replacement for line 5 of exercise 2 (19.04.19) \ninepoint$$ a^{(n+1)-1}=a^n={a^{n-1}\times a^{n-1}\over b^{n-1}}={1\times 1\over 1}=1, \quad\hbox{where $b=a^{(n-2)/(n-1)}@$;} $$ \endchange \improvepage 1.18 clarification in exercise 4 (13.02.10) \ninepoint $\phi^{n-2}$. \becomes $\phi^{n-2}$ for all positive integers $n$. \endchange \improvepage 1.19 clarification in exercise 5 line 1 (13.02.05) exact divisors \becomes positive integer divisors \endchange \improvepage 1.19 additional clarification, exercise 5 line 3 (19.09.20) one or more prime numbers. \becomes one or more prime numbers, namely in the form $n=p_1\ldots p_k$ for some $k\ge1$, where each of $p_1$, \dots,~$p_k$ is prime. \endchange \amendpage 1.19 in exercise 9 (19.09.13) $1-na$ \becomes $1-na$ for all integers $n$ \endchange \improvepage 1.22 lines 1 and 3 after {\eq(8)} (13.01.20) $10^x$ \becomes $b^x$ \qquad[two places] \endchange \amendpage 1.22 line 3 after {\eq(8)} (19.09.17) is 1.999\dots\ \becomes begins with 1.999\dots \endchange \amendpage 1.23 line 1 after {\eq(13)} (15.02.22) Edward M. Reingold. \becomes Ernesto Trucco [{\sl Bull.\ Math.\ Biophysics\/ \bf18} (1956), 130]. \endchange \improvepage 1.25 lines 1 and 2 of exercise 11 (19.11.22) \ninepoint and $x\approx\log_{10}2$, to how \dots~value of $x$ in order to determine \becomes and $x$ is approximately equal to $\log_{10}2$, how many decimal places of $x$'s value will guarantee that we can determine \endchange \improvepage 1.25 in exercise 18 (19.11.22) $\half\lg x$ \becomes $\half\lg x$, for all real $x>0$. \endchange \bugonpage 1.27 line 1 (11.07.22) \ninepoint $n>1$ \becomes $n>1$ and $n\ne e$. \endchange % actually I've also changed $n$ to $x$ in this exercise \amendpage 1.29 replacement for five lines after {\eq(9)} (19.12.22) \noindent where $S'(j)$ specifies summing over all $j$ such that ``there is an integer $i$ such that both $R(i)$ and $S(i,j)$ are true''; and $R^{@\prime}(i,j)$ specifies summing over all~$i$ such that ``both $R(i)$ and $S(i,j)$ are true.'' For example, if the summation is $\sum_{i=1}^n \sum_{j=1}^i a_{ij}$, then $S'(j)$ sums over $j$ where ``there is an integer $i$ such that $1\le i\le n$ and $1\le j\le i$,'' that is, $1\le j\le n$; and $R^{@\prime}(i,j)$ sums over~$i$ where ``$1\le i\le n$ and $1\le j\le i$,'' that is, $j\le i\le n$. Thus, \endchange \improvepage 1.30 last line of Example 1 (19.04.20) consists of simplifying \becomes simplifies \endchange \amendpage 1.35 replacement for line 2 of exercise 18 (19.12.22) \ninepoint\noindent $R(i)$ specifies summing over all~$i$ such that ``$n$ is a multiple of $i$'' and $S(i,j)$ specifies summing over all~$j$ such that ``$1\le j1$.] \endchange \amendpage 1.53 line $-3$ thru line 1 of the text on page 54 (21.04.19) The earliest known \dots\ Another \becomes\nl Long before that (c.~700), in India, Virah\"a\:nka had explained two ways to compute them in his {\sl V\d{r}ttaj\=atisamuccaya\/} (``Manual of prosody''), slokas 6.7--6.11; we'll see those two ways below in Eqs.~\eq(9)~and~\eq(11). Virah\"a\:nka was inspired by an ancient Hindu classic, Pi\:ngala's {\sl Chanda\d{h}\'s\=astra}. The earliest known detailed discussion of binomial coefficients is in Hal\=ayudha's tenth-century commentary on Pi\:ngala's work; see G. Chakra\-varti, {\sl Bull.\ Calcutta Math.\ Soc.\ \bf24} (1932), 79--88. Another \endchange \amendpage 1.55 replacement for displayed equation {\eq(5)} (21.10.04) $$\Bigl({r\atop k}\Bigr)= {r!\over k!\,(r-k)!},\quad r\ge \hbox{integer }k\ge 0. \eqno(5)$$ \endchange \amendpage 1.56 in {\eq(10)} (21.10.04) $n\ge0$. \becomes $n$. \endchange \amendpage 1.56 line $-8$ (21.10.04) with two applications of Eq.~\eq(6) \becomes and Eq.~\eq(6) \endchange \bugonpage 1.60 lines $-3$, $-7$, and $-11$ (21.10.04) $\displaystyle \sum_k$ \becomes $\displaystyle \sum_{k\ge0}$ \endchange \bugonpage 1.61 lines 11, 15, and 16 (21.10.04) $\displaystyle \sum_k$ \becomes $\displaystyle \sum_{k\ge0}$ \endchange \amendpage 1.61 replacement for the bottom 7 lines (16.11.16) \noindent to use Eq.~\eq(20)\dash---which no longer applies. In this situation it pays to complicate things even {\it more}, by replacing the unwanted $n+k\choose m+2k$ %$$\Bigl({n+k\atop m+2k}\Bigr)$$ by a sum of terms of the form \smash{$x+k\choose2k$}, %$$\Bigl({x+k\atop 2k}\Bigr),$$ since our problem will then become a sum of problems that we know how to solve. Accordingly, we use Eq.~\eq(25) with $$k\mapsto j,\quad r\mapsto n-1,\quad m\mapsto m-1,\quad s\mapsto k,\quad n\mapsto 2k;$$ all of the conditions required for \eq(25) are satisfied, because $m$ and $n$ are positive. \endchange \amendpage 1.62 replacement for the top 18 lines (21.10.04) % was (16.11.16) The sum to be solved now takes the form $$\sum_{k\ge0}\,\sum_{j=0}^{n-1}\Bigl({n-1-j\atop m-1}\Bigr) \Bigl({k+j\atop2k}\Bigr)\Bigl({2k\atop k}\Bigr){(-1)^k\over k+1};\eqno(29)$$ and the rest is easy, by interchanging the order of summation: Equation~\eq(28) tells us how to sum on~$k$, and all the complications melt away. Everything reduces to just $$\sum_{j=0}^{n-1}\Bigl({n-1-j\atop m-1}\Bigr)\,\delta_{j0},$$ so our final answer is $$\Bigl({n-1\atop m-1}\Bigr).$$ The solution to this problem was fairly complicated, but not really mysterious; there was a good reason for each step. The derivation should be studied closely, because the use of \eq(25) illustrates some delicate maneuvering with the conditions in our equations. There is actually a better way to attack this problem, however! The reader is invited to figure out how to transform the given sum so that Eq.~\eq(26) applies (see exercise 30). \endchange \amendpage 1.63 insert a remark on line 4 (21.10.04) assuming, as we may, that $nt\ne r+s$. \bugonpage 1.63 lines $-1$, $-2$, $-3$, and $-10$ (21.10.04) $\displaystyle \sum_k$ \becomes $\displaystyle \sum_{k\ge0}$\nl [and also insert `when $m\ge0$' on line $-1$] \endchange \amendpage 1.65 in {\eq(40)} (21.10.04) insert `integer $k\ge0$,' \endchange \bugonpage 1.65 second line after {\eq(40)} (21.10.04) each term \becomes each factor \endchange \amendpage 1.69 line 1 of exercise 10 (21.10.04) \ninepoint $p$ is prime \becomes $p$ is prime and $n$ is an integer \endchange \improvepage 1.70 in exercise 25 (13.10.07) \ninepoint line 1: as in Eq.~\eq(30). \becomes as in Example~4 (see Eq.~\eq(30)).\nl line 5: the identity \becomes multiples of a special case of \eq(34), \endchange \bugonpage 1.70 line 2 of exercise 25 (13.10.07) \ninepoint provided $z$ is small enough \becomes provided that $x$ is close enough to 1 \endchange \amendpage 1.74 line 3 of exercise 67 (21.10.04) \ninepoint $n\ge k\ge0$ \becomes $n\ge k>0$ \endchange \amendpage 1.79 new exercise for Section 1.2.7 (13.02.11) \ninepoint \ex25. [M21] Let $H_n^{(u,v)}=\sum_{1\le j\le k\le n}1/(j^uk^v)$. What are $H_n^{(0,v)}$ and $H_n^{(u,0)}$? Prove the general identity $H_n^{(u,v)}+H_n^{(v,u)}=H_n^{(u)}H_n^{(v)}+H_n^{(u+v)}$. \endchange \bugonpage 1.79 line 3 after {\eq(2)} (21.01.24) (Book of the Abacus) \becomes (Book of Calculation) \endchange \amendpage 1.80, line 6 (21.04.19) therefore \becomes and the rule for computing those numbers was stated by Virah\"a\:nka (c.~700) in his work {\sl V\d{r}ttaj\=atisamuccaya\/}, sloka 6.49. \endchange \amendpage 1.83, replacement for line $-3$ (21.02.06) $$F_n=\phi^n\!/\sqrt{5}\hbox{ {\sl rounded to the nearest integer},\quad for all integers $n\ge0$.}\eqno(15)$$ \endchange \amendpage 1.85 the displayed formula in exercise 24 (17.01.20) insert `{\ninepoint det}' before the matrix \endchange \amendpage 1.91 replacement for {\eq(29)} (21.03.21) $${z\over 1-e^{-z}}=1+\half z+{1\over12}z^2+\cdots =\sum_{k\ge0}{B_kz^k\over k!}.\eqno(29)$$ \endchange \bugonpage 1.100 line $-5$ (20.07.24) Roes {\sl CACM\/} \becomes Roes, {\sl CACM\/} \endchange \improvepage 1.104 line 11 (14.06.26) random variable \becomes random integer \endchange \amendpage 1.104 new sentence preceding the exercises (12.07.19) \noindent[S.~Bernstein had contributed key ideas in {\sl Uchenye zapiski Nauchno-\nl\quad Issledovatel'skikh kafedr Ukrainy\/ \bf1} (1924), 38--48.] \endchange \amendpage 1.108 replacement for bottom line (22.01.20) $$O\bigl( f(n)@g(n)\bigr)=f(n)@O(\bigl(g(n)\bigr),\quad \hbox{if $f(n)$ is never zero.}\eqno(10)$$ \endchange % my letter to Lafratta in 2021 was wrong \amendpage 1.110 lines 14--16 (14.07.01) We have \dots\ This equation \becomes We have $$\root n\of{n}= e^{\ln n/n}=1+(\ln n/n)+O\bigl((\log n/n)^2\bigr),\eqno(18)$$ because $\log n/n\to0$ as $n\to\infty$; see exercises 8 and~11. (Notice that we needn't specify the base of `log' inside $O$-notation, where constants are ignored.) This equation \endchange %\amendpage 1.111 line above Fig.~12 (12.07.08) %{\sl Petropoli\-tan\ae\/} \becomes {\sl Imperialis Petropoli\-tan\ae\/} %\endchange \amendpage 1.111 replacement for Fig.~12 and the lines just above and below (21.03.21) \noindent {\sl Imperialis Petropoli\-tan\ae\/ \bf 6} (1732), 68--69; {\bf8} (1735), 9--22.] \bigskip%\midinsert \ref12|Fig-1.2.11.2-12| $$\epsfbox{\figdir/ch1.12}$$ \centerline{\caption Fig.\ 12. Comparing a sum with an integral.} \bigskip%\endinsert Figure |Fig-1.2.11.2-12| shows a comparison of $\int_1^n f(x)\,dx$ and $\sum_{k=1}^nf(k)$, when $n=\nobreak7$.\break \endchange \amendpage 1.112 replacement for {\eq(3)} (21.03.21) $$\sum_{1\le k\le n}f(k)=\int_1^nf(x)\,dx+{\textstyle\half }\bigl( f(n) +f(1)\bigr) +\int_1^nB_1(\{x\})f'(x)\,dx,\eqno(3)$$ \endchange \amendpage 1.112 replacement for {\eq(4)} and the line above (21.03.21) \noindent are the coefficients in the following infinite series:* $${z\over1-e^{-z}}=B_0+B_1z+{B_2z^2\over 2!}+\cdots =\sum_{k\ge 0}{B_kz^k\over k!}. \eqno(4)$$ \endchange \amendpage 1.112 in {\eq(5)} (21.03.21) $B_1=-\half$ \becomes $B_1=\half$ \endchange \amendpage 1.112 replacement for line $-3$ (21.03.21) $${z\over 1-e^{-z}}-{z\over 2}={z\over 2}\;{1+e^{-z}\over1-e^{-z}}= -{z\over 2}\;{1+e^z\over1-e^z}$$ \endchange \amendpage 1.112 append a footnote (21.03.21) \smallskip\hrule width3pc \medskip \eightpoint\textindent{*}\em Warning: Many books, including earlier printings of {\sl The Art of Computer Programming}, have used the formula $z/(e^z-1)$ instead of $z/(1-e^{-z})$ to define the Bernoulli numbers, thereby making $B_1=\smash{-\half}$. But Peter Luschny published an online ``Bernoulli Manifesto'' in 2013, with compelling arguments that $B_1$ should be $+\half$, as in the original works of Seki and Bernoulli. \endchange \amendpage 1.113 replacement for lines 1--12 (21.03.21) If we multiply both sides of the defining equation \eq(4) by $1-e^{-z}$, and equate coefficients of equal powers of $z$, we obtain the formula $$\sum_k\Bigl({n\atop k}\Bigr)(-1)^{n-k}B_k=B_n-\delta_{n1}.\eqno(7)$$ (See exercise 1.) We now define the {\it Bernoulli polynomial} $$B_m(x)=\sum_kB_k\Bigl({m\atop k}\Bigr)(x-1)^{m-k} =\sum_k\Bigl({m\atop k}\Bigr)(-1)^kB_kx^{m-k}.\eqno(8)$$ If $m=1$, then $B_1(x)=B_0x-B_1=x-\half $, corresponding to the polynomial used~above in Eq.~\eq(3). If $m>1$, we have $B_m(1)=B_m=B_m(0)$, by \eq(6) and \eq(7); in other words, $B_m(\{x\})$ has no discontinuities at integer points $x$. The relevance of Bernoulli polynomials and Bernoulli numbers to our problem will soon be clear. We find by differentiating Eq.~\eq(8) that $$\eqalignno{B_m'(x)&=\sum_k\Bigl({m\atop k}\Bigr)(m-k)(-1)^kB_kx^{m-k-1}\cr &=m\sum_k\Bigl({m-1\atop k}\Bigr)(-1)^kB_kx^{m-1-k}\cr}$$ \endchange \amendpage 1.113 replacement for {\eq(10)} (21.03.21) $$\interdisplaylinepenalty=10000 \eqalignno{\sum_{k=1}^n f(k)&=\int_1^n\!\!\!f(x)\,dx+f(1)+ {B_1\over1!}\bigl( f(n)-f(1)\bigr) +{B_2\over 2!}\bigl( f'(n) -f'(1)\bigr) +\cdots\cr \noalign{\vskip-6pt} &\hskip11em\null+{B_m\over m!}\bigl( f^{(m-1)}(n)-f^{(m-1)}(1)\bigr) +R_{mn}\cr \noalign{\vskip3pt} &=\int_1^n\!\!\!f(x)\,dx+f(1)+\sum_{k=1}^m {B_k\over k!}\bigl( f^{(k-1)}(n) -f^{(k-1)}(1)\bigr) +R_{mn},&\eq(10)\cr}$$ \endchange \amendpage 1.114 line 7 (13.02.26) is less than \becomes is less in absolute value than \endchange \amendpage 1.114 replacement for {\eq(14)} (21.03.21) $$H_n=\ln n+1+\sum_{k=1}^m {B_k\over k}(-1)^{k-1}\Bigl({1\over n^k} -1\Bigr) +R_{mn}.\eqno(14)$$ \endchange \amendpage 1.114 replacement for {\eq(15)} (21.03.21) $$\gamma =\lim_{n\to \infty }(H_n-\ln n)=1+\sum_{k=1}^m {B_k\over k}(-1)^k +\lim_{n\to \infty }R_{mn}.\eqno(15)$$ \endchange \amendpage 1.114 lower half of page (21.03.21) lines $-10$ and $-7$: $H_{n-1}$ \becomes $H_n$\nl line $-5$: (adding $1/n$ to both sides) \becomes \endchange \amendpage 1.115 replacement for {\eq(17)} (21.03.21) $$\ln n!=n\ln n-n+1+{\textstyle\half }\ln n+\sum_{1l$, because that could happen only if $(n+d_1/10+\cdots+d_l/10^l+1/10^l)^m\le u$. \endchange \amendpage 1.469 line 1 of answer 9 (21.04.01) $=b^{pu}\!@$, hence \becomes $=b^{pu}\!@$, using \eq(6) twice. Hence \endchange \amendpage 1.470 line 2 of answer 11 (19.09.17) $10^x=1.99999\ldots$ \becomes $10^x$ begins with $1.99999\ldots$ \endchange \improvepage 1.470 in step E1 of answer 28 (11.10.28) If $1-\epsilon$ \dots $k\gets1$. \becomes Set $x\gets1-\epsilon-x$, $y\gets y_0$, and $k\gets1$, where $1-\epsilon$ is the largest possible value of~$x$, and $y_0$ is the nearest approximation to $b^{1-\epsilon}$. \endchange \amendpage 1.471 new answer 18 (19.12.22) \ans18. $S'(j)$ sums over $j$ with ``$1\le jj$''. \endchange \amendpage 1.472 replacement for last line of answer 26 (20.06.12) The answer is $P_1=(P_1P_2)^{1/2}=\bigl(\prod_{i=0}^n a_i\bigr){}^{n+2}$, because $P_1=\bigl(\prod_{i=0}^n \prod_{j=i}^n a_ia_j\bigr)=P_2$. \endchange \amendpage 1.472 new copy for end of answer 31 (11.10.20) Consequently we have $\bigl(\sum_{j=1}^n u_j\bigr)\bigl(\sum_{j=1}^n v_j\bigr) \le n\sum_{j=1}^n u_jv_j$ when $u_1\le u_2\le\cdots\le u_n$ and $v_1\le v_2\le\cdots\le v_n$, a result known as {\it Chebyshev}'s monotonic inequality. [See {\sl Soobshch.\ mat.\ obshch.\ Khar'kovskom Univ.\ \bf4},\thinspace2 (1882), 93--98.] \endchange \amendpage 1.474 lines 3--5 of answer 43 (11.11.26) as in exercise 44 \dots\ $(x_i-1)\bigr)$. \becomes by setting $x=1$ in exercise~40 and obtaining ${\prod_{k\ne i}(x_k-1)/x_i\prod_{k\ne i}(x_k-x_i)}$. After multiplying numerator and denominator by $x_i-1$, we can sum on $i$ by applying exercise~33 with $r=0$ to the $n+2$ numbers $\{0,1,x_1,\ldots,x_n\}$. \endchange \amendpage 1.476 replacement for answer 4 (13.12.22) \ans4. By part (f), $x\le\lceil x\rceil0$. The $k$th term is $r/(r-tk)$ times $$\displaylines{\quad{1\over n!}\Bigl({n\atop k}\Bigr) \prod_{0\le j1$, \becomes $f(0,m)=\delta_{0m}$. If $n>0$, \endchange \improvepage 1.491 line 2 of answer 66 (15.04.17) $y>n-1$ \becomes $y\ge n-1$ \endchange \amendpage 1.491 replacement for last line of answer 67 (12.02.18) ${n\choose k}\ge\bigl({(n-k+1)e\over k} \bigr){}^k{1\over ek}$, which is less memorable (but often sharper) than ${n\choose k}\ge\bigl({n\over k}\bigr){}^k$. \endchange \amendpage 1.492 replacement for answer 16 (16.06.21) \ans16. $H_{2n}-\half H_n$. \endchange \amendpage 1.493 new answer for section 1.2.7 (13.02.11) \ans25. $H_n^{(0,v)}=\sum_{k=1}^nH_n^{(v)}$ and $H_n^{(u,0)}=H_n^{(u-1)}$; so the identity generalizes~\eq(8). [See L.~Euler, {\sl Novi Comment.\ Acad.\ Sci.\ Pet.\ \bf 20} (1775), 140--186, \S2.] \endchange \amendpage 1.495 last line of answer 34 (18.07.10) Generalizations \dots 7.1.3. \becomes For generalizations, see exercise 4.5.3--52, exercise 5.4.2--10, and Section 7.1.3. \endchange \bugonpage 1.498 line $-2$ of answer 21 (21.05.09) {\sl Series\/} (Dover, 1956) \becomes {\sl Series}, second edition (Blackie, 1951) \endchange \bugonpage 1.499 last line of answer 23 (21.05.09) {\bf27} (1965) \becomes {\bf17} (1965) \endchange \improvepage 1.500 line $-2$ of answer 6 (21.03.21) $H'(t)=e^t/(e^t-1)-1/t$ \becomes $H'(t)=1/(1-e^{-t})-1/t$ \endchange \amendpage 1.503 replacement for answer 1 (21.03.21) \ans1. $(B_0+B_1z+B_2z^2\!/2!+\cdots{})@e^{-z}\!=\!(B_0+B_1z+B_2z^2\!/2!+\cdots{}) -z$; use Eq.~1.2.9--\eq(11). \endchange \bugonpage 1.503 last line of answer 3 (13.03.05) 1937 \becomes 1927 \endchange \amendpage 1.503 replacement for answer 4 (21.03.21) \ans4. $\displaystyle S_m(n)={n^{m+1}\over 1+m}+0^m+\sum_{k=1}^m {B_k\over k!}m\falling{k-1}n^{m-k+1} ={B_{m+1}(n+1)-B_{m+1}\over m+1}+0^m$. \endchange \amendpage 1.504 top half of page (21.03.21) line 2: $\ln\,(n-1)!=(n-\half)\ln n$ \becomes $\ln n!=(n+\half)\ln n$\nl line 3: Now $\ln\Gamma_{n-1}(c)=c\ln (n-1)+\ln\,(n-1)!-\ln\bigl( c\ldots (c+n-1)\bigr)$; \becomes Now let $\Gamma_m(x)=m^xm!/x\rising{m+1}$, so that $\ln \Gamma_n(c)=c\ln n+\ln n!-\ln\bigl(c(c+1)\ldots(c+n)\bigr)$;\nl line 2 of answer 7: $\sum_{k=1}^{n-1}$ \becomes $\sum_{k=1}^n$ \endchange \improvepage 1.504 last line of answer 8 (12.02.18) ${cn^2\choose n}\big/c^n{n^2\choose n}$ \becomes ${cn^2\choose n}\big/\bigl(c^n{n^2\choose n}\bigr)$ \endchange \amendpage 1.509 new answer 23 (18.02.28) \ans23. First, by R. D. Dixon:\hskip5em Second, by George Wahid, if $\rA\ge0$: \smallskip \line{\vtop{\mixthree (3000)&ENT1&4\cr (3001)&LDA&200\cr &SRA&0,1\cr &SRAX&1\cr\endmix}\hfil\vtop{\mixthree &DEC1&1\cr &J1NN&3001\cr &SLAX&5\cr &HLT&0\quad\slug$_{\phantom j}$\cr\endmix} \hfil\hfil\hfil\vtop{\mixthree (3000)&ENT1&5:5\cr (3001)&SLA&1\cr &ST1&3003(4:4)\cr (3003)&ADD&200(*)\cr\endmix}\hfil\vtop{\mixthree &DEC1&1:1\cr &J1P &3001\cr &HLT&0\quad\slug\cr\endmix}} \endchange \improvepage 1.514 replacement for line 5 of the program (13.04.30) \nobreak\vskip-12pt\ansmixthree 3H \ \ \ &ENT2&9*8-8,1&Start at row 9.\cr \endmix \endchange \bugonpage 1.514 replacement for lines 19 and 20 of the program (13.03.10) \nobreak\vskip-12pt\ansmixthree PHASE2&ENT3&9*8 \ \ \ &At this point $\rA =\min_jC(j)$\cr 3H&ENT2&0,3&Prepare to search a row.\cr \endmix \endchange \amendpage 1.518 line 14 (14.08.27) Victorius of Aquitania \becomes Victorius of Aquitaine \endchange \amendpage 1.540 lines 2--6 of answer 14 (21.07.07) When $R$ is empty \dots\ leaving the queue. \becomes To insert at the rear, push onto~$S$. To delete from the front, pop the top of~$R$\dash---except that if $R$ is empty, first pop the elements of~$S$ onto~$R$ until $S$ becomes empty. Each element is first pushed onto~$S$, then popped from~$S$ and pushed to~$R$, then popped from~$R$ when leaving the queue. (But if $R$ and $S$ are both empty, one might prefer to push directly onto~$R$.) \endchange \bugonpage 1.545 line 8 of answer 3 (19.04.23) $\rA \gets\.{INFO($\rI1$)}$ \becomes $\rA \gets\.{INFO($\rI3$)}$ \endchange \amendpage 1.546 last lines of answer 9 (14.06.30) plagues many automatic programming systems.) \becomes plagued many automatic programming systems in the old days.) \endchange \amendpage 1.547 new answer 13 (18.03.15) \ans13. Sha and Kleitman [{\sl Discrete Math.\ \bf63} (1987), 271--278] \vadjust{\vskip-1pt}% proved that the number is at most $\prod_{k=0}^n{n\choose k}\losup{n\choose k}$; \vadjust{\vskip1pt}% Brightwell and~Tetali [{\sl Order\/ \bf20} (2003), 333--345] improved this upper bound to $\exp\bigl((2en2^n\!/r)^r\prod_{k=0}^n{n\choose k}!\bigr)$, where $r=(2^{n+1}-2)/(n+1)$. The obvious lower bound is $\prod_{k=0}^n{n\choose k}!= 2^{2^n(n+O(\log n))}$. For the initial values $\langle a_n\rangle= \langle1,1,2,48,1680384,\ldots{}\rangle$, up to $a_7\approx6.305\times10^{137}$, see OEIS sequence A046873. \endchange \amendpage 1.551 replacement for answer 30 (21.08.17) \ans30. To insert, set $\.P\Leftarrow\.{AVAIL}$, $\.{INFO(R)}\gets\.Y$, $\.{LINK(R)}\gets\.P$, $\.R\gets\.P$, $\.{LINK(P)}\gets\Lambda$. (We need not set \.{LINK(P)}; but that lack of discipline might confuse a garbage collection algorithm, as in exercise~6.) To delete, \.{UNDERFLOW} if $\.F=\.R$; otherwise set $\.P\gets\.F$, $\.F\gets\.{LINK(P)}$, $\.Y\gets\.{INFO(P)}$, $\.{AVAIL} \Leftarrow \.P$. \endchange \amendpage 1.551 replacement for answer 4 (21.08.17) \ans4. The text's operation (a) is unchanged; so is operation (c), but it's now preceded by ``if $\.{LINK(PTR)}=\.{PTR}$, then \.{UNDERFLOW}.'' Operation~(b) becomes ``$\.{INFO(PTR)}\gets\.Y$, $\.P\Leftarrow\.{AVAIL}$, $\.{LINK(P)}\gets\.{LINK(PTR)}$, $\.{LINK(PTR)}\gets\.P$, $\.{PTR}\gets\.P$.'' \endchange \bugonpage 1.552 in answer 12 (12.06.30) line 1: $29p$ \becomes $27p$\nl line 3: $3\over4$ \becomes 78\% \endchange \amendpage 1.570 new sentence to follow line 1 of answer 30 (13.10.08) Thus $\.{LOC(T)}=\.{HEAD}$, and $\.{HEAD}\symord/$ is the first node of the binary tree in symmetric order. \endchange \improvepage 1.570 line $-3$ of answer 30 (13.10.08) the algorithm of exercise 21 \becomes Algorithm~U in answer 21 \endchange \amendpage 1.576 last line of answer 10 (21.11.11) Section 7.4.1 \becomes Section 7.4.1.1 \endchange \amendpage 1.576 new answer(s) (14.09.09) \anss 14, 15. See Martin Ward and Hussain~Zedan, ``Provably correct derivation of algorithms using FermaT,'' {\sl Formal Aspects of Computing\/ \bf26} (2014), 993--1031. \endchange \amendpage 1.578 last line of answer 6 (21.11.11) Section 7.4.1 \becomes Section 7.4.1.2 \endchange \amendpage 1.579 line $-8$ of answer 8 (21.07.18) flows. We \becomes flows. (The unit flow in $e_0$ needn't be measured.) We \endchange \amendpage 1.587 replacement for top eight lines (17.08.12) \noindent types ($\alpha@a$, $\delta Na$, $\alpha@d$, $\delta Na$, $\alpha@a$, $\delta Nd$, $\alpha@d$) on the main diagonal have the form $$ \vbox{\offinterlineskip \def\bit{height 3pt&\omit&&&&&&&&&\cr} \def\midbit{height 3pt&\omit&&&\omit&&\omit&&&&\cr} \def\ctr#1{\hbox to 4em{\hfil #1\hfil }} \halign{ \vrule #&\vrule height 9pt depth 5pt width 0pt \ctr{$#$}&\ctr{$#$}&\ctr{$#$}&\vrule #&\ctr{$#$}&\vrule # &\ctr{$#$}&\ctr{$#$}&\ctr{$#$}&\vrule #\tabskip0pt\cr \noalign{\hrule} \bit &\alpha@a&\beta K\?Q&\alpha@b&&\beta@QP&&\alpha@a&\beta K&\alpha@b&\cr &\gamma J\?P&\delta Na&\gamma R&&\delta@K\?Q&&\gamma J\?L&\delta Nb&\gamma P&\cr &\alpha@c&\beta DS&\alpha@d&&\beta@Y\?\?QT&&\alpha@c&\beta S&\alpha@d&\cr &\multispan3\hrulefill&&&&\multispan3\hrulefill\cr \midbit &\gamma PQ&\delta J\?P&\gamma X\?P&\omit&\delta Na&\omit&\gamma RQ&\delta R&\gamma R&\cr \midbit &\multispan3\hrulefill&&&&\multispan3\hrulefill\cr \bit &\alpha@a&\beta KU&\alpha@b&&\beta DP&&\alpha@a&\beta K&\alpha@b&\cr &\gamma@JT&\delta Nc&\gamma S&&\delta SD&&\gamma JS &\delta Nd&\gamma@T&\cr &\alpha@c&\beta@QS&\alpha@d&&\beta DT&&\alpha@c&\beta S&\alpha@d&\cr \bit \noalign{\hrule}\cr}} $$ \endchange \amendpage 1.587 line 12 (19.06.22) For a similar \becomes (Six of the 92 types can actually be omitted; see exercise 7.2.2.1--121.) For a similar \endchange \amendpage 1.588 line 3 of answer 4 (20.01.05) at $z=\alpha$. \becomes at $z=\alpha$. (See exercise 7.2.2.2--348.) \endchange \amendpage 1.589 last line of answer 6 (18.02.25) 140.] \becomes 140. Incidentally, there are $g_{n-1}$ oriented trees with $n$ {\it leaves\/} and in-degree~2 at nonleaves.] \endchange \amendpage 1.589 in answer 7 (20.01.05) $a\approx2.483253536173$. \becomes and $a\approx2.483253536173$ satisfies $F(1/a)=0$. o\endchange \amendpage 1.598 last line of answer 3 (17.12.28) two. \becomes two. See exercises 7.2.1.6--26 through 7.2.1.6--34. \endchange \bugonpage 1.607 lines 1--9 (16.06.24) [In some printings, the ``primes'' disappeared from step names; for example, step C5$^\prime$ was simply called step C5.] \endchange \let\defaultpointsize=\tenpoint % begin appendices \bugonpage 1.611 line 5 (14.07.25) inner loop A3* \becomes inner loop A2.5* \endchange \bugonpage 1.613 last line of answer 28 (14.04.14) $\.{AVAIL[$k$]}\gets \.L$. \becomes $\.{AVAILF[$k$]}\gets \.L$. \endchange \improvepage 1.614 line $-2$ of answer 33 (17.12.28) Cohen and Nicolau \becomes J. Cohen and A. Nicolau \endchange \amendpage 1.621 in Table 3 {(the value of $B_1$)} (21.03.21) $-1/2$ \becomes 1/2 \endchange \amendpage 1.624 through page 626 (12.04.07) [replace the notation $(R\Relbar\joinrel\joinrel\joinrel\Rightarrow x;\;y)$ by $(R{?}\ x{:}\ y)$ in eleven places] \endchange \amendpage 4a.626 Bernoulli number entry (21.03.21) $(e^z-1)$ \becomes $(1-e^{-z})$ \endchange \amendpage 1.628 new entries for Appendix C (11.04.17) \ninepoint\noindent Program 1.2.10M, 145, 186.\nl Program 1.4.3.1M, 204--211, 530.\nl Program 2.1A, 236.\nl Program 2.1B, 535.\nl Program 2.3.1S, 325. \endchange \bugonpage 1.629 in Appendix C (11.04.17) \ninepoint\noindent Algorithm 2.4B$'$, 606. \becomes Algorithm 2.4B$'$, 605. Algorithm 2.4B$''$, 606.\nl Algorithm 2.5G, 613. \becomes Algorithm 2.5G, 613--614. \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 1.630 and following (11.01.01) Miscellaneous changes to the existing index of Volume~1 are collected here, including corrections and amendments to the old entries as well as new entries that are occasioned by the new material. Thus, the lines of the full index that have changed serve also as an index to the present document. However, when a correction or amendment has caused an old index entry to be deleted, the deletion is usually not indicated. \input exotic \begindoublecolumns \indexformat \gdef\Uni1.08:{\bitmap24:1.08:} \hangindent 2em $\iff$: If and only if. % 47th $\pi$ (circle ratio), as ``random'' example, 45, 397, 591. % 47th Bendix G20 computer, 124. % 46th Bernoulli, Jacques, numbers $B_n$, 76, 91, 112--115, 500. % 46th Bernstein, Sergei Natanovich ({\rus Bernshtei0n, Sergei0 Natanovich}), 104. %30th Brightwell, Graham Richard, 547. % 39th Burroughs B220 computer, 124. % 46th Burroughs B5000 computer, 461. % 46th Carroll, Lewis (= Dodgson, Charles Lutwidge), 465. % 32nd Chakravarti, Gurugovinda ({\bg\C224\C165\C101\C103\C059\C105\C098\C078\C100\ \C099\C137\C098\C191\C073\lower.08ex\hbox{\kern.05em\C082\kern.13em}}), 54. % 46th Chebyshev (= Tschebyscheff), Pafnutii Lvovich ({\rus Chebyshevp2, Pafnut{\char12}i0 Lp1vovichp2} = {\rus Chebyshev, Pafnutii0 Lp1vovich}), inequalities, 98, 104, 472. % 31st Chia, Hsien (\JC48:48:0:40% J7643 <00000000001800000000003cfffffffffffe7fffffffffff0000f00f00000000f00f0000% 0c00f00f00600e00f00f00f00ffffffffff80ffffffffffc0f00f00f00f80f00f00f00f0% 0f00f00f00f00f00f00f00f00ffffffffff00ffffffffff00f00000000f0060000000060% 00000000000000000000000000ffffffff0000ffffffff0000f000000f0000f000000f00% 00f000000f0000f000000f0000ffffffff0000ffffffff0000f000000f0000f000000f00% 00f000000f0000f000000f0000ffffffff0000ffffffff0000f000000f0000f000000f00% 00f000000f0000f000000f0000ffffffff0000ffffffff00000000000000000000000000% 00060003c000000f0000fc00003f00003f8000fe00000fe007f8000003f03fc0000001e0% >%% Unicode char "8cc8 \JC48:48:0:40% J2391 <000003000000040003c000000c0003e0000c0c0003c0001e1fffffffffff1fffffffffff% 3c000300001e7c0003c0001c7c0003e00c3cf80003c01e38f8ffffffff30707fffffff20% 000003c00000000003c01800000003c03c00007ffffffe00003ffffffe00000003c00000% 000003c0000c000003c0001effffffffffff7fffffffffff000000000000030000000180% 03c0000003c003ffffffffe003ffffffffe003c0780f03c003c0780f03c003c0780f03c0% 03c0780f03c003c0780f03c003ffffffffc003ffffffffc003c0000003c0018307c00180% 0003c1f000000043e0f803f00043e0fc00fc00c3c07c107e01c3c07c103e03c3c038183f% 07c3c000381f1f83e0007c0e3f83fffffc003f03fffffc003e01fffff8001c00fffff000% >%% Unicode char "61b2 ), 53. %42nd Choice, axiom of, 469. % 42nd Comfort, Webb Tyler, 461. % 34th Contour integration, 49, 92. % 37th Deletion of a node: Removing it from a data structure and possibly returning it to available storage. \sub from queue, 242, 244--245, 254, 261, 265, 273--274, 278. % 47th Depth of node in a tree, \see Level. % 30th Diagrams of structural information, tree structures, 309--315, 337, 346, 349, 460, 465. % 32nd Digamma function, \see Psi function $\psi(z)$. % 49th Digitek Corporation, 457. % 44th Dodgson, Charles Lutwidge, \see Carroll. % 32nd Doolittle, Myrick Hascall, 303. % 29th $e$ (base of natural logarithms), 23, 619--620, 626. % 30th Empty list, 244--245, 247, 258, 260--261, 273--275, 278, 280, 540, 546. % 30th Euler, Leonhard ({\rus Ei0lerp2, Leonardp2} = {\rus E1i0ler, Leonard}), 49, 50, 52, 57, 75, 76, 87, 111, 374, 407, 472, 493, 496, 536, 600. % 31st \sub totient function $\varphi(n)$, 42--43, 526. % 46th Family trees, 310--311, 317, 406, 465. % 32nd Fletcher, William Thomas, 527. % 39th Floating point arithmetic, 131, 230, 306, 411. % 42nd Fraenkel, Aviezri Siegmund ({\heb\Hll/\Hqq/\Hnn/\Hrr/\Hpp/ \Hyy/\Hrr/\Hzz/\Hai/\Hyy/\Hbb/\Haa/}), 251. % 39th Fuller, John Edward, xi. % 32nd Geek art, xx. % 34th GO button of \MIX, 126, 139, 143--144, 211. % 29th Gordon, Peter Stuart, xi. % 32nd Greedy algorithm, 489. % 40th Hamel, Georg Karl Wilhelm, 480. % 39th Hal\=ayudha ({\dn hlAy\kern-0.4em\char0\kern.45emD}), 54. % 46th Honeywell H800 computer, 124. % 46th Huskey, Harry Douglas, 229. % 34th IBM Corporation, 457. % 44th Ingalls, Daniel Henry Holmes, Jr\period, 522. % 47th Insertion of a node: Entering it into a data structure. \sub into queue, 242, 244--245, 254, 260, 265, 273--274, 278. % 47th Internet, iv, xvi, 112. % 46th Invariants, 2, 17. % 41st Kinkelin, Georg David Hermann, 504. % 39th Knuth, Nancy Jill Carter (\GC75:75:-3:62% G2463 <0000001f0000000000000000001ff8000000000000000007ff000000000000000003ff80% 00000000000000007f8000000000000000007f8000000000000000003f8000003c000000% 00003f8000007e00000000001f800000ff00000000000f800001ff00ffffffffffffffff% ff80ffffffffffffffffffc07fffffffffffffffffe03800000000000000000000000000% 00000000000000000000000070000000000078000000f800000000007f000001fc000000% 00007ffffffffe00000000007fffffffff00000000003ffffffffe00000000003f000000% fc00000000003f000000fc00000000003f000000fc00000000003f000000fc0000000000% 3f000000fc00000000003f000000fc00000000003f000000fc00000000003f000000fc00% 000000003ffffffffc00000000003ffffffffc00000000003ffffffffc00000000003f00% 0000fc00000000003f000000fc00000000003f000000fc00000001c03e0000000003c000% 01e03e0000000007e00001f800000000000ff00001fffffffffffffff00001ffffffffff% fffff80001f8000000000007f80001f8000000000007e00001f8000000000007e00001f8% 000000000007e00001f801c000078007e00001f801e00007e007e00001f801f8000ff007% e00001f801fffffff007e00001f801fffffff007e00001f801ffffffc007e00001f801f8% 000fc007e00001f801f8000fc007e00001f801f8000fc007e00001f801f8000fc007e000% 01f801f8000fc007e00001f801f8000fc007e00001f801f8000fc007e00001f801f8000f% c007e00001f801f8000fc007e00001f801ffffffc007e00001f801ffffffc007e00001f8% 01ffffffc007e00001f801f8000fc007e00001f801f0000fc007e00001f801f0000f0007% e00001f801f000000007e00001f8000000000007e00001f800000000ffcfe00001f80000% 00007fffc00001f8000000000fffc00001f80000000000ffc00001f800000000007f8000% 01f800000000003f800001f000000000001f000001f00000000000100000>%% Unicode char "9ad8 \GC75:75:-3:62% G3011 <0001e0000000000000000001f8000001f00000000001ff000001ff0000000000ff000001% ff0000000000fe000001ff0000000000fc000001fe0000000000f8000001fc0000000000% f8000001f80038000000f80e0001f800fc000000f80f0001f801fe000000f81f8001f803% ff000700f81fffffffffff800380f81fffffffffffc003c0f81f8fffffffffc001e0f83f% 0001f800000001f0f83f0001f800000000f8f87e0001f800000000fcf87c0001f801c000% 00fef8f80001f803e000007ef8f80001f807f800007ef9f00001f80ffc00007efbe01fff% fffffe00007efbc00ffffffffe00007cff0007fffffffe00007cfe000001f80000000008% fa1e0001f80000000000f83f0001f80000000000f87f0001f8001c003fffffff8001f800% 3e001fffffffc001f8007f801fffffffe001f800ffc00803f803ffffffffffe00003f801% ffffffffffe00003f800ffffffffffe00003f8000000000000000007fe00000000000000% 0007ff800f0000078000000fffe00fc0000fc000000ffff007ffffffe000001ffff807ff% fffff000001ffbfe07fffffff000003ef9fe07c00007e000003ef8fe07c00007c000007e% f87f07c00007c000007cf83f07c00007c00000fcf83f07c00007c00000fcf81e07c00007% c00001f8f81e07ffffffc00001f8f80007ffffffc00003f0f80007c00007c00003e0f800% 07c00007c00007c0f80007c00007c0000fc0f80007c00007c0000f80f80007c00007c000% 1f00f80007c00007c0001e00f80007c00007c0003c00f80007ffffffc0007000f80007ff% ffffc0006000f80007ffffffc000c000f80007c00007c0008000f80007c00007c0000000% f80007c00007c0000000f80007c00007c0000000f80007c00007c0000000f80007c00007% c0000000f80007c00007c0000000f80007c00007c0000000f80007c03fffc0000000f800% 07c01fffc0000000fc0007c007ffc0000000fc000fc001ffc0000000fc000fc0007fc000% 0001fc000fc0003f80000001f8000fc0001f80000001f8000000001e0000>%% Unicode char "7cbe %\JC47:48:-1:40% J4586 %<0001801800000001e01e00000001f01f00180001e01e003cfffffffffffefffffffffffe% % 0001e01e00000000c00c00001800306000c01e00787801e01ffff87ffff01ffff87ffff0% % 1e00787801e01e00787801e01ffff87fffe01ffff87fffe01e00787801e01e00787801e0% % 1ffff87fffe01ffff87fffe01e00787801e01e00363001e01e00078001e01e0007c031e0% % 1e00078079e01efffffffde01e7ffffffde01e00078001e01e0c078181e01e0fffffe1e0% % 1e0fffffe1e01e0f0783c1e01e0f0783c1e01e0fffffc1e01e0fffffc1e01e0f0783c1e0% % 1e0f0783c1e01e0fffffc1e01e0fffffc1e01e0f3fc3c1e01e067ff981e01e007fbe01e0% % 1e00f79f01e01e01e78f81e01e03c78fffe01e078787cfe01e1e0783c7c00c7803018380% % >%% Unicode char "862d \GC76:72:-2:62% G3228 <000000000000380000000000700000003c00000000003c0000007e00000000003e000000% 7f80000000001f8000007fc0000000001fc000007fe0000000000fe000007f8000000000% 07f00000ff800000000007f80000ff000000000003fc0000fe000000000003fc0000f000% 0000000001fe0001f0000000000001fe0001e0000000000000fe0003e0000000000000fe% 0007c00000000000007e0007c00000000000007e000f800000000000007e001f00000000% 0000003e003f000780000000003c003e000fc00000000038007c000fe000000000000078% 001fe0000000000000f0003ff00003fffffffffffffff80001fffffffffffffffc00007f% fffffffffffffc0000180000000000000000000000000000000000000000000000000000% 000000000000000000000000000000000000000000000000000000000000000000000000% 000000000000000000000000000000000000000000000000000000000000000000000000% 000000000000000000000000000000000000000000000000000000000000000000000000% 00380000000000000000007c000000000000000000fe000000000000000001fe00000000% 0000000003ff0000000fffffffffffff8000000fffffffffffffc0000003ffffffffffff% c0000000c000000000000000000000000000000000000000000000000000000000000000% 000000000000000000000000000000000000000000000000000000000000000000000000% 000000000000000000000000000000000000000000000000000000000000000000000000% 000000000000000000000000000000000000000000000000000000000000000000000000% 00000000000000000000000000000000380000000000000000007c000000000000000000% fe000000000000000000ff000000000000000001ff800000000000000003ffc0ffffffff% ffffffffffe0fffffffffffffffffff03ffffffffffffffffff008000000000000000000% >%% Unicode char "5170 ), x, xx. % 33rd K\"onigsberg bridges, 374. % 36th Lagrange, Joseph Louis (= Giuseppe Lodovico Lagrangia = Giuseppe Ludovico (= Luigi) De la Grange Tournier), inversion formula, 392, 594. % 39th %Lam\'e, Gabriel L\'eon Jean Baptiste, 407. % 34th Lam\'e, Gabriel, 407. % 37th Leaf of tree, 308, \see Terminal node of a tree. % 39th Lenormand, Claude, 527. % 44th L\'evy, Paul Pierre, 363. % 39th Lilius, Aloysius (= Aloigi Giglio, Luigi Lilio), 159. % 33rd Lineal chart, 310--311, 465. % 32nd List head, in circular lists, 275, 278, 302--303. % 47th log (without subscript), 110. % 33rd Luschny, Peter Heinrich Nikolaus, 112. % 46th Markov, Andrei Andreevich ({\rus Markov, Andrei0 Andreevich}), the younger, 9. % 31st McCall's Cook Book, v. % 41st Mealy, George Henry, II, 462. % 36th Mirsky, Leon ({\rus Mirskii0, Leonid}), 587. % 36th Neumann, John von (= Neumann J\'anos Lajos = Margittai Neumann J\'anos), 18, 229, 231, 457. % 34th Nonnegative coefficients, 396, 501. % 30th Number system, decimal, 21, 619. % 32nd OEIS\regtm: The On-Line Encyclopedia of Integer Sequences\regtm\ ({\tt oeis\period org}). % 43rd Oldenburg, Henry (= Heinrich), 57. % 36th Output-restricted deque, 239--243, 269, 274, 278. % 47th Overflow toggle of \MIX, 126, 131, 134, 142, 144, 208, 214, 228. % 29th Pak, Igor Markovich ({\rus Pak, Igorp1 Markovich}), 407. % 37th Pattern matching, 8. % 31st Pedigree, 310--312, 465. % 32nd Pi ($\pi$), as ``random'' example, 45, 397, 591. % 47th Pi\:ngala, \=Ac\=arya ({\dn aA\char99A\hbox{y\kern-0.3em\hbox{\char13}} Ep\char189l}), 54. % 46th Psi function $\psi(z)$, 44, 75, 493, 622. % 49th Quick, Jonathan Horatio, 45, 502. % 47th Queue, deletion from the front, 242, 244--245, 254, 261, 265, 273--274, 278. % 47th \sub insertion at the rear, 242, 244--245, 254, 260, 265, 273--274, 278. % 47th \sub linked allocation, 259--261, 269, 273--274, 278, 288. % 47th Reingold, Edward Martin ({\heb \Hdd/\Hll/\Hvv/\Hgg/\Hnn/\Hyy/\Hyy/\Hrr/},\indexbreak{\heb \Hfm/\Hyy/\Hyy/\Hkh/ \Hfn/\Hbb/ \Hhh/\Hsh/\Hmm/ \Hqq/\Hkh/\Hts/\Hyy/}), 518. % 33rd Representation (inside a computer),\indexnoperiod \sub of queues, 244--245, 251--254, 259--261, 269, 273--274, 278, 288. % 47th \sub of stacks, 244--254, 258, 269--270, 273--274, 278, 332, 417. % 47th Residue theorem, 472--473. % 37th Reversion storage, 229, 240. % 34th Rice, Stephen Oswald, 565. % 44th Root of a tree, 308, 309, 317, 465. % 32nd Schwenk, Allen John Carl, 495. % 42nd Stack, linked allocation, 258, 269, 270, 273--274, 278, 332, 417. % 47th Staver, Tor B{\o}hm, 582. % 28th Stirling numbers, 66--69, 71--74, 78, 99--100, 506, 582, 591, 625. % 34th sup: Supremum, least upper bound, 37. % 40th Swift, Jonathan, 630. % 39th Szpilrajn (later Marczewski), Edward, 268. % 36th Terminal node of a tree, 308, 318, 352, 397, 589, 597. % 39th Tetali, Venkata Sitarama Vara Prasad \indexbreak({\tl\|0142|\C86\\2\|0128|\C86\\2\C222\ \|0141|\C107\\2\C9\|1128|\C71\\2\C81\ \|2132|\C110\\2\|0129|\C86\\5\|0129|\C103\\6\|0128|\C101\ \|0128|\C107\\2\|0128|\C103\ \|1128|\C97\\{-7}\C175\\3\|0129|\C110\\5\|1148|\C88}), 547. % 39th Totient function $\varphi(n)$, 42--43, 526. % 46th Trees, diagrams of, 309--315, 337, 346, 349, 460, 465. % 32nd Trinomial coefficients, 65. % 49th Trucco, Ernesto, 23. % 33rd Victorius of Aquitaine, 518. % 33rd Virah\=a\:nka, \=Ac\=arya ({\dn aA\char99A\hbox{y\kern-0.3em\hbox{\char13}} EvrhA\kern-.35em{\char"5C}k}), 53--54, 80. % 46th von Neumann, John (= Neumann J\'anos Lajos = Margittai Neumann J\'anos), 18, 229, 231, 457. % 34th Wahid Aziz Abdel-Malek, George \indexbreak ({\arab\Afc/\Aml/\Amm/\Ail/\Aa/ \Afd/\Amb/\Aiai/ \Afz/\Aiy/\Afz/\Aiai/ \Afd/\Amy/\Aihh/\Aw/ \Atch/\Ar/\Afw/\Aitch/}), 509. % 39th Ward, Martin Paul, 576. % 32nd Windley, Peter Francis, 523. % 34th Xie, Xie (\GC78:79:-1:63% G4827 <000000001f0000038000000000001fc00003f00000c000001fc00003fc0001f000001fc0% 0003fc0000f800001f800003fc00007c00001f800003f800003e00001f000003f000001f% 00001e000003f000001f80601e070003f000001fc0783c0f8003f000000fc07c381f8003% f000000fe07e783fc003f000000fe07fffffe003f000000fe07fffffe003f0000007e07f% ffffc003f0000007c07e003f8003f0000007c07e003f0003f0000007007e003f0003f000% 0000007e003f0003f0000000007e003f0003f1c00000007e003f0003f3e00000007e003f% 0003f3f00000007e003f0003f7f80000007fffff7ffffffc0000007fffff3ffffffc0000% 007e003f1e03f000003e007e003f0003f000007f007e003f0003f000ffff807e003f0003% f000ffff807e003f0003f0007fff807e003f0003f000207f007e003f0003f000007e007e% 003f0003f000007e007fffff0003f000007e007fffff0003f000007e007fffff0003f000% 007e007e003f0c03f000007e007e003f0e03f000007e007e003f0703f000007e007e003f% 0783f000007e007e003f07c3f000007e007e003f03e3f000007e007e003f03f3f000007e% 007e003f03f3f000007e007e003f01f3f000007e007e003f01f3f000007e1fffffff00f3% f000007e0fffffff00f3f000007e040007ff00f3f000007e00000fff00f3f000007e0000% 0fff00f3f000007e01c01fff0023f000007e03c01fbf0003f000007e03803f3f0003f000% 007e07003e3f0003f000007e0e007e3f0003f000007e1e00fc3f0003f000007e1c01f83f% 0003f000007e3803f83f0003f000007ef003f03f0003f000007fe007e03f0003f000007f% c00fc03f0003f000007fc01f803f0003f000007f803f003f0003f000007f007e003f0003% f000007e00fc003f0003f000007c00f8003f0003f00001f801f0003f0003f00000f803e0% 003f0003f00000700780fc3f1f83f00000200f00ffff1ffff00000003c003fff03fff000% 000078000fff00fff0000001e00003ff003ff0000003c00001fe003fe0000003000001fc% 001fe0000001000001f0000fc0000000000001e0000f000000000000000000080000>% % unicode char "8c22 \GC79:79:-1:63% G5936 <0000f0000000000000000000fc000000000000000000ff800000000000000000ff800000% 000000000000ff0000e000003c000000fe0000f800007e000000fc0000fe0000ff800000% fc0000ffffffffc00000fc0000ffffffffc00000fc00e0ffffffff000000fc03f0fc07c0% 7e000000fc07f8fc07c07e000ffffffffcfc07c07e0007fffffffefc07c07e0007ffffff% fefc07c07e000200f803fcfc07c07e000000f803f8fc07c07e000001f803f0fc07c07e00% 0001f803f0fc07c07e000001f803f0fc07c07e000001f803f0fc07c07e000003f003e0ff% fffffe000003f003e0fffffffe000007e003e0fffffffe000007e007e0fc07c07f00000f% c007e0fc07c07f00000f8fffe0fc07c07f00001f9fffe0fc07c07f00001f0fffe0fc07c0% 7f00003f03ffe0fc07c07f00007e01ffc0fc07c07f00007c007fc0fc07c07f0000f0003f% 80fc07c07f0003e0001f00fc07c07f0007e0001e00fc07c07f001ff801f000ffffffff00% 3ffc01fe00ffffffff003ffc00fe00ffffffff003df800fc00fc00007f0001f000f800fc% 00007f0001f0e0f870fc00007e0001f1f8f8fcfc0f007e0001f3fcf9fe0007800000ffff% ffffff0007c000007fffffffff0783e000007fffffffff07e3e0300001f1f0f8ff07f1f0% f80001f1f0f8fe07fdf87c0001f1f0f8f803fdfc7e0001f1f0f87803f9fc3f0001f1f0f8% 7863f0fc3f8001f1f0f87863f0fc1fc001f1f0f87863f0fc0fe001f1f0f87863f0fc07f0% 01f1f0f87863f0fc07f801e1f1f87863f0fc03fc01e1f1f878e3f0fc03fc01e1f1f878e3% f07801fe03e1f3f078e3f00181fe03c1f3f079e3f001c0fe03c1f3f07be3f001c0fe03c1% f7f07fe3f001c0fe07c1f7e0ffe3f001c07c0781f7e0ffe3f001e07c0783ffe0ffe3f001% e0600ff3ffc1ffe3f001e0000fffffc1ffc3f003e0001f3ffffffb83f003f0001e1fff7f% f003f803f0003e0fbf3ff003f803fc003c0f3e1ff003fffffc0078087e0fe003fffffc00% 7000fc0fc003fffff800f001f80f8001fffff800e003f0080001ffffe0004007c0000000% 00000000000f8000000000000000000f0000000000000000000e0000000000000000>% %% unicode char "52f0 ), 273, 278. % 47th Zeckendorf, \smash{\'E}douard, 495. % 36th Zedan, Hussein Saleh Mamoud\indexbreak ({\arab\An/\Aa/\Afd/\Aiy/\Az/ \Ad/\Afw/\Amm/\Amhh/\Aim/ \Afhh/\Ail/\Afa/\Aiss/ \Afn/\Amy/\Ams/\Aihh/}), 576. %32nd \vfill \enddoublecolumns \endchange \bye [The next printing will be the 50th.] Not mentioned above: ARTICLES "TO APPEAR" THAT ARE STILL PENDING: