Stanford Lecture: Don Knuth—"A Conjecture That Had To Be True" (2017)

I was going to post this on another thread (the Neal Stephenson one link ), but it also fits here: Donald Knuth does all his writing (even coding!) by hand with pencil on notepad, going through several rounds of editing before anything reaches a computer, and his stated reason is that he can type faster than he can think. (Somewhere a typing speed of 80 wpm is mentioned, which is not even all that fast.) So he says that writing by hand, being slower, perfectly matches the speed at which he can think. In other words, he describes himself as a slow thinker. (We can actually get some glimpses of the way he thinks from his public lectures, e.g. I love the 2017 Christmas lecture ▶ this video or maybe—I haven't watched much—the 1985 problem-solving seminar course link .) And if Knuth describes himself as a slow thinker, it is a lesson to us all.

Indeed! He mentions something related at 5:00 in the video ( ▶ this video ): > You know, people think that mathematicians have been working for hundreds of years and now there's tens of thousands or hundreds of thousands of mathematicians all spending every day working on problems so how could you possibly still find a simple down-to-earth problem that hasn't already been studied, you know, way too much? And the answer is: those problems aren't rare at all, they keep coming up several times a year, and this is an example where even this very basic problem of rectangle into rectangles has all kinds of, sort of, stones not yet turned. And the other thing you mentioned is one of the reasons it's always a pleasure for me to see Knuth's talks or read his work — he is one of the mathematicians (like Euler and unlike Gauss) who make it seem simple: we get the impression that we could do it too, if we spent enough time on it, that things are within reach for us, just barely. This is so inspiring. And then of course when you step back and look at his body of work, it's staggering! (Something like this talk may account for about half a page of Knuth's published output, and he has thousands of them…) That's additionally inspiring.

The best description of the OEIS I've heard is by Donald Knuth in this fun talk ( ▶ this video ) where at 19:50 he says how it lets you "compute your way into the literature": > For the last 30 years or more, there has been a wonderful tool for all kinds of problems of this form and it's been online for a long time: we have the Online Encyclopedia of Integer Sequences. And this is just the nicest thing since sliced bread for mathematics because you can compute your way into the literature. [audience laughter] If you want to know if anybody else has ever studied a problem, all you have to do is evaluate the first few cases of it and then you look it up and there it is. The hit rate is incredible, and all kinds of mathematicians have discovered each other through the OEIS. […] I donate to Wikipedia and the Internet Archive and the OEIS. (Aside: A good blog post about that lecture: link ) Indeed I've used it this way many times; the most recent example is that I became curious about how many polynomial functions there are mod n (after posting this comment: link ), and by computing the answers for n up to 10, I was able to look up up those numbers in the OEIS and find the general formula, and also the relevant papers. (Asked a question about it here: link but ended up answering it myself…) I don't think I'd have even known where to look (as I'm not a professional mathematician), if not for the OEIS. And this happens again and again.

His first publication, as a high-school student, was in MAD magazine. His books are full of jokes, both highly technical ones and more trivial ones. :-) If you have some mathematical inclination and a couple of hours to spare, you may like watching his (1-hour) Christmas lecture from 2017: ▶ this video — you may need to listen carefully (he's over 80 after all), but some of his humour comes through at moments.

> unfortunately he's unable to present it well. His lectures are almost useless. I don't know; I've listened to dozens of hours of his videos and found them all useful and rather clear. I've heard comments like yours from others though, and I guess there are two points: * Of course a person at 80 will not speak the same way they did at 40. (I'm currently watching his lectures on Mathematical Writing, given when he was 49: link -- youtube has some even older videos on TeX etc but they're probably of less general interest.) Older people generally have more halting speech and the like, but this is perfectly natural. I suspect that if, for cultural or whatever reasons, you haven't spent a lot of time listening to old people and learning from them, you may just find it unfamiliar. Nevertheless, I was in the audience when Knuth gave his 2017 Christmas Lecture weeks before his 80th birthday, and a lot of the audience did seem to follow along and enjoyed it. (You can hear laughter in the expected places in the video: ▶ this video -- so clearly not everyone feels the way you do.) * Every person has their own speech style, their way of translating thought into sounds. Like an unfamiliar accent, it may take a few minutes or hours to get used to it. (If you care enough about the content you will.) What you get from speech idiosyncrasies (their pauses, backtracking, mistakes, etc.) that you don't get from the written word is a window into someone's way of thinking, and I find in Knuth's lect

Don Knuth's 2017 Christmas lecture featured a way to count how many ways a rectangle can be subdivided into rectangles [0]. It got its own entry in the Online Encyclopedia of Integer Sequences [1]. [0] ▶ this video [1] link

Ah one place I ran across this: see 16:05 of Knuth's 2017 Christmas lecture ( ▶ this video ): > I got a nice piece of paper here to work with. They had a conference in Poland last year [BachoTeX 2016] and they sent me this nice pad of paper and I like it so much that I decided at my birthday party next month I gotta give out notepaper that's... [audio drowned by laughter] But actually the notepaper at my birthday party is going to be triangle... paper. Because I have a feeling that all kinds of mathematics has never been invented yet because people haven't been given triangle... [laughter].

This works well for me too :) Specifically when I am going to sleep. Recently, I spent a couple of days working on "tight paving/tiles" problem from Knuth's Christmas Lecture ( ▶ this video ) and surprised myself when I managed to exhaustively enumerate all valid arrangements(around 40 I think) for some small configuration while lying on the bed at night, something that I never thought I could do without a pen and paper.

I found Knuth’s “Dancing Links” paper [1] very well written and a somewhat easy read (I had to reread certain parts a couple times). I had to write a sudoku solver for one of my classes and I read that dancing links and algorithm x was one way to do it [2]. I then read some things around the internet to apply dancing links to sudoku solving [3] [4]. If you read the Wikipedia entry on exact cover problems there is a section on sudoku as an exact cover problem [5] this is one thing necessary to understand in order to implement a sudoku solver with algorithm x and dancing links. Knuth even talks about dancing links in his new 2017 Christmas Tree Lecture [6] specifically here at 4:28 [7]. Basically he uses dancing links to solve for certain n in the problem he sets up in that lecture. [1] link [2] link [3] link [4] link [5] link [6] ▶ this video [7] ▶ this video