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

Written by on 1 January 2011

Topics: Project Euler

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.

7 Comments For This Post I'd Love to Hear Yours!

  1. rebr says:

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

  2. Darie says:

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

  3. Jean-Marie Hachey says:

    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)

  4. Sivakumar K R says:

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

  5. Henk van Voorthuijsen says:

    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();
    }
    
  6. Rob says:

    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)

  7. tomas says:

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

    Worked 😀

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.