Project Euler Problem 19

Project Euler Problem 19

Solution

Answer: 171

We need to count how many times the 1st day of a month was a Sunday during the twentieth century, from 1 Jan 1901 to 31 Dec 2000.

Mathematical approach

We are given:

• 1 Jan 1900 was a Monday

• Leap year rule:

• divisible by 4 → leap year

• century years are not leap years unless divisible by 400

A straightforward method is:

1. Track the weekday of each date using day offsets.
2. Start from 1 Jan 1900 = Monday.
3. Move month-by-month.
4. Count whenever:

• the year is between 1901 and 2000 inclusive, and
• the first day of the month is a Sunday.

Represent weekdays modulo 7, e.g.

• 0 = Monday
• …
• 6 = Sunday

For each month, advance by the number of days in that month.

Clean Python code

def is_leap(year):
    return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

month_days = [31, 28, 31, 30, 31, 30,
              31, 31, 30, 31, 30, 31]

day_of_week = 0  # 0 = Monday on 1 Jan 1900
count = 0

for year in range(1900, 2001):
    for month in range(12):
        # Count Sundays on the first of the month
        if year >= 1901 and day_of_week == 6:
            count += 1

        days = month_days[month]

        # February in leap year
        if month == 1 and is_leap(year):
            days += 1

        day_of_week = (day_of_week + days) % 7

print(count)

This computes:

171

Mental check / correctness

• We start at 1 Jan 1900 = Monday.
• We correctly propagate weekdays month-by-month.
• Leap years are handled exactly according to the Gregorian rule (notably 1900 is not leap, 2000 is leap).
• We count only months in 1901–2000 inclusive.

Answer: 171