Basic Idea
The algorithm essentially counts the number of days that have
passed between a fixed date (this will be 1st January 0 AD) and a
chosen date (our birthday). By taking this number and finding its
remainder when divided by 7, provided we know what day of the week
it was on 1st January 0 AD we will know what day we were born
on.
Modular Arithmetic
We do not need to know the exact number of days that have passed
since our fixed date and our birthday, just the remainder when this
number is divided by 7. To make our algorithm easier to work with,
then, we will be taking certain shortcuts, so that what we
calculate is not actually the exact number of days, but a smaller
number which has the same remainder when divided by 7 (if this is
confusing, don't worry, it will make sense later).
Consequently, we'll be using the ideas of 'modular arithmetic', or
'clock arithmetic'. If you have not encountered these ideas before,
you should read the NRICH article on
modular
arithmetic . We want to know the number days between 1 Jan 0
and our birthday
mod 7
.
The Algorithm
A date can be divided into the following four bits information: the
number of hundreds of years, the number of additional years, the
number of months,and number of days that have passed since 1
January 0 AD. Suppose our birthday is 23rd September 1989. To count
the days that have passed since 1 Jan 0, we will use four steps:
count the days up to 1 Jan 1900, then the days between 1 Jan 1900
and 1 Jan 1989, the days between 1 Jan 1989 and 1 Sep 1989, and
finally the days between 1 Sep 1989 and 23 Sep 1989.
The number of days between 1 Sep 1989 and 23 Sep 1989 is obviously
23, or in general our number $D$. Years and months are a bit more
difficult.
Years
$$\frac{365}{7}=52\times 7+1$$ so there are exactly 52 weeks and
one day in a year. This means that our birthday moves forward by
one day each year i.e. 1 year $=$ 365 days $\equiv$ 1 day (mod 7).
So, mod 7, is the number of days between 1 Jan 0 and 1 Jan 1989 is
just 1989?
Unfortunately, we have to take leap years into account. There are
366 days in a leap year, and our birthday moves forward 2 days. We
need to add an extra 1 for each leap year on top of the total
number of years. How many leap years have passed since 1 Jan 0? You
probably know that we get a leap year every four years, in fact
precisely on those years which are divisible by 4. However, there
is one more rule you may not know: if a year is divisible by 100
but not divisible by 400 then it is
not a leap year. For example, 1900 is
divisible by 4, but not 400, so 1900 AD was not a leap year.
The number of leap years between $Y_F$01 and $Y_F$99 is always 24,
so if for a moment we ignore leap years on the turn of the century,
every 100 years our birthday moves forward 100 + 24 = 124 days =
18$\times$7 - 2 $\equiv$ -2 (mod 7). Now we add 1 for the leap year
on 0 AD and an additional 1 every 400 years up to $Y_F$00 (this
number is $1+\big[ \frac{Y_F}{4}\big]$, where $[x]$ denotes the
integer part of $x$. In general, then, between 1 Jan 0 and $Y_F$00
there are: $$-2Y_F+ 1 + \Big[ \frac{Y_F}{4} \Big]$$ days mod 7. Up
to 1 Jan 1900 this number is $19\times -2 + 1 + \big[ \frac{19}{4}
\big] = -33 \equiv2$.
Thinking a similar way we can show that between 1 Jan $Y_F 00$ and
1 Jan $Y_F Y_L$ there are $$Y_L \Big[ \frac{Y_L}{4} \Big] - 1$$
days mod 7,the -1 coming from the fact that we have taken account
of leap years occuring on centuries in out previous formula.
Putting the two parts of the year formula together, up to 1 Jan
$Y_F Y_L$ days are given by:$$-2Y_F+ 1 + \Big[ \frac{Y_F}{4} \Big]
+ Y_L + \Big[ \frac{Y_L}{4} \Big] - 1= Y_L - 2Y_F+ \Big[
\frac{Y_L}{4} \Big] + \Big[ \frac{Y_F}{4} \Big]$$
The number of days mod 7 up to 1 Jan 1989 is $2 + 89 +\big[
\frac{89}{4}\big] - 1 = 112 = 0$ mod 7.
Months
Months are tricky because they contain different numbers of days.
Coming up with a formula for the number of days in the first $M$
months in terms of $M$ is requires some thought. This is by far the
most difficult part of the algorithm to derive. The first columns
of the chart below show the months $M$, days mod 7 in that month,
and the days mod 7 before the $M$th month.
We want to come up with a formula that will approximate the number
of days before $M$ months mod 7, in the hope that we can make it
exact by taking its integer part. Our problem month is February,
which at only 28 days long makes it hard to average out the
months.The average number of days mod 7 in months
not February is around 2.6. So we take
as a first approximation $2.6 \times M$.
$M$ |
$\quad$ Days mod 7 in $M
\quad$ |
days mod 7 before $M \quad$ |
$2.6M$ mod 7 $\quad$ |
$2.6M-4$ mod 7 $\quad$ |
$[2.6M-4]$ mod 7 $\quad$ |
$2.6M-4.39$ mod 7 $\quad$ |
$[2.6M-4.39]$ mod 7 $\quad$ |
|
|
|
|
|
|
|
|
1 |
3 |
0 |
2.6 |
5.6 |
5 |
5.21 |
5 |
2 |
0 |
3 |
5.2 |
1.2 |
1 |
0.81 |
0 |
3 |
3 |
3 |
0.8 |
3.8 |
3 |
3.11 |
3 |
4 |
2 |
6 |
3.4 |
6.4 |
6 |
6.01 |
6 |
5 |
3 |
1 |
6 |
2 |
3 |
1.61 |
1 |
6 |
2 |
4 |
1.6 |
4.6 |
4 |
4.21 |
4 |
7 |
3 |
6 |
4.2 |
0.2 |
0 |
6.81 |
6 |
8 |
3 |
2 |
6.8 |
2.8 |
2 |
2.41 |
2 |
9 |
2 |
5 |
2.4 |
5.4 |
5 |
5.01 |
5 |
10 |
3 |
0 |
5 |
1 |
1 |
0.61 |
0 |
11 |
2 |
3 |
0.6 |
3.6 |
3 |
3.21 |
3 |
12 |
3 |
5 |
3.2 |
6.2 |
6 |
5.81 |
5 |
13 |
3 |
1 |
5.8 |
1.8 |
1 |
1.41 |
1 |
14 |
0 |
4 |
1.4 |
4.4 |
4 |
4.01 |
4 |
If we subtract 4 from our first approximation, then the integer
part of this is very close to an exact formula. You will notice if
we subtract a further number between 0.2 and 0.4, then the integer
part of our approximation will be correct for all months apart from
Jan and Feb - months 1 and 2. However, if we extend our table and
replace months 1 and 2 by 13 and 14 then our formula is exact for
all months. Therefore, given that if $M$ is 1 or 2, it is replaced
by 13 or 14 and $Y_L$ is decreased by 1, the month part of the
algorithm is given by $[2.6M-4.39]$
So the number of days between 1 Jan 1989 and 1 Sep 1989 is
$[2.6\times 9 - 4.39] = [19.01] = 19 \equiv5$.
Putting everything together
The final step is to calculate the sum of our individual parts. If
we work backwards it turns out that 1 Jan 0 AD was a Monday, so we
tweak our formula and subtract 1 from our sum to ensure that 0 is
Sunday instead. Our final formula, then, is $$D + [2.6M-4.38] +
\Big( Y_L - 2Y_F+ \Big[ \frac{Y_L}{4} \Big] + \Big[ \frac{Y_F}{4}
\Big] \Big) - 1 = D + Y_L -2Y_F + [2.6M-5.39] + \Big[ \frac{Y_L}{4}
\Big] + \Big[ \frac{Y_F}{4} \Big]$$ For 23 Sep 1989 we get 23 + 5 +
0 - 1 = 27 = 6 mod 7. So 23 Sep 1989 was a Saturday.