Project Euler

A Taste of Number Theory

Problem 19: Counting Sundays

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

The Catch

How to determine what day of a week any given date is.

The Light

There are plenty of methods to determine the day of week: from the Gauss's algorithm to the Schwerdtfeger's variation, but there is also a simpler method. Given any date mm/dd/yyyy:

  • Refer to the Month-Offset Table below to find the offset value of mm.
  • Define a = ((value found in step 1) + dd) % 7.
  • Define b = (the last 2 digits of yyyy) % 28.
  • Define c = b + b/4. Drop all the decimal (similar to (int) c).
  • Refer to the Century-Offset Table below to find the offset value of yyyy.
  • Add c to the value in step 5. If mm is Jan or Feb AND yyyy is a leap year, then subtract 1.
  • Define d = (a + c) % 7. Look for d in the Day of the Week Table below to determine the day of the week.

Month- Offset Table

Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
0 3 3 6 1 4 6 2 5 0 3 5


Century-Offset Table

1600's 1700's 1800's 1900's 2000's
0 5 3 1 0


Day of the Week Table

Sun Mon Tue Wed Thu Fri Sat
1 2 3 4 5 6 7 or 0

Example: December 8th, 1994.
a = (5 + 8) % 7 = 6
b = 94 % 28 = 10
c = 10 + 10/4 = 12.5 = 12
c = 1 + c = 1 + 12 = 13
d = (6 + 13) % 7 = 5, which is a Thursday.
This approach is straightforward and simple to implement, but... why not just let Java do the labor: utilize the Calendar class.

The Code

import java.util.*;

public class Problem19
{
  public static void main(String[] args)
  {
    Calendar c = Calendar.getInstance();
    int count = 0;

    for(int i = 1; i <= 100; i++) //Go from 1/1/1901 to 12/31/2000
    {
      for(int m = 0; m < 12; m++) //0 is January
      { 
        c.set(1900 + i, m, 1);   //The first of every month
        Date d = c.getTime();
        if(d.getDay() == 0)
          count++;
      }
    }
    System.out.println(count);
  }
}