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.

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

}

I do not agree with using date ðŸ˜›

I think one should find a different way of solving the problem

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

Reference added: System.Numerics

6) Microsoft Office Excel (2007)

7) Microsoft Office Word (2007)

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

in java 8:

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

My way of solving this problem:

12 months in a year

100 years

-> 1200 months

1200 / 7 = 171

Worked ðŸ˜€

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?

@ 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.

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