# 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

### 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++;
}
}
}


On the difference between .NET and C#, .NET is a dev platform for building cross-platform apps, and C# is one of the languages in which one can use the .NET platform. Other languages include F# and Visual Basic.

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.

Maybe is what meant by “you may prefer to do some research for yourself”?

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.

See Modular Arithmetic for a review of 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.