DEV Community

Cover image for Algorithm explained: The Doomsday rule
Pascal Thormeier
Pascal Thormeier

Posted on • Updated on

Algorithm explained: The Doomsday rule

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.014 / 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".

Month Date of Doomsday Memory hook
January 3rd (4th in leap years) 3 years 3, 4 in 4
February 28th (29th in leap years) Last day of Feb
March 0th (yes.) Division by 0
April 4th 4/4
May 9th "... 9 to 5 ..."
June 6th 6/6
July 11th "... at 7-11"
August 8th 8/8
September 5th "... 9 to 5 ..."
October 10th 10/10
November 7th "... at 7-11"
December 12th 12/12

Let's have a look at a calendar:

Calendar with all Doomsdays marked in blue

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:

The Doomsday rule as a diagram.

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:

Year Anchor day
1400 Friday
1500 Wednesday
1600 Tuesday
1700 Sunday
1800 Friday
1900 Wednesday
2000 Tuesday
2100 Sunday
2200 Friday
2300 Wednesday
2400 Tuesday

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',
];
Enter fullscreen mode Exit fullscreen mode

Then, take the century (so essentially floor(year/100)floor(year / 100) ) mod4mod 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(Century2 - (Century % 4) * 2 ) Since this often gives negative results, we use 9 (Tuesday + 1 week) instead and take the result mod7mod 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:

Century Target Anchor day mod 4 * 2 9 - % 7
0 Tue / 2 0 0 9 2
1 Sun / 0 1 2 7 0
2 Fri / 5 2 4 5 5
3 Wed / 3 3 6 3 3
4 Tue / 2 0 0 9 2
5 Sun / 0 1 2 7 0
6 Fri / 5 2 4 5 5
7 Wed / 3 3 6 3 3
8 Tue / 2 0 2 9 2
9 Sun / 0 1 4 7 0

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;
}
Enter fullscreen mode Exit fullscreen mode

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):

Year Anchor day
1600 (leap) Tuesday
1601 Wednesday
1602 Thursday
1603 Friday
1604 (leap) Sunday
1605 Monday
1606 Tuesday
1607 Wednesday
1608 (leap) Friday
1609 Saturday
1610 Sunday
1611 Monday
1612 (leap) Wednesday
1613 Thursday
1614 Friday
1615 Saturday

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;
}
Enter fullscreen mode Exit fullscreen mode

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];
}
Enter fullscreen mode Exit fullscreen mode

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 ( 757*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:

What Value Result
Date 24 24
- Doomsday - 7 17
+ Year anchor day + 1 18
+ Offset + 35 53
Figure out weekday % 7 4

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;
}
Enter fullscreen mode Exit fullscreen mode

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

$weekdays[getWeekday(1763, 11, 24)]; // "Thursday"
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!

Buy me a coffee button

Discussion (0)