019. Counting Sundays

Problem Statement

You are given the following information, but you may prefer to do some research for yourself:

• 1 Jan 1900 was a Monday.
• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Solution

Manual Attempt

Programmatic Attempt

#include <iostream>
#include <cassert>

enum class Month {
    Jan = 1, Feb, Mar, Apr, May, June, July, Aug, Sept, Oct, Nov, Dec};

/**
 * Core idea: Index the days in an increasing manner. 01/01/1900 corresponds
 * to 1, 02/01/1900 corresponds to 32, and so forth.
 */

/**
 * Return the number of days in month `increasing_month_idx`, where a value of
 * 1 corresponds to Jan 1900, and values increase monotonically thereafter.
 */
int NumOfDaysInMonth(int increasing_month_idx) {
    assert(increasing_month_idx > 0);

    int month_idx_base12 = increasing_month_idx % 12;
    if (month_idx_base12 == 0) month_idx_base12 = 12;

    Month month = static_cast<Month>(month_idx_base12);
    assert(month >= Month::Jan && month <= Month::Dec);

    switch (month) {
        case Month::Sept:
        case Month::Apr:
        case Month::June:
        case Month::Nov:
            return 30;

        case Month::Feb: {
            const int year = 1900 + (increasing_month_idx / 12);
            const bool is_leap_year =
                (year % 100 == 0) ? (year % 400 == 0) : (year % 4 == 0);
            return is_leap_year ? 29 : 28;
        }

        default:
            return 31;
    }
}

/**
 * Given that 1 Jan 1900 was a Monday, how many Sundays fell on the first of the
 * month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
 *
 * [1]: https://projecteuler.net/problem=19
 */
void solve_euler_19() {
    // 365 for the year 1900, and (365.25 * 100) for the next 100 years.
    const int total_num_days = 365 + 36525;

    // Returns true if `day_idx` is between 1 Jan 1901 and 31 Dec 200,
    // inclusive.
    std::function<bool(int)> is_in_range_of_interest = [&](int day_idx) {
        return day_idx > 365 && day_idx <= total_num_days;
    };

    // Returns true if `day_idx` was a Sunday. Uses the fact that 7th Jan, 1900
    // was a Sunday.
    std::function<bool(int)> is_a_sunday = [&](int day_idx) {
        return day_idx % 7 == 0;
    };

    int num_sundays_on_first_of_the_month = 0;
    int increasing_month_idx = 1;
    int day_idx = 0;
    while (day_idx <= total_num_days) {
        int first_day_of_month_idx = day_idx + 1;
        if (is_a_sunday(first_day_of_month_idx)
            && is_in_range_of_interest(first_day_of_month_idx)) {
                num_sundays_on_first_of_the_month += 1;
        }
        day_idx += NumOfDaysInMonth(increasing_month_idx);
        increasing_month_idx += 1;
    }

    std::cout << num_sundays_on_first_of_the_month << " Sundays\n";
}

int main() {
    solve_euler_19();
    return 0;
}

Tried setting up a C++ build, like the one used in the Chromium Project . Setting up Clang , LLVM , Ninja and GN took some time. Mostly because I don’t have a good understanding of the purpose of each.

Other People’s Solutions

Some used the Date/Time libraries for their languages. For example, using C#:

int sundays = 0;

for (int year = 1901; year <= 2000; year++) {
    for (int month = 1; month <= 12; month++) {
        if ((new DateTime(year, month, 1)).DayOfWeek == DayOfWeek.Sunday) {
            sundays++;
        }
    }
}

This didn’t occur to me as it defeats the purpose of Project Euler. There’s no fun in letting the built-in functions do most of the work for you. That said, it’s pretty sweet how programming languages have made things easier for us.

goes a different route. They mention Zeller’s Congruence, an algorithm for calculating the day of the week for any Julian or Gregorian calendar date. For the Gregorian calendar, we have:

$$ h = \left( q + \lfloor \frac{13(m + 1)}{5} \rfloor + K + \lfloor K/4 \rfloor + \lfloor J/4 \rfloor - 2J \right) \text{mod } 7 $$

… where \(h\) is the day of the week (0 = Sat, 1 = Sun, …, 6 = Fri), \(q\) is the day of the month, \(m\) is the month (3 = Mar, 4 = Apr …, 14 = Feb), \(K\) is the year of the century (\(\text{year } \text{mod } 100\)), and \(J\) is the zero-based century (\(\lfloor \text{year}/100 \rfloor\)). Jan and Feb are counted as months 13 and 14 of the previous year, e.g. Jan 1st, 1901 would be 13/01/1900 in MM/DD/YYYY format.

However, doesn’t help us in solving the problem faster. ’s final [annotated] solution is:

function solution() {
  var numSundaysOnFirstDayOfMonth = 0;
  var dayOfWeekOfTheFirst = 2; // 01/01/1901 was a Tuesday
  var months = [31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

  for (var y = 1901; y <= 2000; y++) {
    // Update the numbers of days in February.
    months[1] = 28 + (y % 4 === 0 && y % 100 !== 0 || y % 400 === 0);

    for (var month of months) {
      // Adding 7 days results in the same day of the week. Adding the number of
      // days per month helps us go faster. We make use of the homomorphic rule:
      //
      //   (d + m) ≡ (d mod 7 + m mod 7) (mod 7)
      //
      dayOfWeekOfTheFirst += month % 7;

      if (dayOfWeekOfTheFirst % 7 === 0) {
        numSundaysOnFirstDayOfMonth++;
      }
    }
  }
  return numSundaysOnFirstDayOfMonth;
}

There are two things that I don’t understand in ’s code.

First, why is dayOfWeekOfTheFirst given a value of 2 despite 2 being Monday in Zeller’s Congruence formula? If I change dayOfWeekOfTheFirst to to 3 as per Zeller, and check Sundays by dayOfWeekOfTheFirst % 7 === 1, then the code still gives the right answer. Maybe it’s a matter of being consistent with how you label the days of the week.

Second, which homomorphic property is \( (d + m) \equiv (d \text{ mod } 7 + m \text{ mod } 7) \ (\text{mod } 7) \)? Going by , that’s a known result in modular arithmetic.

References

1. #19 Counting Sundays - Project Euler. projecteuler.net . Accessed Jan 7, 2022.
2. Project Euler 19: How many Sundays on the first of a month in C# | MathBlog. Kristian Edlund. www.mathblog.dk . 2013. Accessed Jan 8, 2022.
3. .NET documentation | Microsoft Docs. docs.microsoft.com . docs.microsoft.com . Accessed Jan 8, 2022.
4. Project Euler 19 Solution: Counting Sundays • Computer Science and Machine Learning. Robert Eisele. www.xarg.org . Accessed Jan 8, 2022.
5. Zeller's congruence - Wikipedia. en.wikipedia.org . Accessed Jan 8, 2022.
6. Modular addition and subtraction (article) | Khan Academy. www.khanacademy.org . Accessed Jan 10, 2022.