Detailed mathematical approach

Problem Summary

The candidates are the 1200 dates of the form \((y,m,1)\) with \(1901 \le y \le 2000\) and \(1 \le m \le 12\). We must count how many of those first-of-month dates are Sundays, assuming the Gregorian leap-year rule and the given anchor that 1900-01-01 was a Monday.

This makes the problem completely discrete: each month contributes exactly one candidate date, and the only arithmetic we need is how far that date lies from a known epoch.

Mathematical Approach

The implementations treat calendar arithmetic as modular counting. Once the number of elapsed days is known, the weekday is determined modulo \(7\).

Calendar State and Weekday Encoding

Encode weekdays by

$\text{Monday}=0,\ \text{Tuesday}=1,\ \dots,\ \text{Sunday}=6.$

If a date is \(\Delta\) days after 1900-01-01, then its weekday code is simply \(\Delta \bmod 7\), because each extra day advances the weekday by one step in \(\mathbb{Z}/7\mathbb{Z}\).

Leap Years and Month Lengths

Let the leap-year indicator be

$\lambda(y)=\begin{cases}1,&400\mid y,\\1,&4\mid y\ \text{and}\ 100\nmid y,\\0,&\text{otherwise}.\end{cases}$

Then the length of year \(y\) is \(365+\lambda(y)\). For months, define \(L(y,m)\) by the usual Gregorian table:

$L(y,m)\in\{31,\ 28+\lambda(y),\ 31,\ 30,\ 31,\ 30,\ 31,\ 31,\ 30,\ 31,\ 30,\ 31\}.$

The only variable month is February, whose length is \(28+\lambda(y)\).

Elapsed-Day Formula

For any date \((y,m,d)\), the number of elapsed days after 1900-01-01 is

$D(y,m,d)=\sum_{Y=1900}^{y-1}\bigl(365+\lambda(Y)\bigr)+\sum_{M=1}^{m-1}L(y,M)+(d-1).$

The weekday code is therefore

$w(y,m,d)\equiv D(y,m,d)\pmod 7.$

Problem 19 only needs \(d=1\). If we define

$I(y,m)=\begin{cases}1,&w(y,m,1)=6,\\0,&\text{otherwise},\end{cases}$

then the required count is

$S=\sum_{y=1901}^{2000}\sum_{m=1}^{12} I(y,m).$

Equivalent Recurrences for First Days of Months

The same mathematics can be written recursively. Let \(s_{y,m}=w(y,m,1)\). Moving from one month to the next adds exactly the length of the current month, so

$s_{y,m+1}\equiv s_{y,m}+L(y,m)\pmod 7.$

Crossing a year boundary gives

$s_{y+1,1}\equiv s_{y,1}+365+\lambda(y)\pmod 7.$

These recurrences are not a different method; they are just the elapsed-day formula written incrementally.

Worked Example: The Year 1901

Because 1900 is not a leap year, it has \(365\) days, so

$s_{1901,1}\equiv 365\equiv 1\pmod 7,$

which means 1901-01-01 is a Tuesday. Advancing month by month gives:

January 1 Tuesday, February 1 Friday, March 1 Friday, April 1 Monday, May 1 Wednesday, June 1 Saturday, July 1 Monday, August 1 Thursday, September 1 Sunday, October 1 Tuesday, November 1 Friday, December 1 Sunday.

So the year 1901 contributes exactly two qualifying months. Continuing the same count through December 2000 gives the final total \(S=171\).

How the Code Works

The C++, Python, and Java implementations use the elapsed-day formula directly. For each first day of a month in the target interval, the implementation sums the lengths of all complete years from 1900 up to the previous year, then the lengths of all complete months in the current year, then reduces the result modulo \(7\).

An outer loop scans the inclusive year range and all twelve months in each year. Whenever the weekday code of \((y,m,1)\) is \(6\), the answer counter is incremented.

The implementations also include small internal checks derived from the statement and the recurrence above: 1900-01-01 maps to Monday, 1901-01-01 maps to Tuesday, and the year 1901 contributes exactly two Sunday-first months.

Complexity Analysis

Let \(Y\) be the number of years in the queried interval. There are \(12Y\) candidate months, but each weekday computation recomputes the elapsed-day total from the 1900 epoch. Summing the year-loop work over the full interval gives a quadratic total:

$12\sum_{t=1}^{Y} t = O(Y^2).$

The month-loop inside each date computation contributes only \(O(Y)\) overall, and the memory usage is \(O(1)\). For the Project Euler century this cost is tiny in practice, even though a purely incremental implementation could reduce the running time to \(O(Y)\).

Footnotes and References

1. Problem page: Project Euler Problem 19
2. Gregorian calendar: Wikipedia - Gregorian calendar
3. Leap year rule: Wikipedia - Leap year
4. Day-of-week arithmetic: Wikipedia - Determination of the day of the week