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’sDate
.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 andpm
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 01Year 0
Jan 02Year 0
Jan 03Year 0
Jan 04Year 0
Jan 05Year 0
Jan 06Year 0
Jan 07... 50 weeks of Year 0 omitted... Year 0
Dec 24Year 0
Dec 25Year 0
Dec 26Year 0
Dec 27Year 0
Dec 28Year 0
Dec 29Year 0
Dec 30Year 0
Dec 31Year 1
Jan 01Year 1
Jan 02Year 1
Jan 03Year 1
Jan 04Year 1
Jan 05Year 1
Jan 06... 50 weeks of Year 1 omitted... Year 1
Dec 23Year 1
Dec 24Year 1
Dec 25Year 1
Dec 26Year 1
Dec 27Year 1
Dec 28Year 1
Dec 29Year 1
Dec 30Year 1
Dec 31Year 2
Jan 01Year 2
Jan 02Year 2
Jan 03Year 2
Jan 04Year 2
Jan 05Next, 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 1999 01 January 1998 10 January 1999 02 February 1998 11 February 1999 03 March 1999 00 March 1999 04 April 1999 01 April 1999 05 May 1999 02 May 1999 06 June 1999 03 June 1999 07 July 1999 04 July 1999 08 August 1999 05 August 1999 09 September 1999 06 September 1999 10 October 1999 07 October 1999 11 November 1999 08 November 1999 12 December 1999 09 December 2000 01 January 1999 10 January 2000 02 February (leap) 1999 11 February (leap) 2000 03 March 2000 00 March 2000 04 April 2000 01 April 2000 05 May 2000 02 May 2000 06 June 2000 03 June 2000 07 July 2000 04 July 2000 08 August 2000 05 August 2000 09 September 2000 06 September 2000 10 October 2000 07 October 2000 11 November 2000 08 November 2000 12 December 2000 09 December 2001 01 January 2000 10 January 2001 02 February 2000 11 February 2001 03 March 2001 00 March 2001 04 April 2001 01 April 2001 05 May 2001 02 May 2001 06 June 2001 03 June 2001 07 July 2001 04 July 2001 08 August 2001 05 August 2001 09 September 2001 06 September 2001 10 October 2001 07 October 2001 11 November 2001 08 November 2001 12 December 2001 09 December ... many months omitted ... 2004 01 January 2003 10 January 2004 02 February (leap) 2003 11 February (leap) 2004 03 March 2004 00 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 March 31 0 01 April 30 31 02 April 31 61 03 June 30 92 04 July 31 122 05 August 31 153 06 September 30 184 07 October 31 214 08 November 30 245 09 December 31 275 10 January 31 306 11 February 28 or 29 337 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 00 0 N/A 0 N/A 01 31 31 30 30 02 61 30 61 31 03 92 31 91 30 04 122 30 122 31 05 153 31 153 31 06 184 31 183 30 07 214 30 214 31 08 245 31 244 30 09 275 30 275 31 10 306 31 306 31 11 337 31 336 30 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 00 0 N/A 0 N/A 01 31 31 31 31 02 61 30 61 30 03 92 31 92 31 04 122 30 122 30 05 153 31 153 31 06 184 31 184 31 07 214 30 214 30 08 245 31 245 31 09 275 30 275 30 10 306 31 306 31 11 337 31 337 31 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 00 0 0 0 01 3 3 3 02 5 5 5 03 1 1 1 04 3 3 3 05 6 6 6 06 2 2 2 07 4 4 4 08 0 0 0 09 2 2 2 10 5 5 5 11 1 1 1 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++/%
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.
- Python: zeller.py
- Java: Zeller.java
- C#: Zeller.cs
- TypeScript: zeller.ts
- Rust: zeller.rs
- C: zeller.c
- C++: zeller.cpp
- Haskell: zeller.hs
- Mathematica: zeller.mat.txt
- MATLAB: zeller.m