# 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);
}
}
```