# We study the calendar

• Tutorial
“Is there a year in which not a single month begins on Monday?”
At first glance, yes. A year can start from any day of the week, months also each time start on different days of the week. There are many options, most likely, there will be more than one such year.

So I thought the first minute after I wondered. This should be proved. Go through all the years, for example. A simple and quick way, but not interesting. To prove mathematically was a much more tempting idea, but I completely did not understand how to approach this. Therefore, I just began to write out the duration of each month on paper.

Here it is worth mentioning that we will talk more about the Gregorian calendar , according to which we have been living since 1918. However, part of the reasoning will be true for Julian .

In fact, such a year does not exist. Let's figure out why.

## Part 1. Months

First, remember how many days in each month:
 Jan Feb March Apr May June July Aug Sep Oct Nov Dec 31 28/29 31 thirty 31 thirty 31 31 thirty 31 thirty 31
Now let's see how many days in each month are more than four weeks.
 Jan Feb March Apr May June July Aug Sep Oct Nov Dec 3 0/1 3 2 3 2 3 3 2 3 2 3
At this point, the following idea arises. If you add 7 days to the date, the day of the week will not change. Modular arithmetic works. From here it is easy to understand that if there are two more days in a month than in four weeks, then the first day of the next month will shift by two days of the week relative to the first day of the current month. Anyway,
if there are (28 + N) days in a month, then the first day of the next month will shift by N days relative to the day of the week on the first day of the current month.
For example, this year January began on Tuesday, so February began on Friday. Tue + 3 = Fri

How much is the day of the week on the first day of a certain month? To find this, you need to sum the “surplus” days over four weeks in all previous months. The table shows the shifts relative to the day of the week on the first of January. The first line is for a non-leap year, the second is for a leap year.
 Jan Feb March Apr May June July Aug Sep Oct Nov Dec 0 3 3 6 8 eleven thirteen 16 19 21 24 26 0 3 4 7 9 12 14 17 20 22 25 27
But this does not look very revealing, and we know that a shift of seven days does not change the day of the week. Therefore, we now write in the table the residuals from dividing the total shifts by 7.
 Jan Feb March Apr May June July Aug Sep Oct Nov Dec 0 3 3 6 1 4 6 2 5 0 3 5 0 3 4 0 2 5 0 3 6 1 4 6
Now another thing! It is clearly seen how to determine the day of the week on the first day of any month if the day of the week on the first of January is known. You just need to add a shift for the month of interest. I have known the pattern February-March-November since high school, but I did not notice the others.

We got the answer to the question at the beginning of the article.
Since for both variants of the year in the table there are all shifts from 0 to 6, then in any year there is a month that begins on some specific day of the week.
But now you can ask other questions. For example, “in what years is there only one such month?” Or “in which years of such months is the maximum?”. To do this, you must be able to determine the day of the week on the first of January of any year.

## Part 2. Years

When I learned to program, and this was in the 10th grade of the school at PascalABC, one of the first serious tasks was to implement a procedure that prints a calendar for the year, which was passed as an argument. We had tips on what functions to implement. In general, it came down to counting the days between two dates: the reference and the current, to determine the day of the week on January 1 of the desired year.

This approach worked, but the speed depended on how close the required year to the reference. It upset me, but I couldn’t come up with something better then. Now, the perfect moment has come to fully understand this.

Leap years in the Gregorian calendar are assigned as follows:
• a year whose number is a multiple of 400 is a leap year
• the remaining years, the number of which is a multiple of 100, are non-leap
• the remaining years, the number of which is a multiple of 4, are leap years
• the rest of the years are non-leap
This description shows that the leap cycle has a period of 400 years. But it is not clear whether such four-hundred-year cycles will begin on the same day of the week.

Note that the first of January from year to year is shifted by one or two days of the week, and write
some code.
``````bool is_leap_year(int year)
{
if ((year % 400) == 0) return true;
if ((year % 100) == 0) return false;
if ((year %   4) == 0) return true;
return false;
}
void first_weekdays_table()
{
ofstream file("weekdays.txt", ios_base::out);
int weekday = 3;
for (int i = 1801; i <= 3000; ++i)
{
file << weekday;
if ((i % 100) != 0)
{
file << " ";
}
else
{
file << endl;
}
weekday += is_leap_year(i) ? 2 : 1;
weekday %= 7;
}
file.close();
}
``````

The days of the week are displayed on the first of January of each year, from 1801 to 3000. Monday is designated as “0”, Tuesday as “1”, etc. We will present everything in the form of a table of two complete four-hundred-year cycles and two halves. Centuries go horizontally, the vertical of the year in these centuries. In the cells at the intersection of the century and year, the day of the week on which this year began is written. For example, the day of the week that 1997 began is at the intersection of column “1900” and line “97”. This is Wednesday. Full version of the table: part 1 , part 2 .

In the table, you can immediately notice two things: four-hundred-year cycles really begin on the same day of the week (2001, 2401 and 2801; Monday), and instead of 2000 there is "one thousand nine hundredth." The latter was done on purpose, for further convenience. The first fact allows us to move on without obstacles.
In the Gregorian calendar, all four hundred-year cycles begin on Monday.
But the most interesting lies in the full version of the table. You may find that every century within a four-hundred-year cycle consists of a repeating twenty-eight-year cycle:
 0 1 2 3 5 6 0 1 3 4 5 6 1 2 3 4 6 0 1 2 4 5 6 0 2 3 4 5

The first century begins with a shift in the cycle equal to 0, the second with a shift of 4, the third with a shift of 8 and the fourth with a shift of 12. For this, the table is presented in the form where there are “hundredths” of a century and there are no zero. It is worth saying that in total there are 14 different options for the year. In a twenty-eight-year cycle, once for each day of the week, the beginning of a leap year falls and three times the start of a non-leap year.

Now we can determine the day of the week for any date without using reference dates. To do this, we need to understand in which century, within a four-hundred-year cycle, is a year, and what is its account in this century. According to the table we determine the day of the week on the first of January of the year, and with the help of the first part of the article - the day of the week on the specific day of the desired month. Instead of a thousand words
we’ll write some more code.
``````int get_weekday(int year, int month, int day)
{
int weekdays[] = {0, 1, 2, 3, 5, 6,
0, 1, 3, 4, 5, 6,
1, 2, 3, 4, 6,
0, 1, 2, 4, 5, 6,
0, 2, 3, 4, 5};
int shift_not_leap[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};
int shift_leap[]     = {0, 3, 4, 0, 2, 5, 0, 3, 6, 1, 4, 6};
bool is_leap = is_leap_year(year);
year -= 1;
year %= 400;
int century = year / 100;
year %= 100;
int index = (year + (4 * century)) % 28;
int weekday = weekdays[index];
weekday += is_leap ? shift_leap[month - 1]
: shift_not_leap[month - 1];
weekday += (day - 1);
weekday %= 7;
return weekday;
}
``````

### Update from 07/03/2019

If we present the twenty-eight-year cycle in the form of a table,

``````0, 1, 2, 3,    5, 6,
0, 1,    3, 4, 5, 6,
1, 2, 3, 4,    6,
0, 1, 2,    4, 5, 6,
0,    2, 3, 4, 5
``````

it becomes clear how you can calculate the shift of the day of the week to January 1:

``````weekday = (index + (index / 4)) % 7;
``````

Given this, as well as the fact that the offsets for months in a leap year can be calculated through the offsets in a non-leap year, we write
next function
``````int get_weekday_c(int year, int month, int day)
{
int shifts[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};
int shift = shifts[month - 1];
if (is_leap_year(year) and (month > 2))
{
shift += 1;
};
year = (year - 1) % 400;
int century = year / 100;
int index   = ((4 * century) + (year % 100)) % 28;
int weekday = (index + (index / 4)) + shift + (day - 1);
return (weekday % 7);
}
``````

Thus, you can calculate the day of the week for any date, knowing only 12 numbers: the shift of the days of the week to the first day of each month.

## Part 3. Summary

With just two tables, you can determine the day of the week for any date without using reference dates.

The sequence of days of the week on January 1 in a twenty-eight-year cycle:
 0 1 2 3 5 6 0 1 3 4 5 6 1 2 3 4 6 0 1 2 4 5 6 0 2 3 4 5

And a table of weekday offsets by the first day of each month for non-leap and leap years:
 Jan Feb March Apr May June July Aug Sep Oct Nov Dec 0 3 3 6 1 4 6 2 5 0 3 5 0 3 4 0 2 5 0 3 6 1 4 6
At the time of writing the article, I found on Habré two similar topics: one and two . The author of the first, using a special table, shows how to find in the mind the day of the week for dates in the XX and XXI centuries. The table he presented contains 56 numbers. The algorithm proposed in the article uses the table of the days of the week and two offset tables containing (28 + 2 * 12) = 52 numbers that you need to remember. All source code is on GitHub .

An interesting fact: from February 1 to 13, 1918, not a single person was born in Soviet Russia.

Ask yourself questions in the morning on Sundays =)