Lesson 2.1: Zeller's Congruence

This lesson does not cover any new topics. In this lesson, we practice using variables and assignments to solve the problem of finding the day of the week for a given date.

This is an optional lesson. You should read Lesson 1 and Lesson 2 before this one, but you can continue to Lesson 3 without reading this.

What's the problem?

Some of the problems we covered in Lessons 1 and 2 have been pretty obscure, right? Well here's one that's clearly important: Find the day of the week given a date, like January 12, 1992. There's a formula to solve this problem called Zeller's Congruence. Any program on your computer that deals with dates, like a calendar or spreadsheet program, probably has some version of Zeller's Congruence built in.

Like in Lesson 2, we'll enter the program into a text editor (I'm calling the file zeller.bc) and run the program in a terminal. Our program will start by setting three variables, for the day, month, and year, and it will end with halt:

zeller.bc

day = 12
month = 1
year = 1992

halt

When we're done, it will give us a number that represents the day of the week for this date. You're probably not used to thinking of days of the week as numbers, but we do the same thing with months. Here's the numbering we're going to use:

0	Sunday
1	Monday
2	Tuesday
3	Wednesday
4	Thursday
5	Friday
6	Saturday

Since January 12, 1992 was a Sunday, our program should output 0 when we run it with day, month, and year set to 12, 1, and 1992. This is how it will look when we run the completed program (we'll be using integer mode):

christopher:~/smooth$ bc -q zeller.bc 
0
christopher:~/smooth$

Of course, if we want to know the day of the week for a different date, we'll just need to change the three variables at the top and run it again.

This is actually a really complicated problem, because the Gregorian calendar system is a total mess. Months can have 28, 30, or 31 days, and they come in a strange order, and then 24.25% of years are leap years, when February has 29 days. Also, any solution to this problem has to be exactly right. You can't make any approximations like ignoring leap years, because if you skip even one day, the day of the week will be off for every day that follows it. So it's a complicated pattern that we have to describe exactly right. But it is still a pattern, so theoretically we could come up with a mathematical formula that gives us the day of the week.

That sounds like a lot of work, though. Fortunately for us, Christian Zeller already did it in 1882.

Step 1: renumber the month and year

Zeller's Congruence has three steps. Step 1 is actually the hardest. It's a trick Zeller came up with to deal with February. February is a pain because it's the only month that doesn't have 30 or 31 days, and the number of days it has depends on whether it's a leap year or not. If February were the last month of the year, it would be much easier to deal with. So instead of the year running from January to December, under Zeller's Congruence, the year runs from March to February. It's weird, but like I said, this is the hardest step, so just bear with me.

When you shift the end of the year by 2 months like this, January and February actually change years. Here's what the regular month numbering looks like:

November 1991	11/1991
December 1991	12/1991
January 1992	1/1992
February 1992	2/1992
March 1992	3/1992
April 1992	4/1992
May 1992	5/1992

And here's what it looks like for Zeller's Congruence:

November 1991	8/1991
December 1991	9/1991
January 1992	10/1991
February 1992	11/1991
March 1992	0/1992
April 1992	1/1992
May 1992	2/1992

Also notice that the months run from 0 to 11, rather than from 1 to 12.

So the first thing we have to do is modify the month and year variables in our program, to change them to the Zeller versions. Here are the assignments that do this:

month += 9
month %= 12
year -= month / 10

This is actually kind of an ugly way to do this step. When we get to Lesson 4 we'll learn a better way, but this way works, even if it is kind of ugly. You can use these lines without trying to understand them. If you want an explanation, though, click here for more information:

Click to reveal explanation

Click to hide

To understand the month statements, you have to think in terms of the month number "wrapping around". This is a way of counting called modular arithmetic. Under arithmetic mod 12, any time a number goes to 12, it wraps back around to 0. So for instance, 9 + 4 = 1. That's like saying that September (month = 9) plus 4 months brings you to January (month = 1). Arithmetic mod 12 also appears on a 12-hour clock: 9:00 plus 4 hours brings you to 1:00.

So that's the reason for the line month %= 12. This line changes the month to whatever its mod-12 equivalent is in between 0 and 11. Using the example from before, (9 + 4) % 12 = 1. You can add as many numbers as you want together, and then just take it mod 12 at the end, and you'll end up with a number between 0 and 11. For instance, if you start in October (month = 10), and then go 4 months into the future, then another 11 months, then 197 more months, what month is it? It's June (month = 6), as you can see by entering into bc:

(10 + 4 + 11 + 197) % 12
6

The Zeller month number is 3 behind the regular month number, which is the reason for the line month += 9. In arithmetic mod 12, adding 9 is the same as subtracting 3. (In terms of a 12-hour clock, going forward 9 hours is the same as going back 3 hours.) The reason we add 9 instead of subtracting 3 is because of a complication when you try to take the mod of a negative number. Under true modular arithmetic, -2 is the same as 10, so you might expect that -2 % 12 would give you 10. As it is, some programming languages give you 10 and some give you -2, and unfortunately bc is one of the ones that gives you -2. So we avoid that issue by not taking the mod of a negative number.

The year formula is a little simpler. If it's January or February (month is 10 or 11, after the month number is modified), we need to subtract 1 from year. In integer mode, division is rounded down to the next whole number. So the expression month / 10 will be equal to 1 when month is 10 or 11, and equal to 0 when month is between 0 and 9. So subtracting month / 10 from year does what we need.

At any rate, these statements should be added to the program, so now it looks like this:

zeller.bc

day = 12
month = 1
year = 1992
month += 9
month %= 12
year -= month / 10

halt

Step 2: split the year

Step 2 is a little easier. The year has to be split into two parts, which we'll call c and d. d is the last two digits of the year, and c is everything before the last two digits. So if year is 1984, then c is 19 and d is 84. And if year is 2364, then c is 23 and d is 64.

The way we're going to do this is by dividing by 100. Remember that in real mode, 1984 divided by 100 would be 19.84, but in integer mode, it's 19 remainder 84. The quotient (19) is what we want to assign to c, and the remainder (84) is what we want to assign to d. See if you can fill in the assignments for c and d in the program:

zeller.bc

day = 12
month = 1
year = 1992
month = (month + 9) % 12
year -= month / 10
c = ???
d = ???

halt

If you can't figure out what the assignments for c and d should look like, check out the answer here:

Click to reveal solution

Click to hide solution

c = year / 100
d = year % 100

Step 3: apply Zeller's formula

The last step is simply a formula that converts day, month, c, and d into the day of week number:

(a + b + day) mod 7

where $$a = d + d/4 + c/4 + 5c$$

and $$b = {13 month + 11}/5$$

All of the divisions in this formula need to be rounded down to the next whole number. That's fine, because that's how division works in integer mode.

It's probably not worth trying to understand this formula, but for one thing, you know that it will always give you a number from 0 to 6. This is because the whole thing is taken mod 7, and the remainder when you divide by 7 is always between 0 and 6.

Try to complete your program using this formula. When you think you've got it, you can try running the program and see if you get 0 like you should. You can also try changing day, month, and year to today's date, and see if your program gives you the number for the current day of the week.

If you have any trouble, compare your program to this one:

Click to reveal completed program

Click to hide completed program

zeller.bc

day = 12
month = 1
year = 1992
month += 9
month %= 12
year -= month / 10
c = year / 100
d = year % 100
a = d + d/4 + c/4 + 5*c
b = (13*month + 11) / 5
(a + b + day) % 7
halt

Practice

If your program is working correctly, use it to find the day of the week for these dates:

1. December 21, 1872
2. November 12, 1955
3. January 1, 802701

Click to reveal solution

Click to hide solution

1. December 21, 1872: Saturday
2. November 12, 1955: Saturday
3. January 1, 802701: Tuesday