In the process of looking up John Conway’s “Doomsday Algorithm” for figuring out what day of the week “any” date falls on, I came across Chamberlain Fong’s description of a simplification of Conway’s algorithm that he and Michael Walters came up with, which they describe in a paper on arxiv. (“Any” is in quotes for reasons explained in Part 2.)
What does the Fong/Walters algorithm do differently? Let’s note what’s the same. Conway’s scheme of “Doomsdays” is still in place, and you still need to know the Doomsday for the start of the century. The difference is in computing the offset. There is no dividing by 12, remembering the quotient, dividing the remainder by 4, etc. (Apparently that part of the method was due to Lewis Carroll, as explained in Part 2 or in Fong’s Scientific American blog post.)
How does the alternate method , which they call “odd+11” work? If you love flowcharts, look here. But it’s pretty simple:
- Take the last two digits of the year.
- Is it odd? If so, add 11.
- Divide your number (which now must be even) by 2.
- Is your new number odd? If so, add 11 again.
- Reduce your number modulo 7.
- Subtract your number from 7 (“take the 7s complement”).
The number you come up with is your offset from the Doomsday at the start of the century. Let’s try it with 2020, and check the result against what we got in Part 1. Step 1: 20. Step 2: Not odd, so still 20. Step 3: 10. Step 4: Still not odd, so still 10. Step 5: 3. Step 6: 4. That is what we got in Part 1.
To be honest, I’m not wild about Steps 5 and 6. Really, it should be one step that says “Take the negative of your number, modulo 7.” If your number is 14, it is 0 modulo 7. The negative of 0 is still zero. That is better than subtracting it from 7, coming up with 7, and saying, “Well, 7 is 0 modulo 7, anyway, so let’s call it 0.”
Let’s also do 1929, because it illustrates another reason why I prefer the modified Step 5/6. Step 1: 29. Step 2: Odd, so 40. Step 3: 20. Step 4: Not odd, so still 20. Following Fong/Walters, you could say 20 is 6 modulo 7, and the 7s complement is 1. And that is the correct answer, as we saw in Part 1. But 21 is a multiple of 7, so you could just say “20 is -1 modulo 7,” and if we take the negative of that, we get 1 immediately.
How did Fong and Walters come up this? I have no idea, but my guess is that it involved a lot of time noodling around.
How do we know it works? Fong and Walters give a proof, but I think it’s possible to simplify the proof, a lot. [Edit: I would also have said I don’t really understand why it works, but see the addendum below.]
What happens to your answer if you add 4 to the year? How does that change your calculation? Well, the first thing to notice is that if the number was even before, it’s still even, so you will do the same thing you did before in step 2, and so the number you at the end of Step 2 is 4 more than what you had before. In Step 3, the number that you end up with will be 2 more than what you had before. So if your number was odd before, it still is, and at the end of Step 5, your number is still 2 more than what you had last time around. When you reduce modulo 7, your number is still 2 more (understood modulo 7). When you take the negative modulo 7, you wind up with something that is 2 less. But modulo 7, 2 less is the same as 5 more! This is exactly what we want! Advancing the year by 4 should advance the day by 5—one for each year, and one for the leap year.
Once we know that, it’s enough to show that it works for 00, 01, 02, and 03… and then you can get to any year up to 99 by repeatedly adding 4. (This is the wonder of “mathematical induction.”) I don’t have the stomach to drag either of us through a written blow-by-blow, but this table shows you the result of each step:
| Year/Step 1 | Step 2 | Step 3 | Step 4 | Step 5 | Step 6 |
| 00 | 0 | 0 | 0 | 0 | 0 |
| 01 | 12 | 6 | 6 | 6 | 1 |
| 02 | 2 | 1 | 12 | 5 | 2 |
| 03 | 14 | 7 | 18 | 4 | 3 |
At the end of Step 6, we see that each year advances the day by 1, which is exactly what we need! And we saw above, that for 04, the day will advance by 5, again exactly what we need.
Addendum, later that same day. I sent an appreciative email to Fong and Walters. I heard back from Mike Walters almost immediately. He wrote:
I actually did come up with the idea by ‘noodling around’ for an hour or so, as described on my blog … I never liked Conway’s method, there was too much mental math involved for my tastes … One night I was bored and I just wrote out the grid of years (the one shown on my blog post) and stared at it until I saw the pattern with the leap years, then the rest came together.
He noticed two things:
- If you have a leap year, dividing by 2 and taking the negative modulo 7 gives you the correct offset. This is exactly what we saw above: every extra 4 years adds two to the quotient, taking the negative subtracts 2, which is the same modulo 7 as adding 5, which is exactly how much each subsequent leap year needs to add to the offset.
- If you have a non-leap year, the year 11 years later has the same Doomsday.*
So Walters’ original algorithm is “just add 11 until you get to a leap year [something divisible by 4], and then do the divide by 2 and negative-modulo-7 thing. You might have two add 11 up to 3 times. Chamberlain Fong picked this up and made it even easier to compute, resulting in the steps above.
Before taking apart Fong’s version, why is it that adding 11 years to a non-leap year gives a year with the same Doomsday? It’s just what we’ve seen. If you start with a non-leap year, the subsequent 11 years will include 3 leap years. How many days will we advance the Doomsday when we go 11 years forward? One for each year, with an additional one for each leap year, is 11+3=14. But 14 is 0 modulo 7, so the two years have the same Doomsday.
How does Fong’s version work? Start with the last two digits. If your number is odd, add 11. Let’s call what we end up with “y.” It will be even, and it will refer to a year with the correct Doomsday. This y might be divisible by 4, or it might not. If it’s divisible by 4, we just saw that the negative of y/2, modulo 7, is the correct offset for our Doomsday. But if y is divisible by 4, y/2 is even, so the Fong algorithm gives us the right answer. Now here’s the clever thing: if y/2 is odd, adding 11 to y/2 has the same effect as adding 22 to y, that is, it’s the same as adding 11 to y twice. And it gets you to a place where the original leap year calculation works. So essentially the algorithm has a way of adding 11 to your original year either: 0 times (for a leap year), once (in Step 2 but not in Step 4), twice (in Step 4 but not in step 2), or 3 times (in Step 2 and step 4). How many times it does it depends on what your year is modulo 4, but you don’t have to think about that, you just think about even and odd.
I subsequently heard back from Chamberlain Fong. He pointed me to a survey of calendar methods by Kamal Abdali, which contains an alternate verification of the Fong/Walters algorithm. The proof I’ve given here is more “walking you through the algorithm,” and it may work better as a conversation than it does written out. Abdali’s proof, and Fong’s original proof, involve equations, which may be more to your taste. But if you want to clean up the discussion of the previous paragraph, you would end up looking at your year modulo 4. In other words, you would look at the two “least significant bits” in its binary expansion, which are “b” and “c” in Abdali’s paper. And there is something to clean up here, because the “add 11 and get a year with the same Doomsday” trick does not work if you start from a leap year. So if you’re effectively adding 11 two or three times, you need to verify that those take you to a leap year, not across one.
[*Just to keep you from tearing your hair out, I say “leap year” above when I should say “year divisible by 4. If we start in 1897, the subsequent 11 years include 3 that are divisible by 4: 1900, 1904, and 1908. However, 1900 is not a leap year, so it includes only two bona fide leap years. But the math still gives the correct answer for 1897, even though 1908 does not have the same Doomsday as 1897.]