# Programming Praxis

A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer

## Thank God It’s Friday!

### June 24, 2011

We have previously given two algorithms to calculate the day of the week, one in the Standard Prelude and one in the exercise on Zeller’s Congruence. In today’s exercise we give three more algorithms to calculate the day of the week.

Our first method is due to Carl Gauss, and is based on moving January and February to the end of the preceding year, then fitting a straight line through the number of days in each month. Gauss gives the formula $w = \left( d + \lfloor 2.6 m - 0.2 \rfloor + y + \lfloor \frac{y}{4} \rfloor + \lfloor \frac{c}{4} \rfloor - 2c \right) \pmod{7}$ where Y is the input year, except that it is reduced by 1 in January and February, d is the day of the month, m is the number of the month, with 1 for March through 12 for February, y is the last two digits of Y, c is the first two digits of Y, and w is the day of the week, with 0 for Sunday through 6 for Saturday. For instance, June 24, 2011 is calculated as 24 + floor(2.6×4−0.2) + 11 + floor(11÷4) + floor(20÷4) – 2×20, modulo 7, which is 5 for Friday.

Our second method is due to Tomohiko Sakamoto, who gives a table of offsets for the days of each month from the day at the start of the year: t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Then Sakamoto subtracts 1 from the input year in January and February and calculates the day of the week with the formula $\left( y + \lfloor \frac{y}{4} \rfloor - \lfloor \frac{y}{100} \rfloor + \lfloor \frac{y}{400} \rfloor + t[m-1] + d \right) \pmod{7}$. For instance, June 24, 2011 is calculated as 2011 + floor(2011÷4) − floor(2011÷100) + floor(2011÷400) + t[6−1] + 24 = 2011 + 502 – 20 + 5 + 3 + 24 = 2525, modulo 7, which is 5 for Friday.

Our third method is due to John Horton Conway, and is intended for mental calculation. Conway’s method is based on calculating the anchor day for the requested century, the doomsday for the requested year, and interpolating from various repetitions of the doomsday through the year.

The anchor day is calculated as $\left( 5c + \lfloor \frac{c-1}{4} \rfloor \right) \pmod{7} + Thursday$, where c is the century; note that century years, such as 2000, are part of the succeeding century, so c=21 for the year 2000. For example, the anchor day for the 21st century is Tuesday, calculated as 5×21 + floor(20÷4), modulo 7, plus Thursday. Anchor days repeat every four centuries, in the cycle Friday, Wednesday, Tuesday, Sunday starting from the year 1800.

The doomsday is calculated by dividing the last two digits of the year by 12 to calculate the quotient and remainder. Then the doomsday is the quotient, plus the remainder, plus the quotient of the remainder divided by 4, plus the anchor day for the century. For example, the doomsday for 2011 is Monday, calculated as 0 + 11 + floor(11÷4) = 13, which is 6 modulo 7, plus the anchor day Tuesday.

Once the doomsday is known, the day of the week is calculated by locating the nearest doomsday in each month, which can be memorized in the following manner: For April, June, August, October, and December, the doomsday is the month number: 4/4, 6/6, 8/8, 10/10, and 12/12. For May, July, September, and November, the doomsday can be calculated by the ditty “I worked 9 to 5 at 7-11″ which gives 5/9, 7/11, 9/5, and 11/7. The last day of February is a doomsday, whether a common year or a leap year, and this gives an easy way to calculate the day of the week for March, where doomsday is 3/0 (the “zeroth” day of March). All that’s left is January, for which the doomsday is 1/10 in common years and 1/11 in leap years.

Thus, the day of the week for June 24, 2011 is calculated as 24−6=18 ≡ 4 (mod 7) days past the doomsday, which gives an answer of Friday. Conway claims to be able to calculate any day of the week in two seconds, though I confess I have not been able to make the required calculations reliably except by using pencil and paper to assist.

Your task is to write programs to calculate the day of the week using the three functions described above; for Conway’s algorithm, you should calculated the doomsday for the year rather than the day of the week for the date. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

### Like this:

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
5 Comments »

### 5 Responses to “Thank God It’s Friday!”

1. June 24, 2011 at 9:45 AM

[...] today’s Programming Praxis exercise, our goal is to implement three functions related to dates: two ways to [...]

2. Remco Niemeijer said
June 24, 2011 at 9:46 AM

My Haskell solution (see http://bonsaicode.wordpress.com/2011/06/24/programming-praxis-thank-god-it%E2%80%99s-friday/ for a version with comments):

```data Weekday = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving (Enum, Eq, Show)

gauss :: Int -> Int -> Int -> Weekday
gauss y m d = toEnum $ mod (d + floor (2.6 * fromIntegral
  (mod (m - 2) 12) - 0.2) + y' + div y' 4 + div c 4 - 2*c) 7 where
    (c,y') = divMod (if m < 3 then y - 1 else y) 100

sakamoto :: Int -> Int -> Int -> Weekday
sakamoto y m d = toEnum $ mod (y + div y 4 - div y 100 +
    div y 400 + [0,3,2,5,0,3,5,1,4,6,2,4] !! (m - 1) + d) 7

conway :: Int -> Weekday
conway y = toEnum $ mod (q + r + div r 4 + 5*(c+1) + div c 4 + 4) 7
    where (c, (q,r)) = (div y 100, divMod (mod y 100) 12)
```
3. Graham said
June 25, 2011 at 11:57 PM

My Python submission (basically just a translation of the Scheme solution):

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

from fractions import Fraction

DAYS = {0: "Sunday", 1: "Monday", 2: "Tuesday", 3: "Wednesday", 4: "Thursday",
        5: "Friday", 6: "Saturday"}

def gauss(year, month, day):
    yr = (year - 1) if (month < 3) else year
    m = (month + 10) if (month < 3) else (month - 2)
    c, y = divmod(yr, 100)
    return DAYS[sum((day, int((Fraction('13/5') * m) - Fraction('1/5')), y,
                 (y / 4), (c / 4), - 2 * c)) % 7]

def sakamoto(year, month, day):
    t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
    y = (year - 1) if (month < 3) else year
    return DAYS[sum((day, y, (y / 4), - (y / 100), (y / 400), t[month - 1]))
                % 7]

def doomsday(year):
    return DAYS[sum((2, year, year / 4, - (year / 100), year / 400)) % 7]

if __name__ == "__main__":
    print gauss(2011, 6, 24)
    print sakamoto(2011, 6, 24)
    print doomsday(2011)
```
4. Mike said
June 28, 2011 at 4:56 AM

Python version

Tried all the formulas from Wikipedia for conway’s method. And went all the way to calculate the day of the week.

```dow = "Sun Mon Tue Wed Thu Fri Sat".split()

def leap(year):
    return bool(not year % 400 or not year % 4 and year % 100)

def gauss(year, month, day):
    c, y = divmod(year if month > 2 else (year - 1), 100)
    m = (month - 3)%12 + 1
    return dow[(day + int(2.6*m - 0.2) + y + y//4 + c//4 - 2*c) % 7]

def sakamoto(year, month, day):
    t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
    y = year if month > 2 else (year - 1)
    return dow[(day + y + y//4 - y//100 + y//400 + t[month - 1]) % 7]

def conway(year, month, day):
    c, y = divmod(year, 100)

    # original formula
    #c += 1
    #anchor = (5*c + (c-1)//4 + 4)%7
    # modified formula-don't add 1 to first 2 digits of year.
    anchor = (5*c + c//4 + 2)%7

    # original conway formula
    #doomsday = (anchor + y//12 + y%12 + y%12//4)%7

    # alternative from wikipedia.  I think this is easiest to do in head.
    doomsday = (anchor + y + y//4)%7

    # odd+11 rule from wikipedia
    #y = (y+11) if y&1 else y
    #y = y//2
    #y = (y+11) if y&1 else y
    #y = 7 - y%7
    #doomsday = (anchor + y)%7

    #computer formula from wikipedia
    #doomsday =  (2 + y + y//4 - y//100 + y//400)%7

    nearest = (10, 28, 0, 4, 9, 6, 11, 8, 5, 10, 7, 12)[month - 1]
    if month < 3 and leap(year):
        nearest += 1
    
    return dow[(doomsday + day - nearest) % 7]
```
5. razvan said
July 5, 2011 at 3:56 PM

Here’s my solution in Java:

```package dayofweek;

public class DayOfWeek {

    private static final int[] SAKAMOTO_TABLE = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6,
            2, 4 };

    private static void checkDate(int d, int m, int y) {
        if (m < 1 || m > 12)
            throw new NumberFormatException("Bad month");
        if (d < 0 || d > 31)
            throw new NumberFormatException("Bad day");
        if (m == 2
                && (d > 29 || d > 28
                        && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)))
            throw new NumberFormatException("Bad day");
        if (y < 0)
            throw new NumberFormatException("Bad year");
    }

    public static int gauss(int d, int m, int y) {
        checkDate(d, m, y);
        if (m >= 3 && m <= 12)
            m -= 2;
        else if (m < 3 && m > 0) {
            m += 10;
            y--;
        }
        int c = y / 100;
        y %= 100;
        return (d + (int) Math.floor(2.6 * (double) m - 0.2) + y + y / 4 + c
                / 4 - 2 * c) % 7;
    }

    public static int sakamoto(int d, int m, int y) {
        checkDate(d, m, y);
        if (m < 3 && m > 0)
            y--;
        return (y + y / 4 - y / 100 + y / 400 + SAKAMOTO_TABLE[m - 1] + d) % 7;
    }

    public static int conway(int d, int m, int y) {
        checkDate(d, m, y);
        int c = y / 100 + 1;
        int anchor = ((5 * c + (c - 1) / 4) % 7 + 4) % 7;
        int yy = y % 100;
        int quo = yy / 12, rem = yy % 12;
        int doomsday = ((quo + rem + rem / 4) % 7 + anchor) % 7;
        int doom = 0;
        if (m == 4 || m == 6 || m == 8 || m == 10 || m == 12)
            doom = m;
        else if (m == 2) {
            if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
                doom = 29;
            else
                doom = 28;
        } else if (m == 3)
            doom = 0;
        else if (m == 3) {
            if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
                doom = 11;
            else
                doom = 10;
        } else
            switch (m) {
            case 5:
                doom = 9;
                break;
            case 7:
                doom = 11;
                break;
            case 9:
                doom = 5;
                break;
            case 11:
                doom = 7;
                break;
            }

        if (d > doom)
            return ((d - doom) % 7 + doomsday) % 7;
        else
            return ((doomsday - (doom - d) % 7) + 7) % 7;
    }

    public static String intToDate(int d) {
        switch (d) {
        case 0:
            return "Sunday";
        case 1:
            return "Monday";
        case 2:
            return "Tuesday";
        case 3:
            return "Wednesday";
        case 4:
            return "Thursday";
        case 5:
            return "Friday";
        case 6:
            return "Saturday";
        }
        throw new NumberFormatException("Bad day of week");
    }

    public static void main(String[] args) {
        System.out.println(intToDate(gauss(24, 6, 2011)));
        System.out.println(intToDate(sakamoto(24, 6, 2011)));
        System.out.println(intToDate(conway(11, 5, 2010)));
    }

}
```
%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 3, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9426423907279968, "perplexity_flag": "middle"}