Tuesday, April 8, 2008


Last week, I wrote about one of my more spectacular failures, which involved a progression that began 1, 2, 4, 8, 16, 32, but then rather than continuing sensibly as 64, 128, ..., instead exploded into 273, 65569, 4294967361, and 1.5x1082. The next term is a little over 265569 and the term after that a little over 24294967361, which has about a billion digits when written out in full.

Joshua Zucker suggested that I submit this to the On-Line Encyclopedia of Integer Sequences, which I did. So I've now been immortalized in Sequence A137181. I can see my tombstone now: “He failed...BIG.”

Several years ago I was giving a guest lecture in a colleague's Algorithms class, when I encountered immortality of a different sort. The students were asking me about how I invented “Okasaki trees”, and were dumbfounded when I didn't know what they were talking about. How could I not know about Okasaki trees when I invented them? “Well,” I told them, “I've invented a lot of different data structures, and most of them are trees of one kind or another. But I've never called any of them Okasaki trees.” After a bit more digging, it turned out that my colleague (who wasn't there that day) had been telling them the previous week about my simplification of red-black trees, and he called them Okasaki trees.

The lasting result of this is that I now have a friend at work who ribs me about Okasaki trees every chance she gets.

No comments: