This past week I started reading Siobhan Roberts’s new biography of John Conway, Genius at Play: The Curious Mind of John Horton Conway. I’m enjoying it so far. I’ll have more to say about it later, once I finish it, but for now, I was struck by this offhanded statement early in the book:
He’s invented many peculiar algorithms—for counting stairs while you climb without actually counting, and for how best to read through a stack of double-sided loose-leaf pages.
Naturally, I wanted to know what these algorithms are! As for the stair-climbing algorithm, Tanya Khovanova explains it here. The idea is to take the stairs not just one at a time, but in a one-two-two cycle. During one cycle you climb five stairs and take three steps (left-right-left or the reverse). You’ll come back to the beginning of the cycle on the same foot every ten stairs. When you get to the top, you can easily tell where you are in this ten-stair cycle. So this is an easy way to count stairs modulo ten. The idea is that you can usually estimate how many stairs there were to within ten, so you don’t need to actually count the number of ten-stair cycles.
Of course, if you are climbing something really tall like the Eiffel Tower, this estimation method does not work, and you have to actually count the number of ten-stair cycles. …or do you? I like the suggestion given by Paul, in a comment on Khovanova’s post, to enlist one or more mathematically-minded friends. If your friends climb in cycles other than 10 stairs, you can use the Chinese Remainder Theorem to work out the exact number of stairs up to the least common multiple of your cycle lengths. Paul suggests having one friend cycle by 3 stairs, which you could accomplish by a one-two cycle (i.e. always take a single step with your left foot, and two stairs with your right—although this has the distinct disadvantage of making one leg considerably more tired than the other; you friend could switch sides every now and then, by hopping from one foot to the other on the same stair). In any case, if you know the number of stairs modulo ten and also modulo three, then you can determine the number of stairs modulo 30. Then you only need to estimate the total number of stairs to the closest multiple of 30. You could additionally have another friend use a one-two-two-two pattern to count the number of stairs modulo 7 (with a similar but less marked asymmetry of effort); the three of you together could determine the number of stairs modulo 210. You could even get a fourth friend to use a one-two-one-two-two pattern, in order to count stairs modulo 16 (there are 8 stairs in the pattern, but it uses an odd number of feet, so it would take 16 stairs for the cycle to repeat). This would get you up to determining the number of stairs modulo , all without doing any actual counting. Not bad!
Now, as for the paper-reading algorithm. It is clear why this would be of interest to a mathematician: one often prints out mathematical papers double-sided, to save paper (and weight). From my own experience, it is also clear why one needs an algorithm. Reading a stack of single-sided pages is easy: when you are done reading a page, just move it to the bottom of the stack, and start reading the next one. With double-sided pages, however, there are two possible actions: either flip the current page over to read the other side, or move the current page to the bottom of the stack. In going through the paper, these actions strictly alternate. The problem is that while engaged in reading a paper, it is very difficult to remember which you did last! Sometimes there are page numbers, which help, but it is still a nuisance to flip back and forth looking at page numbers. Of course you always do one thing on odd pages and the other thing on even pages, but the parity might change from paper to paper (depending on whether there is a cover sheet or a table of contents and so on), so remembering which is the case for the current paper is hopeless. In any case, some papers do not even have page numbers.
I expect that Conway’s algorithm is some simple set of practices that make it physically easy to remember, with minimal effort, whether to flip a page over or move it to the back. So far I have been unable to find it by searching. Does anyone know what it is? Or, better yet, can you invent such an algorithm? Feel free to discuss ideas in the comments!