Project Nayuki


Zeller’s congruence

Given an arbitrary date (y, m, d) on the standard Gregorian calendar, how do we calculate its day-of-week k? Zeller’s congruence solves this problem efficiently; it is a mathematical formula that is relatively short, avoids conditionals and look-up tables, and runs in constant time. This page explains step by step how the algorithm works, and provides runnable library code and tests.

Gregorian calendar rules

Calendar day

Each calendar day (abbreviated as just day) starts at midnight and runs for 24 hours continuously until just before the next midnight. For example, the time interval [2000-12-31 00:00:00, 2001-01-01 00:00:00) is a day. A day is an abstract concept and can be labelled in various formats. We ignore leap seconds for simplicity. We also ignore time zones and edge cases like a day having 23 or 25 hours. Note that other calendar systems may define the start of days at another time like noon.

Day-of-week

A week is any 7 consecutive days, and the day-of-week is a value drawn from a set of 7 labels. We will use the convention that 0 = Sunday, 1 = Monday, 2 = Tuesday, 3 = Wednesday, 4 = Thursday, 5 = Friday, 6 = Saturday. This matches the behavior of java.util.Date and JavaScript’s Date.

Each calendar day maps to a day-of-week (many-to-one relation). Consecutive days map to consecutive days-of-week modulo 7. For example, is a Saturday (6), is a Sunday (0), and is a Monday (1).

Linear date

A linear date system defines an epoch day, then labels each calendar day as the signed integer denoting the number of days after the epoch. For example, if the epoch is on the Gregorian calendar, then on the Gregorian calendar would in this linear date system be day 4 (i.e. epoch + 4).

Calculating the day-of-week is really easy in a linear date system: If the linear date is d and the epoch’s day-of-week is k0, then d’s day-of-week is given by k = (k0 + d) mod 7.

A consequence of this is that Unix time, a linear time scale, allows for easy day-of-week calculations. With a Unix timestamp t given in seconds and the fact that is a Thursday (4), that timestamp’s UTC day-of-week is given by (⌊t / 86400⌋ + 4) mod 7.

Calendar date

A (Gregorian) calendar date is a triple of integers (y, m, d). A lenient date has no restrictions on the range of each integer, whereas a strict date restricts m to [1, 12] and d to [1, monthLength(y, m)].

Proleptic calendar

Although the Gregorian calendar was first used on and might be disused someday, we will make the simplifying assumption that the calendar rules extend infinitely into the past and future.

Note that before that day, the Julian calendar was used; it had the same (y, m, d) format and almost identical rules except for leap years. This means that dates recorded in the Julian calendar cannot be reinterpreted verbatim in the Gregorian calendar; some math is needed to convert between the two calendar systems.

Year

In the (proleptic) Gregorian calendar, the year (y) can be any integer. Positive numbers denote AD/CE years. Year 0 is interpreted as 1 BC/BCE, because we normally don’t recognize 0 as a year number. Year −1 is interpreted as 2 BC/BCE, and so on.

Leap year

Leapness is a Boolean property of each year. Every year that is a multiple of 400 is a leap year. Otherwise if it’s a multiple of 100, it’s not a leap year. Otherwise if it’s a multiple of 4, it’s a leap year. Otherwise it’s not a leap year. We can see that this pattern repeats every 400 years. Straightforward Python code:

def is_leap_year(y):
	if y % 400 == 0:
		return True
	elif y % 100 == 0:
		return False
	elif y % 4 == 0:
		return True
	else:
		return False

Simplified Python code:

def is_leap_year(y):
	return (y % 4 == 0) and \
		((y % 100 != 0) or (y % 400 == 0))
Month

In strict mode, the month (m) is an integer between 1 and 12, inclusive. In English, the months are named 1 = January, 2 = February, ..., 11 = November, 12 = December. For every year, month 1 is the earliest and month 12 is the latest.

In lenient mode, months outside the range [1, 12] are reduced to strict months in a logical way. For example, 2000-13 (lenient, the month after year , month 12) reduces to (strict, year , month 01). For example, 1997-(−03) (lenient, 4 months before year , month 01) reduces to (strict, year , month 09).

Month length

The length of a month is the number of (strict) days it contains. For a strict month m: If m ∈ {1, 3, 5, 7, 8, 10, 12}, the month length is 31. Otherwise if m ∈ {4, 6, 9, 11}, the month length is 30. Otherwise m = 2: If y is a leap year then the month length is 29; otherwise y is not a leap year and the month length is 28. Straightforward Python code:

def month_length(y, m):
	if m in {1, 3, 5, 7, 8, 10, 12}:
		return 31
	elif m in {4, 6, 9, 11}:
		return 30
	elif m == 2:
		if is_leap_year(y):
			return 29
		else:
			return 28

Simplified Python code:

MONTH_LENGTHS = [None, 31, None, 31,
	30, 31, 30, 31, 31, 30, 31, 30, 31]

def month_length(y, m):
	if m != 2:
		return MONTH_LENGTHS[m]
	else:
		return 29 if is_leap_year(y) else 28
Year length

By adding up the twelve month-lengths, we can deduce that a non-leap year has 365 days and a leap year has 366 days.

Day-of-month

In strict mode, the day-of-month (d) is an integer in the range [1, monthLength(y, m)]. For every month, day-of-month 1 is the earliest and monthLength(y, m) is the latest.

In lenient mode, days-of-month outside that range are reduced to strict days-of-months in a logical way. For example, 2005-06-32 (lenient, 2 days after ) reduces to (strict). For example, 1984-11-00 (lenient, 1 day before ) reduces to (strict).

Next date

When enumerating successive (strict) dates, the day-of-month increments until it reaches the upper bound for that particular year and month. When the day-of-month reaches the maximum value, it resets to 1 and the month is incremented; if the month is already 12, then the month resets to 1 and the year is incremented. Python code:

def next_date(y, m, d):
	if d < month_length(y, m):
		return (y, m, d + 1)
	elif m < 12:
		return (y, m + 1, 1)
	else:
		return (y + 1, 1, 1)
Previous date

To compute the previous (strict) date: If the day-of-month is not 1, then simply decrement it. Otherwise if the month is not 1, then decrement it and set the day-of-month to the last day of that new month. Otherwise decrement the year, set the month to 12, and set the day-of-month to 31. Python code:

def previous_date(y, m, d):
	if d > 1:
		return (y, m, d - 1)
	elif m > 1:
		return (y, m - 1, month_length(y, m - 1))
	else:
		return (y - 1, 12, 31)
Periodic centuries

The pattern of leap years repeats every 400 years. In other words, the year y is a leap year if and only if the year y + 400 is a leap year. This also means that the number of days in any consecutive 400 years must be a constant; that block of years has 365×400 normal days and 97 leap days, for a total of 146097 days. This count is a multiple of 7, so there is a whole number of 7-day weeks in any 400 consecutive years. Therefore, any pair of months which are exactly 400 years apart will start on the same day-of-week and have the same number of days.

Anchor day

The day whose label is (year , January 1st) on the Gregorian calendar is a Saturday (6). This fact plus the rules on the length of each month, is sufficient to determine the day-of-week of every calendar date. It doesn’t matter which day we use as an anchor for the day-of-week calculation as long as at least one anchor is specified and it doesn’t contradict other anchors.

Naive day-of-week algorithm

Given a Gregorian calendar strict date (y, m, d), there is a conceptually simple way to figure out its day-of-week: We start on a date with a known day-of-week, then repeatedly step forward or backward one day at a time while also stepping the day-of-week. The running time is proportional to (linear in) the absolute number of days between the epoch and the target date, making it potentially very slow. Python code:

def day_of_week_naive(y, m, d):
	ymd = (1600, 1, 1)
	dow = 6
	while ymd < (y, m, d):
		ymd = next_date(*ymd)
		dow = (dow + 1) % 7
	while ymd > (y, m, d):
		ymd = previous_date(*ymd)
		dow = (dow - 1) % 7
	return dow

(Because of the 400-year periodicity property, if we change the initial ymd value to (2000, 01, 01), then the initial dow value of 6 would still be correct.)

Efficient day-of-week algorithm by Christian Zeller

Python code
def day_of_week(y, m, d):
	m -= 3
	y += m // 12
	m %= 12
	temp = y + y // 4 - y // 100 + y // 400
	return (temp + (m * 13 + 12) // 5 + d) % 7

This implementation’s code may differ from other versions of Zeller’s congruence, but that doesn’t make it wrong. Some subexpressions and numeric constants will change depending on how years and months are reduced and how the days-of-week are numbered.

The function above can be decomposed into this broad form, where py means pseudoyear and pm means pseudomonth:

def day_of_week(y, m, d):
	py, pm = reduce(y, m)
	return (f(py) + g(pm) + d + offset) % 7

So after the reduction function, the calculation is just a sum of four integer terms modulo 7. We will derive every subexpression/subfunction in order to understand how they work.

Optional 400-year reduction

Although Python operates on bigint by default, many other programming languages use fixed-range number types. To reduce the value ranges of variables and intermediate expressions, especially when operating on lenient dates, we can perform some reductions at the start. This code is justified because the days-of-week repeat every 400 years or 4800 months:

y %= 400
m %= 4800
Reduction to pseudoyear and pseudomonth

Probably nobody in daily life thinks that adding a leap day at the end of February is a problem, but for calculation purposes it is inconvenient. Let’s restructure how years and months work:

  • Pseudomonths (m′) are numbered as 0 = March, 1 = April, ..., 9 = December, 10 = January, 11 = February. By design, we have m′ + 3 ≡ m mod 12, effectively rotating the months by a few places so that March corresponds to 0.

  • Each pseudoyear (y′) begins in March (pseudomonth 0). Hence, any possible leap day is always at the end of a pseudoyear.

  • If the real month is at least 3, then the pseudoyear equals the real year; otherwise the pseudoyear is the real year minus 1. So if m < 3 then (y′, m′) = (y − 1, m + 9); otherwise (y′, m′) = (y, m − 3).

Despite how complicated the rules above might seem, the calculation is mathematically elegant and branchless:

pm = m - 3
py = y + pm // 12
pm %= 12

We’ll focus on strict dates (which is a subset of lenient dates), where m ∈ [1, 12]. If m ∈ [1, 2], then (m − 3) ∈ [−2, −1], ⌊(m − 3) / 12⌋ = −1, y′ = y − 1, and m′ = (m − 3) mod 12 so m′ ∈ [10, 11]. Otherwise m ∈ [3, 12], then (m − 3) ∈ [0, 9], ⌊(m − 3) / 12⌋ = 0, y′ = y, and m′ = (m − 3) mod 12 so m′ ∈ [0, 9].

You can do the extra work to convince yourself that the code is correct for lenient dates, even when the real month is outside the range [1, 12] – the pseudomonth will always be in the range [0, 12), and the pseudoyear will be adjusted appropriately.

Trivia: For many centuries, each year did in fact begin in March. We see relics of this in the number prefixes encoded in the following month names: 09 Septem(7)-ber, 10 Octo(8)-ber, 11 Novem(9)-ber, 12 Decem(10)-ber.

Fusion of reductions

If we perform the optional 400-year reduction followed by the pseudoyear-pseudomonth reduction, then we would have y′ ∈ [−1, 798]. But we can do better by fusing both calculations together:

pm = (m - 3) % 4800
py = y % 400 + pm // 12
pm %= 12

What this achieves is that y′ = −1 becomes y′ = 399, so now y′ ∈ [0, 798], and we won’t have to worry about flooring vs. truncating division later on.

Handling the pseudoyear

We shall define the function f(y′) as the signed number of days from the start of pseudoyear 0 to the start of pseudoyear y′. This function will be a summation of integer terms.

Every pseudoyear (or real year) has either 365 or 366 days. Our first summation term is 365y′, and then later terms will account for cumulative leap days.

Noting that 365 = 52×7 + 1, every non-leap year has 52 seven-day weeks and 1 extra day. If we pretend that every year is non-leap, looking at any particular date (y, m, d) with day-of-week k, then the corresponding day next year is (y+1, m, d) and has day-of-week (k + 1) mod 7. This also means that our first term can simplify from 365y′ to just y′ if we take f(y′) modulo 7. Illustration:

Sun (0) Mon (1) Tue (2) Wed (3) Thu (4) Fri (5) Sat (6)
Year 0
Jan 01
Year 0
Jan 02
Year 0
Jan 03
Year 0
Jan 04
Year 0
Jan 05
Year 0
Jan 06
Year 0
Jan 07
... 50 weeks of Year 0 omitted...
Year 0
Dec 24
Year 0
Dec 25
Year 0
Dec 26
Year 0
Dec 27
Year 0
Dec 28
Year 0
Dec 29
Year 0
Dec 30
Year 0
Dec 31
Year 1
Jan 01
Year 1
Jan 02
Year 1
Jan 03
Year 1
Jan 04
Year 1
Jan 05
Year 1
Jan 06
... 50 weeks of Year 1 omitted...
Year 1
Dec 23
Year 1
Dec 24
Year 1
Dec 25
Year 1
Dec 26
Year 1
Dec 27
Year 1
Dec 28
Year 1
Dec 29
Year 1
Dec 30
Year 1
Dec 31
Year 2
Jan 01
Year 2
Jan 02
Year 2
Jan 03
Year 2
Jan 04
Year 2
Jan 05

Next, we will handle leap years gradually. First, we’ll assume that a real year is leap if and only if it’s a multiple of 4, ignoring the rules about multiples of 100 and 400. This would actually mean that a pseudoyear is leap if and only if it’s one less than a multiple of 4 (i.e. −1 mod 4). Illustration of months, with the start of years/pseudoyears highlighted:

Real Pseudo
Year Month Year Month
199901 January199810 January
199902 February199811 February
199903 March199900 March
199904 April199901 April
199905 May199902 May
199906 June199903 June
199907 July199904 July
199908 August199905 August
199909 September199906 September
199910 October199907 October
199911 November199908 November
199912 December199909 December
200001 January199910 January
200002 February (leap)199911 February (leap)
200003 March200000 March
200004 April200001 April
200005 May200002 May
200006 June200003 June
200007 July200004 July
200008 August200005 August
200009 September200006 September
200010 October200007 October
200011 November200008 November
200012 December200009 December
200101 January200010 January
200102 February200011 February
200103 March200100 March
200104 April200101 April
200105 May200102 May
200106 June200103 June
200107 July200104 July
200108 August200105 August
200109 September200106 September
200110 October200107 October
200111 November200108 November
200112 December200109 December
... many months omitted ...
200401 January200310 January
200402 February (leap)200311 February (leap)
200403 March200400 March

While it might seem strange that leap pseudoyears are not multiples of 4, this actually makes things easier. For illustration, we can see that the number of leap days from the start of pseudoyear 2000 to the start of pseudoyear... 2000 is 0, 2001 is 0, 2002 is 0, 2003 is 0, 2004 is 1, 2005 is 1, 2006 is 1, 2007 is 1, 2008 is 2, etc. The exact number of leap days from the start of pseudoyear 2000 to the start of pseudoyear y′ is ⌊(y′ − 2000) / 4⌋. Due to the 400-year periodic equivalence, the number of leap days from the start of pseudoyear 0 to pseudoyear y′ is ⌊y′ / 4⌋, hence giving us the second summation term.

To improve our approximation, every real year that is a multiple of 100 is not a leap year (overriding the multiple-of-4 rule), so every pseudoyear that is one less than a multiple of 100 (i.e. −1 mod 100) is not leap. This means pseudoyears −101, −1, 99, 199, 299, 399, 499, etc. are not leap. For example, from the start of pseudoyear 0 to the start of pseudoyear 100, we accumulate exactly 1 anti-leap day which is at the end of pseudoyear 99. We implement this compensation with our third summation term of −⌊y′ / 100⌋.

Finally, to match the Gregorian leap year rules exactly, we need every real year that is a multiple of 400 to be a leap year (overriding the multiple-of-100 rule), so every pseudoyear that is one less than a multiple of 400 (i.e. −1 mod 400) is leap. This means pseudoyears −401, −1, 399, 799, etc. are leap. For example, from the start of pseudoyear 0 to the start of pseudoyear 400, we accumulate exactly 1 anti-anti-leap day which is at the end of pseudoyear 399. We implement this compensation with our fourth summation term of ⌊y′ / 400⌋.

Altogether, we have: f(y′) = 365y′ + ⌊y′ / 4⌋ − ⌊y′ / 100⌋ + ⌊y′ / 400⌋. Python code:

def f(py):
	return 365 * py + py // 4 \
		- py // 100 + py // 400
Handling the pseudomonth

We shall define the function g(m′) as any number that is congruent modulo 7 to the number of days from the start of pseudomonth 0 to the start of strict pseudomonth m′, where 0 ≤ m′ ≤ 11.

Consider how many days there are from the start of pseudomonth 0 (which is the start of the pseudoyear) to the start of pseudomonth m′. We know that for m′ = 0, the answer is 0 because no months have passed. For m′ = 1, the answer is 31 because March has 31 days. For m′ = 2, the answer is 61 because it adds April which has 30 days. And so on and so forth until m′ = 11, where the answer is 337.

Note that we never need to calculate or add the length of pseudomonth 11 (February), so this calculation is independent of the pseudoyear. This is why we arranged things so that potential leap days are at the end of pseudomonth 11, which in turn is at the end of the pseudoyear.

Pseudomonth Number of days Cumulative days before
00 March310
01 April3031
02 April3161
03 June3092
04 July31122
05 August31153
06 September30184
07 October31214
08 November30245
09 December31275
10 January31306
11 February28 or 29337

There seems to be an exploitable pattern: Starting from pseudomonth 0, the number of days per month almost perfectly repeats every 5 months. Because we are only interested in the cumulative number of days since pseudomonth 0, we can indeed assume the 5-month periodicity because we never need to add the length of pseudomonth 11. How do we find a formula that periodically increments by the sequence [31, 30, 31, 30, 31]? Well, the average increment is 153/5, so we can try the formula ⌊153m′ / 5⌋:

Pseudomonth (m′) Cumul days Increment ⌊153m′ / 5⌋ Increment
000N/A0N/A
0131313030
0261306131
0392319130
041223012231
051533115331
061843118330
072143021431
082453124430
092753027531
103063130631
113373133630

The values generated by ⌊153m′ / 5⌋ are almost correct, as is the sequence of increments created by subtracting adjacent values. If we add 4 to the pseudomonth, this will rotate the sequence of increments to make them correct, and then we subtract 122 from the result to compensate:

Pseudomonth (m′) Cumul days Increment ⌊153(m′ + 4) / 5⌋ − 122 Increment
000N/A0N/A
0131313131
0261306130
0392319231
041223012230
051533115331
061843118431
072143021430
082453124531
092753027530
103063130631
113373133731

Going back to the function’s definition, we only care about the cumulative pseudomonth days modulo 7. The additive term −122 simplifies to +4. The multiplicative term 153 simplifies to 13 because the division by 5 means that we need to take 153 modulo 7×5. Hence, we have ⌊153(m′ + 4) / 5⌋ − 122 ≡ ⌊13(m′ + 4) / 5⌋ + 4 mod 7:

Pseudomonth (m′) Cumul days mod 7 (⌊153(m′ + 4) / 5⌋ − 122) mod 7 (⌊13(m′ + 4) / 5⌋ + 4) mod 7
00000
01333
02555
03111
04333
05666
06222
07444
08000
09222
10555
11111

We can manipulate this formula further:
⌊13(m′ + 4) / 5⌋ + 4
= ⌊(13m′ + 13×4) / 5⌋ + 4
= ⌊(13m′ + 52) / 5⌋ + 4
= ⌊(13m′ + 2 + 50) / 5⌋ + 4
= ⌊(13m′ + 2) / 5 + 50/5⌋ + 4
= ⌊(13m′ + 2) / 5 + 10⌋ + 4
= ⌊(13m′ + 2) / 5⌋ + 10 + 4
≡ ⌊(13m′ + 2) / 5⌋
mod 7.

Altogether, we have: g(m′) = ⌊(13m′ + 2) / 5⌋. Python code:

def g(pm):
	return (13 * pm + 2) // 5
Handling the day-of-month

Including the day-of-month is easy because it is already a linear day format – so we simply add it to the grand sum. We don’t need any special handling for lenient dates.

Handling the offset

The three terms of the grand sum so far imply that the pseudo-date (y′, m′, d) = (0, 0, 0) has day-of-week of 0, because 0 days have elapsed from pseudoyear 0 to pseudoyear 0, 0 days have elapsed from pseudomonth 0 to pseudomonth 0, and 0 days have elapsed from day-of-month 0 to day-of-month 0. This date actually corresponds to lenient real date (y, m, d) = (0, 3, 0), which has the same day-of-week as 2000-03-00, which is one day before (Wednesday). Therefore, the offset term in the grand sum is 2.

Final formulas

From some sections above, we translate some prose/code and copy some formulas:

y′ = y + ⌊(m − 3) / 12⌋.
m′ = (m − 3) mod 12.
f(y′) = 365y′ + ⌊y′ / 4⌋ − ⌊y′ / 100⌋ + ⌊y′ / 400⌋.
g(m′) = ⌊(13m′ + 2) / 5⌋.

Substitute the subfunctions into the grand sum, simplify 365 modulo 7, then fuse the offset of 2 into the g(m′) expression:

k = [f(y′) + g(m′) + d + 2]
= [(365y′ + ⌊y′ / 4⌋ − ⌊y′ / 100⌋ + ⌊y′ / 400⌋) + ⌊(13m′ + 2) / 5⌋ + d + 2]
≡ [y′ + ⌊y′ / 4⌋ − ⌊y′ / 100⌋ + ⌊y′ / 400⌋ + ⌊(13m′ + 2) / 5 + 2⌋ + d]
= [y′ + ⌊y′ / 4⌋ − ⌊y′ / 100⌋ + ⌊y′ / 400⌋ + ⌊(13m′ + 2) / 5 + 10/5⌋ + d]
= [y′ + ⌊y′ / 4⌋ − ⌊y′ / 100⌋ + ⌊y′ / 400⌋ + ⌊(13m′ + 2 + 10) / 5⌋ + d]
= [y′ + ⌊y′ / 4⌋ − ⌊y′ / 100⌋ + ⌊y′ / 400⌋ + ⌊(13m′ + 12) / 5⌋ + d] mod 7.

Source code

Note: All the code in the explanations above use the Python programming language, where its % operator is the true modulo; for example, x % 7 always yields an answer in the range [0, 6]. But in programming languages like C/C++/Java/JavaScript, the % operator is remainder, so x % 7 yields an answer in the range [−6, 6]. Likewise, the // operator in Python is flooring division, whereas / in many languages is truncating division. Both pairs of operators behave equally when the left-hand argument is non-negative but differently when it’s negative; take care when translating Python code to other languages.

More info