## John Conway’s algorithms for counting stairs and reading double-sided paper?

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 $\mathrm{lcm}\ \{3,7,10,16\} = 1680$, 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!

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

### 9 Responses to John Conway’s algorithms for counting stairs and reading double-sided paper?

1. blaisepascal2014 says:

My method for reading papers is to maintain two stacks, one face up on the right, one face down on the left. Going to the next page simply moves a page from one stack to the other, turning it over in the process. It works equally well for both single and double-sided papers.

I do agree that there is a problem with interrupted reading, or when you can’t maintain space for two stacks. My method wouldn’t work, for instance, if I were holding the stack in hand, and not sitting at a table.

One thing you could do is use a post-it note or similar to flag the left side of the stack. Then when you finish reading side one, shift the leaf to the back like normal, then turn the whole stack over to read side two. This puts the flag on the right side of the stack. Then flip the stack over again to read side one of the next leaf. If you have to put down the stack, the side the flag is on indicates whether this is the front or back side you are reading, and you can shift/flip as appropriate.

• Brent says:

Ah, that makes sense, basically you treat the pages as if they are the pages of a book. I think I have done that at times but I should try to keep it in mind more often! In any case, yes, I was specifically thinking about the situation when you are, say, holding the stack of paper in your hand. I like your idea about a post-it note, I will have to give that a try to see how it works in practice! The one downside I can see is that you have to remember which side of the stack the post-it is “supposed” to be on, but at least you get to be consistent. You would just have to come up with some mnemonic that made sense to you. “Left Leaf, Right Reverse” or something like that.

• blaisepascal2014 says:

Yep, treat two stacks like the pages of a book.

My single-stack method is equivalent to treating the one stack like the pages of a book with a spiral binding. When you are reading an odd-numbered page, the binding is typically on the left. When you are reading an even-numbered page, the binding is typically on the right. When you want to go from an odd-numbered page to an even-numbered page, you turn the page over (putting it in the back of the book), then flip the book over so the binding is on the right. When you want to go from an even-numbered page to the next odd-numbered page, you just flip the book over so the binding is on the left again. The post-it simply marks which side of the stack has the virtual binding.

• Brent says:

Yes, makes sense. (This makes me think of another algorithm: just three-hole punch the pages and put them in a binder. 😉

If you don’t have a post-it handy you could always dog-ear the top left corner of the first page. If you don’t put too much energy into the crease it shouldn’t be too hard to notice which side the dog-ear is on. I just tried it with a stack of paper, and all I have to do is look at the edges of the stack (in practice you can e.g. gently bend the stack into a U shape with the ends towards you, to see both edges of the stack at once) to see where the dog-ear is, since it creates a little gap in the stack.

2. mrob27 says:

Make sure all pages are aligned neatly, then fan the whole stack slightly (by curling, the way one might do when loading blank paper into a printer). Once fanned, a tiny bit (a millimetre or so) of each sheet is exposed. Draw a line that touches each page only briefly. Now all the odd-numbered pages have a mark. I draw my line diagonally, so I can use the marks to re-sort the pages if they get shuffled.

• Brent says:

Oh, great idea! I like it.

• mrob27 says:

Thanks. It’s quick, and minimally destructive… though I’ve been known to punch holes or dog-ear corners, as others suggested. But I’ve never committed the unforgivable crime uf using a stapler 😀