Interludium: It’s Doomsday!

Posted: February 28, 2013 | Author: | Filed under: algorithms | Tags: , , | Leave a comment

And Now for Something Completely Different (Monty Python’s Flying Circus)

Introduction

This post explains how to calculate the day of the week, with all calculations inside your head.
It’s a geekish party trick, and doesn’t really belong on a research blog,
but since today is in fact doomsday, I feel I can get away with it.
Anyway, here follows the algorithm written down in ocaml, but optimized for my brain.

Doomsday

Doomsday is the most important day of the year. It’s the last day of February:
February 28th on normal years, February 29th on leap years.
If you know what day of the week it is on Doomsday, you quite easily adjust for any other day of the year.
The trick is to have an anchor in each month that is the same day of the week as Doomsday.

Anchors for each month

The Anchor for February is doomsday itself.
The anchor for another even month m is m. The anchor for most odd months can be remembered by
the following mnemonic:

I work 9-5 at the 7-11

It simply helps you remember that doomsday for the 9th month is the fifth day of that month and vice-versa.
This only leaves January and March. March is easy: the zeroth of March is the last day of February, which is doomsday. January is a bit more difficult: most years it’s January 3rd, on leap years it’s the 4th. The ocaml summary is this:

  let anchor_of_month yy = function (* "I work 9-5 at the 7-11" *)
    | 1  -> 3  + leap yy
    | 2  -> 28 + leap yy
    | 3  -> 0  (* last day of Feb is zeroth day of Mar *)
    | 5  -> 9
    | 9  -> 5
    | 7  -> 11
    | 11 -> 7
    | m  -> m

An example:

  • 25/12/2013 Christmas
  • Today (28/2/2013 = Doomsday 2013) is a Thursday
  • Hence, December 12 (12/12) is also a Thursday.
  • 19 Thu, 26 Thu, 25 is a Wednesday.

This is all you need to know to be able to calculate the day of the week for any day in the current year.
The funny thing is that this is rather simple to explain to humans, but not so trivial to formalize.
Here’s an attempt:

  let day_of_week hh yy mm dd = 
    let doom = anchor_of_month yy mm
    and w = of_year hh yy
    in 
    if doom >= dd 
    then zoom_down doom w dd
    else zoom_up doom w dd

The two zoom functions are what we do when we move from the anchor in the month to the day we want.

  let rec zoom_down known w dd = 
    if known = dd then days.(w)
    else
      let t = known -7 in
      if t > dd 
      then zoom_down t w dd
      else zoom_down (known - 1) (prev w) dd

  let rec zoom_up known w dd = 
    if known = dd then days.(w)
    else
      let t = known + 7 in
      if t < dd 
      then zoom_up t w dd
      else zoom_up (known + 1) (next w) dd

If this were code written for a computer, I would have distilled something more compact, but my brain doesn’t handle higher order functions very well.

Doomsday for other years

The most frequent use of the doomsday algorithm as a party trick is the calculation the day of the week of someone’s birthday. The algo will yield a number, which you will interprete as a day of the week.
Days are numbered like this:

Sun 0
Mon 1
… …

The next thing you need to know is the adjustment for the century.
For 19YY years it’s 3 (WEDnesday) while for 20YY years, it’s 2 (Y-TUE-K).
There are rules for other centuries, but I didn’t learn them, as I don’t frequent vampire parties.
The formula I tend to use to calculate the doomsday of a year is shown below.

  let of_year hh yy =
    let start = match hh with
      | 19 -> 3 (* WE'D be in this day *)
      | 20 -> 2 (* Y-Tue-K *)
    in
    let d12 = yy / 12 in
    let r12 = (yy mod 12) in
    let r4 = r12 / 4 in
    (start + d12 + r12 + r4) mod 7

For some years it’s simpler to move the mod 7 up a bit.

Some tests

If you want to practice this, you need some special dates. Below are some exercises.

29/02/2013 => Thu
25/05/2013 => Sat
25/12/2013 => Wed
01/01/2013 => Tue
11/09/2001 => Tue
06/10/1973 => Sat
03/11/1971 => Wed
20/07/1969 => Sun
08/05/1945 => Tue
11/11/1918 => Mon

Closing words

I picked this up on various resources. The good stuff comes from there, the mistakes are my own.

Have fun,

Romain.