Problem 19: Counting Sundays

Project Euler Problem 19 Solution

EulerSolve provides an optimized solution for Project Euler Problem 19, Counting Sundays, with C++, Python, Java, and a step-by-step mathematical explanation.

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)$....

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

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

Problem 19 source code

C++

#include <iostream>
#include <string>

namespace {

struct Options {
    int start_year = 1901;
    int end_year = 2000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(const int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--start-year=", options.start_year)) {
            continue;
        }
        if (parse_int_after_prefix(arg, "--end-year=", options.end_year)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.start_year >= 1900 && options.end_year >= options.start_year;
}

bool is_leap_year(const int year) {
    if (year % 400 == 0) {
        return true;
    }
    if (year % 100 == 0) {
        return false;
    }
    return (year % 4 == 0);
}

int days_in_month(const int year, const int month) {
    static const int month_days[] = {
        0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31,
    };
    if (month == 2 && is_leap_year(year)) {
        return 29;
    }
    return month_days[month];
}

int weekday_monday_zero(const int year, const int month, const int day) {
    // 1900-01-01 is Monday -> 0.
    int days = 0;
    for (int y = 1900; y < year; ++y) {
        days += is_leap_year(y) ? 366 : 365;
    }
    for (int m = 1; m < month; ++m) {
        days += days_in_month(year, m);
    }
    days += day - 1;

    return days % 7;
}

int solve(const int start_year, const int end_year) {
    int count = 0;
    for (int year = start_year; year <= end_year; ++year) {
        for (int month = 1; month <= 12; ++month) {
            const int weekday = weekday_monday_zero(year, month, 1);
            if (weekday == 6) {  // Sunday
                ++count;
            }
        }
    }
    return count;
}

bool run_checkpoints() {
    if (weekday_monday_zero(1900, 1, 1) != 0) {
        std::cerr << "Checkpoint failed for 1900-01-01 weekday" << '\n';
        return false;
    }
    if (weekday_monday_zero(1901, 1, 1) != 1) {
        std::cerr << "Checkpoint failed for 1901-01-01 weekday" << '\n';
        return false;
    }
    if (solve(1901, 1901) != 2) {
        std::cerr << "Checkpoint failed for year 1901 count" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.start_year, options.end_year) << '\n';
    return 0;
}

Python

def is_leap_year(year):
    if year % 400 == 0:
        return True
    if year % 100 == 0:
        return False
    return year % 4 == 0

def days_in_month(year, month):
    month_days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    if month == 2 and is_leap_year(year):
        return 29
    return month_days[month]

def weekday_monday_zero(year, month, day):
    # 1900-01-01 is Monday -> 0
    days = 0
    for y in range(1900, year):
        days += 366 if is_leap_year(y) else 365
    for m in range(1, month):
        days += days_in_month(year, m)
    days += day - 1
    return days % 7

def solve(start_year=1901, end_year=2000):
    count = 0
    for year in range(start_year, end_year + 1):
        for month in range(1, 13):
            if weekday_monday_zero(year, month, 1) == 6:  # Sunday
                count += 1
    return count

if __name__ == "__main__":
    assert weekday_monday_zero(1900, 1, 1) == 0, "Checkpoint failed for 1900-01-01"
    assert solve(1901, 1901) == 2, "Checkpoint failed for year 1901"
    print(solve())

Java

public class Euler19 {
    static boolean isLeapYear(int year) {
        if (year % 400 == 0)
            return true;
        if (year % 100 == 0)
            return false;
        return year % 4 == 0;
    }

    static int daysInMonth(int year, int month) {
        int[] md = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
        if (month == 2 && isLeapYear(year))
            return 29;
        return md[month];
    }

    static int weekdayMondayZero(int year, int month, int day) {
        int days = 0;
        for (int y = 1900; y < year; y++)
            days += isLeapYear(y) ? 366 : 365;
        for (int m = 1; m < month; m++)
            days += daysInMonth(year, m);
        days += day - 1;
        return days % 7;
    }

    static int solve(int startYear, int endYear) {
        int count = 0;
        for (int y = startYear; y <= endYear; y++)
            for (int m = 1; m <= 12; m++)
                if (weekdayMondayZero(y, m, 1) == 6)
                    count++;
        return count;
    }

    public static void main(String[] args) {
        assert solve(1901, 1901) == 2 : "Checkpoint failed";
        System.out.println(solve(1901, 2000));
    }
}