Part 2 of Algorithms explained! Every few weeks I write about an algorithm and explain and implement it!
Is there an algorithm you always wanted to know about? Leave a comment!

Today: The Doomsday rule - or: figuring out if November 24th 1763 was a Tuesday

John Conway is most famously known for "Conway's Game Of Life" - but he published a whole lot more. One especially remarkable algorithm he developed around 1970 is the Doomsday rule.

The name may sound a little odd, but the algorithm is amazing: It allows you to calculate the day of the week for any given date in your head.

In this post I will explain how this algorithm works and do a practical example in PHP.

What's a Doomsday, though?

The "Doomsday" of the "Doomsday rule" is not about the end of the world. Every year has so called Doomsdays. A Doomsday is a day whose weekday is known. For every year the Doomsdays have the same weekday.

For example: If you know that the November 7th (a Doomsday) was a Saturday - which weekday is November 21st? You know that there's 14 days in between and you know that a week has 7 days - so it's $14 / 7 = 2.0$ , so 2 whole weeks. November 21st must therefore be a Saturday as well.

To make calculations easier, each month has a fixed Doomsday. This table helps to memorize them. There's also some memory hooks, like "I work 9-to-5 at 7-11".

Let's have a look at a calendar:

And indeed: All these dates have the same weekday. Actually, all dates that have the same weekday can be considered Doomsdays.

The algorithm

The Doomsday rule takes advantage of the fact that patterns in calendars repeat every so often. Here's a basic diagram of what the algorithm is actually doing:

It basically narrows down the weekday by first looking at the century given, then the year, then the month and finally pinponting the exact date. Let's go through it step-by-step. We'll try to figure out the weekday of November 24th, 1763 (I'll explain why I chose this particular date later on).

Figuring out the weekday of the Doomsdays

To figure out the weekday of the Doomsdays of a given year (the so called "Anchor day"), we need to know the so called "Century Anchor day" first. This is the Anchor day of the first year of a given century. Those repeat in a 400 year cycle:

If we calculate that back to the year 0, we get a Tuesday. This we can use to calculate the Anchor day for any century. First, let's label the weekdays, starting from Sunday:

$weekdays = [
    0 => 'Sunday',
    1 => 'Monday',
    2 => 'Tuesday',
    3 => 'Wednesday',
    4 => 'Thursday',
    5 => 'Friday',
    6 => 'Saturday',
];

Then, take the century (so essentially $floor(year / 100)$ ) $mod 4$ (to get into the 4 century cycle) and multiply that by 2. Next we take the Tuesday of year 0 into account by subtracting the 4 century cycle number from it (i.e. $2 - (Century$ ) Since this often gives negative results, we use 9 (Tuesday + 1 week) instead and take the result $mod 7$ to get rid of that extra week.

(By the way: We're going to use a lot of % today.)

Let's see if this works:

The 4 century cycle works because every 400 years, calendars basically repeat. For every year of a century, the Doomsday weekday can be calculated from the century it is in.

Let's code this out:

/**
 * Determines the anchor day a century.
 *
 * @param int $yyyy Year, 1-4 digits
 * @return int Anchor day number
 */
function getCenturyAnchorday(int $yyyy): int {
    return (9 - (floor($yyyy / 100) % 4) * 2) % 7;
}

So the Century anchor day for November 24th 1763 is (9 - (floor(1763 / 100) % 4) * 2) % 7 which is 0, so Sunday.

From century to year

With the Century Anchor day ready, we can calculate the Anchor day for the year itself. We first need the last two digits of the year: $year % 100. The weekdays for the Year Anchor days are basically increasing, so Tue, Wed, Thu, Fri, Sat, Sun, Mon, Tue, except for leap years, where a day is skipped (since there's a day more).

Let's make an example with the first few years of the 17th century (1600 onwards):

This result can be achieved by taking the year, adding the number of leap years since the century started (i.e. the number of additional days to count in) and adding the Century Anchor day. This result mod 7 is then the Year Anchor day. This is what the code looks like:

/**
 * Determines the year's anchor day.
 *
 * @param int $yyyy Year, 1-4 digits
 * @return int Year anchor day
 */
function getYearAnchorDay(int $yyyy): int {
    $centuryAnchorday = getCenturyAnchorday($yyyy);
    $yy = $yyyy % 100; // Year, 1-2 digits

    return ($yy + floor($yy / 4) + $centuryAnchorday) % 7;
}

Since we know that the Century Anchor day of November 24th 1763 is 0, we can calculate the Year Anchor day: (63 + floor(63 / 4) + 0) % 7 which is 1, so Monday.

Marvelous! We can now determine the weekday of the Doomsdays of any given year! Next up is pinpointing the actual day by finding the next best Doomsday. With our Doomsday table above we can make this a simple mapping:

/**
 * Determines if a given year is a leap year.
 *
 * @param int $year
 * @return bool
 */
function isLeapYear(int $year): bool {
    return $year % 4 === 0 && ($year % 100 !== 0 || $year % 400 === 0);
}

/**
 * Determines the Doomsday of a given month.
 *
 * @param int $yyyy Year, 1-4 digits
 * @param int $m Month, 1-2 digits
 * @return int
 */
function getNearestDoomsday(int $yyyy, int $m): int {
    $isLeapYear = isLeapYear($yyyy);
    return [
        1 => !$isLeapYear ? 3 : 4,
        2 => !$isLeapYear ? 28 : 29,
        3 => 0,
        4 => 4,
        5 => 9,
        6 => 6,
        7 => 11,
        8 => 8,
        9 => 5,
        10 => 10,
        11 => 7,
        12 => 12,
    ][$m];
}

1763 is not a leap year, and we're looking at November anyways, so the next best Doomsday is November 7th.

Almost there!

Now we need to count the number of days from the actual date we're looking for to the next best anchor day. We calculate the difference between the date of the nearest Doomsday and the date we're looking for, add the Year Anchor day, add another 35 ( $7*5$ , to avoid any negative numbers) and take the result mod 7. This gives us the final weekday number!

For example, if the next best Doomsday is November 7th, and we're looking for November 24th, the calculation looks like this. We know that the Year Anchor day is a Monday, so 1. We also know the nearest Doomsday, which is November 7th:

And in code:

/**
 * Determines the weekday of a given date.
 *
 * @param int $yyyy Year, 1-4 digits
 * @param int $m Month, 1-2 digits
 * @param int $d Day, 1-2 digits
 * @return int Number of the weekday, 0 = Sun, 6 = Sat
 */
function getWeekday(int $yyyy, int $m, int $d): int {
    $doomsday = getNearestDoomsday($yyyy, $m);
    $yearAnchorDay = getYearAnchorDay($yyyy);

    return ($yearAnchorDay + ($d - $doomsday) + 35) % 7;
}

And now we can calculate the weekday for November 24th 1763:

$weekdays[getWeekday(1763, 11, 24)]; // "Thursday"

So, no, November 24th 1763 is not actually a Tuesday, but a Thursday. Let's write a test for that:

$result = true;
for ($i = 0; $i < 1000; $i++) {
    $yyyy = mt_rand(100, 9999); // PHP's mktime will make a wraparound with any smaller years.
    $m = mt_rand(1, 12);
    $d = mt_rand(1, 27);

    $result = $result && $weekdays[getWeekday($yyyy, $m, $d)] === date('l', mktime(0, 0, 0, $m, $d, $yyyy));
}

var_dump($result); // true

So PHP gives the same results as our implementation of the Doomsday rule. Here's a PHPSandbox with the entire code!

Takeaway thoughts

When I first heard about the Doomsday rule, I was baffled. It took me quite some time (and calculating) to understand it, but once I got it, I was amazed by its cleverness. The algorithm isn't too costly either, because it only uses algebra.

With some more memory hooks (especially memorizing Doomsdays and anchor days for several years) one can calculate any weekday in their head. Kind of a neat party trick, actually: "Give me any date, I'll tell you its weekday."

Oh, and about November 24th 1763: That's the date when Bayes' Theorem was first announced.

I write tech articles in my free time. If you enjoyed reading this post, consider buying me a coffee!