Doomsday Algorithm

Suppose we wish to determine the day of the week for a given date, say, June 16, 1904. We can, of course, search for the day of the week using Google, but we don’t need Google! We can use the Doomsday Algorithm. The Doomsday Algorithm, devised by the English mathematician John Conway, is a method to determine the day of the week for a given date, and in this post we’ll learn how to determine that June 16, 1904 was a Thursday.

Gregorian Calendar

The Gregorian calendar was introduced by Pope Gregory XIII in October 1582, supplanting the Julian calendar, and that year Thursday, October 4, 1582 was followed by Friday, October 15, 1582. So, why switch calendars? Well, the motivation was the solar year, or the time it takes the Earth to orbit the Sun, which can be measured between successive spring or autumn equinoxes, or summer or winter solstices. The Julian calendar assumed the average solar year had 365.25 days, hence a normal year had 365 days, and a leap year had 366 days, with no exceptions; however, an actual solar year, though it varies, has roughly 365.24219 days, meaning the Julian calendar gained a day every 128 years:

Thus, to prevent the drift of the calendar, the Gregorian system implements leap years for years divisible by four, except for years divisible by 100, unless those years divisible by 100 are also divisible by 400. For example, 1700, 1800, and 1900 are not leap years, but 2000 is a leap year. As a result, the average calendar year over a 400-year period is shortened by 0.0075 days, becoming 365.2425 days (a value closer to the actual length of a solar year):

Modular Arithmetic

With modular arithmetic, we impose a structure on the integers (…, -2, -1, 0, 1, 2, …) such that we identify a number with the remainder after dividing said number by the modulus, the defining divisor. For example, a 12-hour clock uses integers modulo 12, where 12 is the modulus, and we identify 8 o’clock with 20 o’clock (8 \(\equiv\) 20 mod(12)), since dividing 20 by 12 results in a remainder of 8. We say 8 and 20 are congruent, or equivalent, modulo 12. Further, there are 12 congruence classes, or sets of congruent numbers, since the structure cycles according to the modulus 12. Such a congruence class is \({0 + 12(n): n \in \mathbb{Z}}\), where \(\mathbb{Z}\) is the set of integers, so we have 0, -12, 12, -24, 24, and so on, in the same congruence class.

Here, we consider integers modulo 7:

Since we have seven days in a week, we label the days as follows:

Thus, if today is Monday (1), in seven days, of course, we will return to Monday: \(1 + 7 = 8 \equiv 1 \ \text{mod(}7\text{)}\). Presto!

Further, we observe that a one-year period (without a leap year) results in a one-day offset:

whereas a 400-year period results in a zero-day offset, accounting for the Gregorian system of leap years:

Doomsday Algorithm

Now, having the background, we arrive at the Doomsday Algorithm.

First, in any given year, there are dates (we’ll call these doomsday dates) which fall on the same day of the week, and in a given year, said day of the week is called the doomsday. Really, we could choose other sets of dates, but there are easy-to-remember doomsday dates:

For example, in a given year, if the doomsday is Monday (with respect to our doomsday dates), every doomsday date above is a Monday, and knowing a one-year period (without a leap year) results in a one-day offset, the following year’s doomsday would be Tuesday.

Second, we establish the doomsday for each centurial year (e.g., 1500, 1600, 1700, etc.). Once we have the doomsday for each centurial year, we can use modular arithmetic to determine the doomsday for any year in a given century, from which we can determine the day of the week of a given date.

Now, I’m writing as of August 30, 2022, so the nearest doomsday date is August 29, 2022, which I know was a Monday. Thus, the doomsday for the year 2022 is Monday. Further, there have been 5 leap years since 2000, so we obtain the offset from 2000 to 2022:

where \(\lfloor x \rfloor\) (“floor of x”) is the greatest integer smaller than or equal to \(x\). We find the doomsday for 2000 is Tuesday, since Monday (1) + 1 is Tuesday (2). Repeating the process, noting that 2000 is a leap year, we obtain the offset from 1900 to 2000:

We find the doomsday for 1900 is Wednesday, since Tuesday (2) + 1 is Wednesday (3). Again, repeating the process, noting that 1900 is not a leap year, we obtain the offset from 1800 to 1900:

We find the doomsday for 1800 is Friday, since Wednesday (3) + 2 is Friday (5). We can repeat the process for the offset from 1700 to 1800, and we find the doomsday for 1700 is Sunday. Since the Gregorian calendar has a cycle of 400 years (as we saw there was a zero-day offset), we now have the doomsday for each centurial year:

Finally, here are the steps of the Doomsday Algorithm:

1. Given a date, consider the century, and determine the doomsday, X, for that century. For June 16, 1904, the doomsday for 1900 is Wednesday (X = 3).
2. Take the year of the given century, Y, and determine the doomsday for that year. For June 16, 1904 (Y = 4): \(X + Y + \lfloor \frac{Y}{4} \rfloor = 3 + 4 + 1 \equiv 1 \ \text{mod(}7\text{)}.\) Thus, the doomsday for 1904 is Monday (1).
3. Find the nearest doomsday date, and add/subtract to the given date. For June 16, 1904, 6/6 and 6/13 are doomsday dates, meaning June 13, 1904 was a Monday (1), so June 16, 1904 was a Thursday (4), since \(1 + (16 - 13) \equiv 4 \ \text{mod(}7\text{)}\).

Python Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
day_dictionary = {'0':'Sunday', 'Sunday':'0', '1':'Monday', 'Monday':'1',\
                  '2':'Tuesday', 'Tuesday':'2', '3':'Wednesday', 'Wednesday':'3',\
                  '4':'Thursday', 'Thursday':'4', '5':'Friday', 'Friday':'5',\
                  '6':'Saturday', 'Saturday':'6'}

ddates_normal = ['1/3', '1/10', '1/17', '1/24', '1/31', '2/7', '2/14', '2/21', '2/28',\
                  '3/7', '3/14', '3/21', '3/28', '4/4', '4/11', '4/18', '4/25', '5/2',\
                  '5/9', '5/16', '5/23', '5/30', '6/6', '6/13', '6/20', '6/27', '7/4',\
                  '7/11', '7/18', '7/25', '8/1', '8/8', '8/15', '8/22', '8/29', '9/5',\
                  '9/12', '9/19', '9/26', '10/3', '10/10', '10/17', '10/24', '10/31',\
                  '11/7', '11/14', '11/21', '11/28', '12/5', '12/12', '12/19', '12/26']
ddates_leap = ['1/4', '1/11', '1/18', '1/25', '2/1', '2/8', '2/15', '2/22', '2/29',\
                  '3/7', '3/14', '3/21', '3/28', '4/4', '4/11', '4/18', '4/25', '5/2',\
                  '5/9', '5/16', '5/23', '5/30', '6/6', '6/13', '6/20', '6/27', '7/4',\
                  '7/11', '7/18', '7/25', '8/1', '8/8', '8/15', '8/22', '8/29', '9/5',\
                  '9/12', '9/19', '9/26', '10/3', '10/10', '10/17', '10/24', '10/31',\
                  '11/7', '11/14', '11/21', '11/28', '12/5', '12/12', '12/19', '12/26']

def anchor(date):
    """The anchor function accepts a date as a string, 'M/D/YYYY', and returns the doomsday of the
    corresponding centurial year. For example, passing '10/5/1582' will return 'Wednesday',
    since the corresponding centurial year is '1500'."""
    
    date_list = date.split('/')
    century = date_list[2][0:2] + '00'
    
    if ((int(century) - 1500)%400 == 0):
        return 'Wednesday'
    elif ((int(century) - 1600)%400 == 0):
        return 'Tuesday'
    elif ((int(century) - 1700)%400 == 0):
        return 'Sunday'
    elif ((int(century) - 1800)%400 == 0):
        return 'Friday'
    
def is_leap(date):
    """The is_leap function accepts a date as a string, 'M/D/YYYY', and returns True/False if the year, 
    YYYY, is/is not, respectively, a leap year. For example, passing May 4, 1900 will return False."""
    
    date_list = date.split('/')
    year = date_list[2]
    
    # years not divisible by 4 #
    if (int(year)%4 != 0):
        return False
    
    # years divisible by 4, but not 100 #
    if ((int(year)%4 == 0) & (not (int(year)%100 == 0))):
        return True
    
    # years divisible by 4 and 100, but not 400 #
    if ((int(year)%4 == 0) & (int(year)%100 == 0) & (not (int(year)%400 == 0))):
        return False
    
    # years divisible by 4, 100, and 400 #
    if ((int(year)%4 == 0) & (int(year)%100 == 0) & (int(year)%400 == 0)):
        return True

def doomsday_algorithm(date):
    """The doomsday_algorithm function accepts a date as a string, 'M/D/YYYY', and returns the day of the week. 
    For example, passing '6/4/1904 will return 'Thursday'."""
    
    date_list = date.split('/')
    anchor_value = int(day_dictionary[anchor(date)])
    (month, day, year_of_century) = (date_list[0], date_list[1], date_list[2][2:4])
    
    # for a normal (non-leap) year #
    if (not is_leap(date)):
        
        year_doomsday = (anchor_value + (int(year_of_century) + (int(year_of_century)//4)))%7
        
        ddates_distance = []
        for elem in ddates_normal:
            compare = elem.split('/')
            if (compare[0] == month):
                ddates_distance.append(int(compare[1]) - int(day))        
        
        day_of_week = day_dictionary[str((year_doomsday - ddates_distance[0])%7)]
        print(year_doomsday, ddates_distance, day_of_week)
            
    
    # for a leap year #
    elif (is_leap(date)):
        
        year_doomsday = (anchor_value + (int(year_of_century) + (int(year_of_century)//4)))%7
        
        ddates_distance = []
        for elem in ddates_leap:
            compare = elem.split('/')
            if (compare[0] == month):
                ddates_distance.append(int(compare[1]) - int(day))        
        
        day_of_week = day_dictionary[str((year_doomsday - ddates_distance[0])%7)]
        print(year_doomsday, ddates_distance, day_of_week)