# Project Euler 19: How many Sundays on the first of a month

Problem 19 of Project Euler is a curious little problem. It states

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)?

I thought a while about this, before I realised that the easiest way to solve this is most likely to exploit the .NET API. Like many other high level languages .NET offers a really good day/time API, which is easy to use for a problem like this.

The solution is two simple loops to reach all the dates we need to check, and then check if that is a Sunday. In C# this can be implemented as

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

Pretty simple, and an output as

```There are 171 sundays on the first of a month
Solution took 0 ms
```

I have seen a solution proposed which works for the exact question. Since there are 12 month and 100 years, we have 1200 months with a uniform distribution 1/7th of them is mondays, totalling 171 mondays. This solution works nicely for this period, but not for 1903 – 2002.

## Closing remarks

It was a curious little problem to find an answer for, however using the date/time API it was fairly easy to provide a brute force solution. As usual I have uploaded the source code for you. ### Posted by Kristian rebr

You can do this even in one single loop:
int sundays = 0;
for(DateTime date = new DateTime(1901, 1, 1); date.Date <= new DateTime(2000, 12, 31).Date; date = date.AddMonths(1))
{
if (date.DayOfWeek == DayOfWeek.Sunday) { sundays; }
} Darie

I do not agree with using date 😛
I think one should find a different way of solving the problem Jean-Marie Hachey

The specifications given in the introduction are those of the Gregorian calendar.

“The Gregorian calendar, also called the Western calendar and the Christian calendar, is internationally the most widely used civil calendar. It has been the unofficial global standard for decades, recognised by international institutions such as the United Nations and the Universal Postal Union.” (1)
To know more: perpetual calendar (2); leap year (3).
___

Distribution of the first weekdays for the 16th-20th-century period are presented in Table 1:

Table 1
Sum of the first days of the month in 5 centuries
(1 Jan. 1501 @ 31 Dec. 2000)
http://img11.hostingpics.net/pics/221990pe19table1.jpg

Results in Table 1 were calculated with Kristian’s algorithm (4).
___

Table 2 shows the occurence of the 14 recurring calendars for the 20th century.

Table 2
The fourteen different recurring Gregorian calendars (Period: 1901-2000)
http://img11.hostingpics.net/pics/891552pe19tabletwo.jpg

There are 14 recurring years in the Gregorian calendar:
7 calendars for the regular years and 7 calendars for the bissextile (leap) years.
Periodicity observed: 6-11-11 years (regular years); (4 years (bissextile (leap) years)).
_____

Sources:
1) Gregorian calendar
http://en.wikipedia.org/wiki/Gregorian_calendar
2) Perpetual calendar
http://mathforum.org/library/drmath/view/59233.html
3) Leap year
http://en.wikipedia.org/wiki/Leap_year
4) Code of Project Euler – Problem 19
http://www.mathblog.dk/files/euler/Problem19.cs
5) Microsoft Visual C# 2010 Express
6) Microsoft Office Excel (2007)
7) Microsoft Office Word (2007) Sivakumar K R

Suppose if I need to find the solution for the same problem for a larger input. Lets say 10^16 to 10^16+1000. How can we optimise this solution further.?. Can we make use of any math trick here.?
Because, We cant pass a BigInteger as a parameter to DateTime instance right. Will you please advise on this case.? Henk van Voorthuijsen

in java 8:

```public long sundaysIn20thCentury() throws Exception {
return IntStream.range(1901, 2001)
.boxed()
.flatMap(year -&gt; (Stream&lt;YearMonth&gt;)Stream.of(Month.values())
.map(month -&gt; YearMonth.of(year, month)))
.filter(month -&gt; month.atDay(1).getDayOfWeek().equals(DayOfWeek.SUNDAY))
.count();
}
``` Rob

Here’s how I worked it out:
– 1/1/1901 starts on a Tuesday (Start day is 2).
– Using the rules given I work out the day count for each month.
– I keep a working total of the day count going through the months 1 at
a time, starting from an offset of 2.
– After each month if the day count is evenly divisible by 7, then
the month starts on a Sunday.

``` #!/usr/bin/python```

``` def daysInMonth(year, month): if month == 3 or month == 5 or month == 8 or month == 10: return 30 elif month == 1: return year % 400 == 0 or (year % 4 == 0 and year % 100 != 0) else: return 31 daysSoFar = 0 sundayCount = 0 DAY1_1901 = 2 for year in range(1901, 2001): for month in range(12): daysSoFar += daysInMonth(year, month); if (daysSoFar + DAY1_1901) % 7 == 0: sundayCount += 1 ```

```print "In the years from 1901 to 2000, {} months start on a Sunday".format(sundayCount) ``` tomas

My way of solving this problem:
12 months in a year
100 years
-> 1200 months
1200 / 7 = 171

Worked 😀 T

Python Code:

import calendar
count=0
for x in range(1900,2001):
for y in range(1,13):
if calendar.weekday(x,y,1)==6:
print(x,y)
count+=1

print(count)

OUTPUT:173

Any clue why is the answer different? selenae

@ Sivakumar

The Gregorian calendar repeats on a cycle of 400 years.

Calculate how many 1st-of-the-months fall on Sundays in the 400-year cycle.
Multiply that by the number of full 400-year cycles in the interval (e.g. 2 in your example 1001-year interval).

Then count the Sundays in the remaining years by replacing N with N%400. Pratik Bhangale

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