Challenge Level

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.