The Great Crash (aka the Wall Street Crash of 1929) occurred in October 29, 1929

Multiple Choice question:

This day in history is also known as

a) Black Monday

b) Black Tuesday

c) Black Wednesday

d) Black Thursday

e) Black Friday

Saturday and Sunday are excluded because the stock market is closed on those days.

## Tuesday, July 31, 2012

## Friday, December 2, 2011

### Unix cal program for September 1752

//calendar for September 1752

% cal 9 1752

September 1752

Su Mo Tu We Th Fr Sa

1 2 14 15 16

17 18 19 20 21 22 23

24 25 26 27 28 29 30

## Monday, October 24, 2011

### Prepare to Meet Thy Doomsday

I wrote an article for Scientific American regarding the Doomsday algorithm.

"What Day is Doomsday? How to Mentally Calculate the Day of the Week for Any Date"

special thanks to John Matson for the editorial work.

Chinese translation: http://www.ccglim.com/11434.html

"What Day is Doomsday? How to Mentally Calculate the Day of the Week for Any Date"

special thanks to John Matson for the editorial work.

Chinese translation: http://www.ccglim.com/11434.html

## Sunday, August 7, 2011

### Sakamoto's Algorithm

Tomohiko Sakamoto came up with a terse program for calculating the day of the week in 1993. His code was written in the C language. The non-portable code goes like this:

int dayofweek(unsigned int y, unsigned int m, unsigned int d)

{

y -= m < 3;

return (y + y/4 - y/100 + y/400 + "-bed=pen+mad."[m] + d) % 7;

}

Here is the portable version:

int dayofweek(int y, int m, int d)

{

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

y -= m < 3;

return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;

}

int dayofweek(unsigned int y, unsigned int m, unsigned int d)

{

y -= m < 3;

return (y + y/4 - y/100 + y/400 + "-bed=pen+mad."[m] + d) % 7;

}

Here is the portable version:

int dayofweek(int y, int m, int d)

{

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

y -= m < 3;

return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;

}

## Monday, May 30, 2011

## Saturday, January 22, 2011

### Doomsday Timeline

by the doomsayers

The Doomsday Algorithm was first introduced in 1973. Over the years, it has undergone many refinements and improvements. The ultimate goal is to make the algorithm easy to calculate mentally in addition to being easy to remember. Here is a timeline of important modifications to the Doomsday algorithm. Please email spectralfft at yahoo.com for corrections/suggestions to this timeline

1882: Christian Zeller devised the Zeller's congruence algorithm for determining the day of the week for any calendar date. This algorithm is not suitable for mental calculation but works well in computer software.

1887: Lewis Carroll published a perpetual calendar algorithm in the journal Nature with the title "To Find the Day of the Week for Any Given Date". Carroll's algorithm can be performed mentally. Lewis Carroll, himself, can calculate the day of the week in about 20 seconds.

1967: Martin Gardner published "Tricks of Lightning Calculators" in the May issue of Scientific American magazine. He gives a full description of Carroll's calendar algorithm.

when?: Martin Gardner told John Horton Conway about Lewis Carroll's perpetual calendar algorithm and challenged him to come up with a better algorithm.

1973: John Horton Conway published the original Doomsday algorithm in the journal Eureka. The title of his paper is "Tomorrow is the Day After Doomsday". Conway reuses Lewis Carroll's formula for calculating doomsyear.

when?: John Horton Conway came up with an improved mnemonic "working 9 to 5 at the 7-Eleven"

when?: John Horton Conway came up with a table-lookup acceleration to calculating the doomsyear term. This method is very fast but it requires the memorization of 18 numbers.

1993: Tomohiko Sakamoto posted a terse C program containing his calendar algorithm in the Usenet newsgroup comp.lang.c . His algorithm and program listing is remarkably simple, but not suitable for mental calculation. Moreover, unlike Zeller's congruence, the Sakamoto algorithm uses table-lookup for each of the 12 months.

1994: Rudy Limeback created a website on the Doomsday algorithm

1995: Sidney Graham created a website on the Doomsday algorithm

2001: Bob Goddard came up with an improved mnemonic -- January 3/4 instead of the original January 31/32

2004: Sohael Babwani published a new algorithm for calculating the day of the week for any calendar date. Like Zeller's congruence, his algorithm is not suitable for mental calculation.

2008: Mike Walters came up with an algorithm to simplify doomsyear term calculation. Bob Goddard later helped him refine this method.

2009: Bob Goddard published the "First Sunday Doomsday Algorithm" which introduced several innovations, including the use of 7's complement in lieu of subtraction/negation

2010: Chamberlain Fong devised the Decade method for calculating doomsyear

2010: Chamberlain Fong and Mike Walters devised the Odd+11 method for calculating doomsyear

2010: Yingking Yu came up with new mnemonics: January 11 and February 22 for leap years. Yingking Yu also made several suggestions to calculating doomsyear.

The Doomsday Algorithm was first introduced in 1973. Over the years, it has undergone many refinements and improvements. The ultimate goal is to make the algorithm easy to calculate mentally in addition to being easy to remember. Here is a timeline of important modifications to the Doomsday algorithm. Please email spectralfft at yahoo.com for corrections/suggestions to this timeline

1882: Christian Zeller devised the Zeller's congruence algorithm for determining the day of the week for any calendar date. This algorithm is not suitable for mental calculation but works well in computer software.

1887: Lewis Carroll published a perpetual calendar algorithm in the journal Nature with the title "To Find the Day of the Week for Any Given Date". Carroll's algorithm can be performed mentally. Lewis Carroll, himself, can calculate the day of the week in about 20 seconds.

1967: Martin Gardner published "Tricks of Lightning Calculators" in the May issue of Scientific American magazine. He gives a full description of Carroll's calendar algorithm.

when?: Martin Gardner told John Horton Conway about Lewis Carroll's perpetual calendar algorithm and challenged him to come up with a better algorithm.

1973: John Horton Conway published the original Doomsday algorithm in the journal Eureka. The title of his paper is "Tomorrow is the Day After Doomsday". Conway reuses Lewis Carroll's formula for calculating doomsyear.

when?: John Horton Conway came up with an improved mnemonic "working 9 to 5 at the 7-Eleven"

when?: John Horton Conway came up with a table-lookup acceleration to calculating the doomsyear term. This method is very fast but it requires the memorization of 18 numbers.

1993: Tomohiko Sakamoto posted a terse C program containing his calendar algorithm in the Usenet newsgroup comp.lang.c . His algorithm and program listing is remarkably simple, but not suitable for mental calculation. Moreover, unlike Zeller's congruence, the Sakamoto algorithm uses table-lookup for each of the 12 months.

1994: Rudy Limeback created a website on the Doomsday algorithm

1995: Sidney Graham created a website on the Doomsday algorithm

2001: Bob Goddard came up with an improved mnemonic -- January 3/4 instead of the original January 31/32

2004: Sohael Babwani published a new algorithm for calculating the day of the week for any calendar date. Like Zeller's congruence, his algorithm is not suitable for mental calculation.

2008: Mike Walters came up with an algorithm to simplify doomsyear term calculation. Bob Goddard later helped him refine this method.

2009: Bob Goddard published the "First Sunday Doomsday Algorithm" which introduced several innovations, including the use of 7's complement in lieu of subtraction/negation

2010: Chamberlain Fong devised the Decade method for calculating doomsyear

2010: Chamberlain Fong and Mike Walters devised the Odd+11 method for calculating doomsyear

2010: Yingking Yu came up with new mnemonics: January 11 and February 22 for leap years. Yingking Yu also made several suggestions to calculating doomsyear.

## Sunday, June 20, 2010

### Methods for Accelerating Conway's Doomsday Algorithm

updated arXiv version of this document:

http://arxiv.org/abs/1006.3913

and part 2

http://arxiv.org/abs/1010.0765

We propose a simplification of a key component in the Doomsday Algorithm for calculating the day-of-the-week of any given date. In particular, we propose to replace the calculation of the required term:

floor(x/12) + x mod 12 + floor((x mod 12)/4)

with

2 y + 3(y mod 2) + z + leap

where

x is an input two-digit year;

y is the tens digit of x;

z is the ones digit of x;

leap is the number of leap years in the y decade less than or equal to x excluding the start of the decade;

We argue that this simplification makes the algorithm simpler and easier to calculate mentally.

The Doomsday rule is an algorithm for calculating the day of the week for any given calendar date. It was invented by John Horton Conway in 1982. It was designed to be simple enough that, with practice, one can do the calculation in his head without paper or pencil and come up with an answer in just a few seconds. Conway himself was able to do the algorithm calculations in his head in about 2 seconds [1].

For brevity, we won't discuss the full algorithm here. Instead we refer the readers to excellent writeups [2][3] that describe the algorithm in full detail. We will, however, summarize key components of the algorithm to point out some important definitions and nomenclature.

The Doomsday algorithm's input is a calendar date of the form MM/DD/YYYY where MM is the month, DD is the day, and YYYY is the year. YYYY can further be broken down to its constituent century CC and year within the century YY. The output of the algorithm is a number between 0 to 6 that corresponds to each of the 7 days fo the week.

The key equation of the Doomsday rule can be described a sum (modulo 7) of three terms:

day_of_the_week = [doomscentury + doomsyear + doomsmonth ] mod 7

where:

doomscentury(CC) is a function of the input date's century

doomsyear(YY) is a function of the input date's 2-digit year within a century

doomsmonth(MM,DD) is a function of the input date's calendar month and day.

In this paper, we only really care about the doomsyear term. We will only gloss over the doomsmonth and doomscentury terms. The doomsmonth term is what takes advantage of the fact that April 4, June 6, August 8, October 10, and December 12 all fall on the same day of the week for any calendar year. The doomscentury term accounts for the quirk in the Gregorian calendar system where years that are divisible by 100 are not leap years except when they are divisible by 400. We will not attempt to simplify or discuss further the doomscentury and doomsmonth terms for the rest of this paper.

The doomsyear term is given by Conway [4] as:

floor(x/12) + x mod 12 + floor((x mod 12)/4)

where x is the input date's 2-digit year within a century.

The addition is always modulo 7, so the resulting doomsyear term is a number between 0 and 6, inclusive.

In practice, calculating the doomsyear term is a bottleneck of the Doomsday algorithm. Aside from having to do divisions by 12 and 4, one has to keep in memory 3 numbers to add. The term given by Conway is actually already an acceleration method for the term

x + floor(x/4)

which, in practice, is difficult to calculate for two-digit input numbers mentally [2] especially if followed by a required modulo 7 operator. Several people have suggested acceleration methods for the doomsyear term. Conway himself offered a lookup table acceleration for it [3][5]. His acceleration method is arguably the fastest but it requires the memorization of 18 numbers and extra rules for handling leap years. In 2008, Mike Walters [6] came up with a simpliflication of the doomsyear term that involves addition of multiples of 11, a division by 2, and a negation modulo 7 operator. Bob Goddard [7] made improvements to this method in 2009. Our proposed acceleration method is just as simple as Mike Walters' and Bob Goddard's method. In addition, our proposed acceleration method is amenable to a table-lookup memorization similar to Conway’s lookup table acceleration.

Let us break down the two-digit year x into its constituent digits y and z, where y is the tens digit, and z is ones digit. That is,

http://arxiv.org/abs/1006.3913

and part 2

http://arxiv.org/abs/1010.0765

**Abstract**We propose a simplification of a key component in the Doomsday Algorithm for calculating the day-of-the-week of any given date. In particular, we propose to replace the calculation of the required term:

floor(x/12) + x mod 12 + floor((x mod 12)/4)

with

2 y + 3(y mod 2) + z + leap

where

x is an input two-digit year;

y is the tens digit of x;

z is the ones digit of x;

leap is the number of leap years in the y decade less than or equal to x excluding the start of the decade;

We argue that this simplification makes the algorithm simpler and easier to calculate mentally.

**Introduction**The Doomsday rule is an algorithm for calculating the day of the week for any given calendar date. It was invented by John Horton Conway in 1982. It was designed to be simple enough that, with practice, one can do the calculation in his head without paper or pencil and come up with an answer in just a few seconds. Conway himself was able to do the algorithm calculations in his head in about 2 seconds [1].

For brevity, we won't discuss the full algorithm here. Instead we refer the readers to excellent writeups [2][3] that describe the algorithm in full detail. We will, however, summarize key components of the algorithm to point out some important definitions and nomenclature.

The Doomsday algorithm's input is a calendar date of the form MM/DD/YYYY where MM is the month, DD is the day, and YYYY is the year. YYYY can further be broken down to its constituent century CC and year within the century YY. The output of the algorithm is a number between 0 to 6 that corresponds to each of the 7 days fo the week.

The key equation of the Doomsday rule can be described a sum (modulo 7) of three terms:

day_of_the_week = [doomscentury + doomsyear + doomsmonth ] mod 7

where:

doomscentury(CC) is a function of the input date's century

doomsyear(YY) is a function of the input date's 2-digit year within a century

doomsmonth(MM,DD) is a function of the input date's calendar month and day.

In this paper, we only really care about the doomsyear term. We will only gloss over the doomsmonth and doomscentury terms. The doomsmonth term is what takes advantage of the fact that April 4, June 6, August 8, October 10, and December 12 all fall on the same day of the week for any calendar year. The doomscentury term accounts for the quirk in the Gregorian calendar system where years that are divisible by 100 are not leap years except when they are divisible by 400. We will not attempt to simplify or discuss further the doomscentury and doomsmonth terms for the rest of this paper.

The doomsyear term is given by Conway [4] as:

floor(x/12) + x mod 12 + floor((x mod 12)/4)

where x is the input date's 2-digit year within a century.

The addition is always modulo 7, so the resulting doomsyear term is a number between 0 and 6, inclusive.

**Related Work**

In practice, calculating the doomsyear term is a bottleneck of the Doomsday algorithm. Aside from having to do divisions by 12 and 4, one has to keep in memory 3 numbers to add. The term given by Conway is actually already an acceleration method for the term

x + floor(x/4)

which, in practice, is difficult to calculate for two-digit input numbers mentally [2] especially if followed by a required modulo 7 operator. Several people have suggested acceleration methods for the doomsyear term. Conway himself offered a lookup table acceleration for it [3][5]. His acceleration method is arguably the fastest but it requires the memorization of 18 numbers and extra rules for handling leap years. In 2008, Mike Walters [6] came up with a simpliflication of the doomsyear term that involves addition of multiples of 11, a division by 2, and a negation modulo 7 operator. Bob Goddard [7] made improvements to this method in 2009. Our proposed acceleration method is just as simple as Mike Walters' and Bob Goddard's method. In addition, our proposed acceleration method is amenable to a table-lookup memorization similar to Conway’s lookup table acceleration.

**Simplified Formula**

Let us break down the two-digit year x into its constituent digits y and z, where y is the tens digit, and z is ones digit. That is,

y = floor(x/10)

z = x mod 10

For example, if x = 74, then y= 7 and z = 4. If x = 88, then y= 8 and z= 8.

Having defined y and z in terms of x, we propose the replacement doomsyear function as

doomsyear(y,z) = 2 y + 3 (y mod 2) + z + leap

We define an extra variable called leap as the number of leap years between the start of the y decade and the z year. If the start of a decade is a leap year, we don't count it. But if the year z is a leap year, we do include it. For example, if x = 88, the decade starts at 80 and we have leap = 2 because 84 and 88 are leap years. If x=74, the decade starts at 70 and we have leap = 1 because 72 is a leap year. In general, the variable leap can only have three values: 0 , or 1, or 2. There can't be more than 2 leap years after the start of a decade. Remember, we never include the start of the decade in our leap count.

z = x mod 10

For example, if x = 74, then y= 7 and z = 4. If x = 88, then y= 8 and z= 8.

Having defined y and z in terms of x, we propose the replacement doomsyear function as

doomsyear(y,z) = 2 y + 3 (y mod 2) + z + leap

We define an extra variable called leap as the number of leap years between the start of the y decade and the z year. If the start of a decade is a leap year, we don't count it. But if the year z is a leap year, we do include it. For example, if x = 88, the decade starts at 80 and we have leap = 2 because 84 and 88 are leap years. If x=74, the decade starts at 70 and we have leap = 1 because 72 is a leap year. In general, the variable leap can only have three values: 0 , or 1, or 2. There can't be more than 2 leap years after the start of a decade. Remember, we never include the start of the decade in our leap count.

In summary, our proposed method for calculating doomsyear breaks the 2-digit input year into its constituent digits; and does simple arithmetic on these digits. Afterwards, there is the addition of a leap year correction term. Our method essentially requires only 3 additions and a multiplication by 2. Moreover, since the input is broken down to single digit numbers, the calculations done only involve small numbers and are easy to do mentally. In fact, our doomsyear arithmetic only involves positive integers in between 0 to 31. This range of numbers happens to be the “calendar range” which probably cannot be avoided in the calculations of any calendar algorithm.

There are no explicit divisions or subtractions in our doomsyear formula. However, there are implicit divisions and subtractions needed when one is figuring out the leap year correction term and when one is doing a modulo 7 operation afterwards. Nevertheless, all doomsyear acceleration methods require these implicit divisions and subtractions!

Let's calculate the doomsyear term for these years:

1) 1974: y = 7, z = 4

leap = 1 because 1972 is a leap year

doomsyear = 2*7 + 3*1 + 4 + leap = 14 + 3 + 4 + 1 = 22 = 1 (mod 7)

2) 2040: y = 4, z= 0

leap = 0

doomsyear = 2*4 + 3*0 + 0 + leap = 8 + 0 + 0 + 0 = 1 (mod 7)

3) 2010: y = 1, z = 0

leap = 0

doomsyear = 2*1 + 3*1 + 0 + leap = 2 + 3 + 0 + 0 = 5 (mod 7)

4) 1988: y = 8, z= 8

leap = 2 because 1984 and 1988 are leap years

doomsyear = 2*8 + 3*0 + 8 + leap = 16 + 0 + 8 + 2 = 26 = 5 (mod 7)

5) 2007: y = 0, z= 7

leap = 1 because 2004 is a leap year

doomsyear = 2*0 + 3*0 + 7 + leap = 0 + 0 + 7 + 1 = 8 = 1 (mod 7)

6) 1998: y = 9, z=8

leap = 2 because 1992 and 1996 are leap years

doomsyear = 2*9 + 3*1 + 8 + leap = 18 + 3 + 8 + 2 = 31 = 3 (mod 7)

Memorization and Lookup Tables

Let’s define the decade anchor to be the “(2y + 3 (y mod 2))” subexpression of the doomsyear term. This subexpression only depends on the y decade of the input year.

decade_anchor(y) = ( 2 y + 3 (y mod 2) ) mod 7

By virtue of memorizing the decade anchor for each decade, one can significantly speed-up the calculation of the doomsyear term. This memorization is, of course, optional. Here is the table to memorize:

If one memorizes this simple table of 10 numbers, one can avoid calculating the decade anchor “2y + 3 (y mod 2)” component of the doomsyear formula. The doomsyear formula is thus:

doomsyear(y,z) = decade_anchor(y) + z + leap

An important mnemonic that can aid in memorizing this table involves the observation of its clamping effect. That is, for the starting and ending decades of the 00’s and the 90’s, the decade anchor is 0. Thus, one only really needs to memorize 8 numbers when using this decade anchor lookup table acceleration trick.

Look Before You Leap

There are several tricks to make the calculation of the leap term easier. Let’s look at a table of possible values for the leap term depending on the digit year z:

One can easily see that for digit years 0 and 1, the leap value is always 0. Likewise, for the digit years 8 and 9, the leap value is always 2; and for the digit years 4 and 5, the leap value is always 1. So, we only really need to do leap year calculations when the digit year is 2, 3, 6, or 7. Furthermore, if one checks whether the decade is odd or even, leap year determination can be totally avoided at the expense of more memorization.

Lucky Number 7

Another tip for the calculation of the doomsyear term involves the observation that 7 = 0 in modulo 7 arithmetic. So the z term in the doomsyear formula can be dropped altogether for the years 07, 17, 27, 37, 47 etc.

References:

[1] Mark Alpert, ”Not Just Fun and Games”, Scientific American, April 1999.

[2] Wikipedia contributors, ”Doomsday Rule”, Wikipedia, The Free Encyclopedia.

[3] Rudy Limeback, “Doomsday Algorithm”,

http://rudy.ca/doomsday.html

[4] Richard Guy, John Horton Conway, Elwyn Berlekamp : "Winning Ways: For Your Mathematical Plays, Volume. 2: Games in Particular", Academic Press, London, 1982

[5] Sidney Graham, “Doomsday Rule”,

http://www.cst.cmich.edu/users/graha1sw/Pub/Doomsday/DoomsdayIntro.html

[6] Mike Walters, “An Easier Doomsday Algorithm”, Blogspot blog

http://easydoomsday.blogspot.com/

[7] Bob Goddard, “First Sunday Doomsday Algorithm”, Blogspot blog

http://firstsundaydoomsday.blogspot.com/

Let us look at table 3 once again and observe some properties of the doomsyear term.

Property#1 Non-Leap-Year Increment

We can see from table 3 that the doomsyear increases by 1 for every non-leap year. This follows from the fact that 365 = 1 (mod 7); and the day of the week increases by one after each non-leap year.

Property#2 Leap-Year Increment

We can also see from table 3 that the doomsyear increases by 2 for every leap year. This follows from the fact that 366 = 2 (mod 7); and the day of the week increases by two after each leap year.

Property#3 Periodicity

The days of the week repeat with a period of 7. The leap years within a century repeat with a period of 4. It is no surprise that doomsyear values repeat every 28 years. 28 is, of course, the least common multiple of 7 and 4.

Property#4 Quasi-periodicity

We can observe from table 3 that the doomsyear value almost repeats a count of 0 to 6 every 5 or 6 years except for regular jumps occuring every leap year.We can call this property as quasi-periodicity.

John Horton Conway devised an acceleration method to avoid explicit calculation of the doomsyear term. In practice, Conway’s method is probably the fastest acceleration method for such, but it involves memorizing 18 numbers and some non-intuitive rules. In this section, we will describe Conway’s look-up table method. In the next section, we will compare and contrast our method with Conway’s acceleration method.

Conway’s lookup table method requires memorizing the years of the century where the doomsyear value is zero. Let us call these numbers as zero-anchor years. These are:

0, 6, 11.5, 17, 23, 28, 34, 39.5, 45

51, 56, 62, 67.5, 73, 79, 84, 90, 95.5

There’s actually the added complication of the half-numbers: 11.5, 39.5, 67.5 and 95.5. These half-numbers mean that the preceding year has doomsyear value 6 and the succeeding year has doomsyear value 1. For example, doomsyear(11) = 6, and doomsyear(12) = 1; doomsyear(67) = 6, and doomsyear(68) = 1. These half-numbers occur because of the increment-by-2 property of doomsyear values during leap years. In effect, a doomsyear of value 0 got skipped in the half-number locations.

The gist of Conway’s acceleration method is to find the nearest zero-anchor year to your input year. Afterwards, subtract the zero-anchor year from your input year and add a leap year correction to get the doomsyear value For this section, we will restrict the zero-anchor to be the less than your input year. It is actually possible to select a zero-anchor greater than your input year, but it requires remembering some additional rules when dealing with leap years and half-numbers. This is tricky and error-prone, so we will not cover it.

Here are the steps of Conway’s acceleration method:

**Examples**Let's calculate the doomsyear term for these years:

1) 1974: y = 7, z = 4

leap = 1 because 1972 is a leap year

doomsyear = 2*7 + 3*1 + 4 + leap = 14 + 3 + 4 + 1 = 22 = 1 (mod 7)

2) 2040: y = 4, z= 0

leap = 0

doomsyear = 2*4 + 3*0 + 0 + leap = 8 + 0 + 0 + 0 = 1 (mod 7)

3) 2010: y = 1, z = 0

leap = 0

doomsyear = 2*1 + 3*1 + 0 + leap = 2 + 3 + 0 + 0 = 5 (mod 7)

4) 1988: y = 8, z= 8

leap = 2 because 1984 and 1988 are leap years

doomsyear = 2*8 + 3*0 + 8 + leap = 16 + 0 + 8 + 2 = 26 = 5 (mod 7)

5) 2007: y = 0, z= 7

leap = 1 because 2004 is a leap year

doomsyear = 2*0 + 3*0 + 7 + leap = 0 + 0 + 7 + 1 = 8 = 1 (mod 7)

6) 1998: y = 9, z=8

leap = 2 because 1992 and 1996 are leap years

doomsyear = 2*9 + 3*1 + 8 + leap = 18 + 3 + 8 + 2 = 31 = 3 (mod 7)

**Tips and Tricks**Memorization and Lookup Tables

Let’s define the decade anchor to be the “(2y + 3 (y mod 2))” subexpression of the doomsyear term. This subexpression only depends on the y decade of the input year.

decade_anchor(y) = ( 2 y + 3 (y mod 2) ) mod 7

By virtue of memorizing the decade anchor for each decade, one can significantly speed-up the calculation of the doomsyear term. This memorization is, of course, optional. Here is the table to memorize:

If one memorizes this simple table of 10 numbers, one can avoid calculating the decade anchor “2y + 3 (y mod 2)” component of the doomsyear formula. The doomsyear formula is thus:

doomsyear(y,z) = decade_anchor(y) + z + leap

An important mnemonic that can aid in memorizing this table involves the observation of its clamping effect. That is, for the starting and ending decades of the 00’s and the 90’s, the decade anchor is 0. Thus, one only really needs to memorize 8 numbers when using this decade anchor lookup table acceleration trick.

Look Before You Leap

There are several tricks to make the calculation of the leap term easier. Let’s look at a table of possible values for the leap term depending on the digit year z:

One can easily see that for digit years 0 and 1, the leap value is always 0. Likewise, for the digit years 8 and 9, the leap value is always 2; and for the digit years 4 and 5, the leap value is always 1. So, we only really need to do leap year calculations when the digit year is 2, 3, 6, or 7. Furthermore, if one checks whether the decade is odd or even, leap year determination can be totally avoided at the expense of more memorization.

Lucky Number 7

Another tip for the calculation of the doomsyear term involves the observation that 7 = 0 in modulo 7 arithmetic. So the z term in the doomsyear formula can be dropped altogether for the years 07, 17, 27, 37, 47 etc.

**Conclusion**We presented an acceleration method for calculating the doomsyear term of the Doomsday rule. Our method is simple because it only involves additions and a multiplication by 2. Furthermore, we provided further tips and tricks that can give additional speed to our method. In the appendix section of this paper, we show that our acceleration method method is similar in form to Conway’s lookup table acceleration method, but requires less memorization.

References:

[1] Mark Alpert, ”Not Just Fun and Games”, Scientific American, April 1999.

[2] Wikipedia contributors, ”Doomsday Rule”, Wikipedia, The Free Encyclopedia.

[3] Rudy Limeback, “Doomsday Algorithm”,

http://rudy.ca/doomsday.html

[4] Richard Guy, John Horton Conway, Elwyn Berlekamp : "Winning Ways: For Your Mathematical Plays, Volume. 2: Games in Particular", Academic Press, London, 1982

[5] Sidney Graham, “Doomsday Rule”,

http://www.cst.cmich.edu/users/graha1sw/Pub/Doomsday/DoomsdayIntro.html

[6] Mike Walters, “An Easier Doomsday Algorithm”, Blogspot blog

http://easydoomsday.blogspot.com/

[7] Bob Goddard, “First Sunday Doomsday Algorithm”, Blogspot blog

http://firstsundaydoomsday.blogspot.com/

**Appendix 1: Some Doomsyear Properties**

Let us look at table 3 once again and observe some properties of the doomsyear term.

Property#1 Non-Leap-Year Increment

We can see from table 3 that the doomsyear increases by 1 for every non-leap year. This follows from the fact that 365 = 1 (mod 7); and the day of the week increases by one after each non-leap year.

Property#2 Leap-Year Increment

We can also see from table 3 that the doomsyear increases by 2 for every leap year. This follows from the fact that 366 = 2 (mod 7); and the day of the week increases by two after each leap year.

Property#3 Periodicity

The days of the week repeat with a period of 7. The leap years within a century repeat with a period of 4. It is no surprise that doomsyear values repeat every 28 years. 28 is, of course, the least common multiple of 7 and 4.

Property#4 Quasi-periodicity

We can observe from table 3 that the doomsyear value almost repeats a count of 0 to 6 every 5 or 6 years except for regular jumps occuring every leap year.We can call this property as quasi-periodicity.

**Appendix 2: Conway’s Look-up Table Acceleration Method**

John Horton Conway devised an acceleration method to avoid explicit calculation of the doomsyear term. In practice, Conway’s method is probably the fastest acceleration method for such, but it involves memorizing 18 numbers and some non-intuitive rules. In this section, we will describe Conway’s look-up table method. In the next section, we will compare and contrast our method with Conway’s acceleration method.

Conway’s lookup table method requires memorizing the years of the century where the doomsyear value is zero. Let us call these numbers as zero-anchor years. These are:

0, 6, 11.5, 17, 23, 28, 34, 39.5, 45

51, 56, 62, 67.5, 73, 79, 84, 90, 95.5

There’s actually the added complication of the half-numbers: 11.5, 39.5, 67.5 and 95.5. These half-numbers mean that the preceding year has doomsyear value 6 and the succeeding year has doomsyear value 1. For example, doomsyear(11) = 6, and doomsyear(12) = 1; doomsyear(67) = 6, and doomsyear(68) = 1. These half-numbers occur because of the increment-by-2 property of doomsyear values during leap years. In effect, a doomsyear of value 0 got skipped in the half-number locations.

The gist of Conway’s acceleration method is to find the nearest zero-anchor year to your input year. Afterwards, subtract the zero-anchor year from your input year and add a leap year correction to get the doomsyear value For this section, we will restrict the zero-anchor to be the less than your input year. It is actually possible to select a zero-anchor greater than your input year, but it requires remembering some additional rules when dealing with leap years and half-numbers. This is tricky and error-prone, so we will not cover it.

Here are the steps of Conway’s acceleration method:

1) Select the nearest zero-anchor year less than your input year.

2) Let z0 be the difference between your input year and the selected zero-anchor. Ignore fractional values of half-numbers in zero-anchor years. That is, treat 11.5, 39.5, 67.5, and 95.5 as 11, 39, 67, and 95 respectively in calculating the difference

3) Count the number of leap years between the zero-anchor and your input year. If the zero-anchor year is a leap year, do not include it. On the other hand, if your input year is a leap year, include it in the leap count. Let us denote this count of leap years as leap0

4) Add z0 and leap0 to get the doomsyear value. If the selected zero-anchor is a half-number, subtract 1 from the sum. We denote this as the anchor adjustment term needed for half-number zero-anchors.

To sum it all up, Conway’s acceleration method can be described by the equation:

doomsyear = anchor_adjustment + z0 + leap0

Note that the anchor_anjustment term is almost always zero except for half-number years where it has a value of –1.

Examples:

1) 1974:

zero-anchor is 1973

z0 = 1974 – 1973 = 1

leap0 = 0

doomsyear = 1 + 0 = 1

2) 2040:

zero-anchor is 2039.5

z0 = 2040 – 2039 = 1

leap0 =1 because 2040 is a leap year

doomsyear = -1 + 1 + 1 = 1

3) 2010:

zero-anchor is 2006

z0 = 2010 – 2006 = 4

leap0 = 1 because 2008 is a leap year

doomsyear = 4 + 1 = 5

4) 1988:

zero-anchor is 1984

z0 = 1988 – 1984 = 4

leap0 = 1 because 1988 is a leap year. Remember, we don’t count the zero-anchor

doomsyear = 4 + 1 = 5

5) 2007:

zero-anchor is 2006

z0 = 2007 – 2006 = 1

leap0 = 0

doomsyear = 1 + 0 = 1

6) 1998:

zero-anchor is 1995.5

z0 = 1998 – 1995 = 3

leap0 = 1 because 1996 is a leap year

doomsyear = -1 + 3 + 1 = 3

7) 1914:

zero-anchor is 1911.5

z0 = 1914– 1911 = 3

leap0 = 1 because 1912is a leap year

doomsyear = -1 + 3 + 1 = 3

8) 1972:

zero-anchor is 1967.5

z0 = 1972 – 1967 = 5

leap0 = 2 because 1968 and 1972 are leap years

doomsyear = -1 + 5 + 2 = 6

As we mentioned in the tips and tricks section, our method is amenable to lookup table acceleration. In fact, we claim that after this lookup table acceleration, our method is very similar to Conway’s acceleration method. Let us compare and contrast the doomsyear equation for our method and Conway’s method. These are:

doomsyear(y,z) = decade_anchor(y) + z + leap

and

doomsyear(x) = anchor_adjustment(x) + z0 + leap0

respectively. We have carefully named different terms of the equations to highlight the similarities between both equations. Let us list down these similarities.

1) Both equations are the sum of 3 terms. Each of these terms correspond with a counterpart in the other method.

2) Both equations use memorization of an anchor year for the speedup. In our method, the starting year of the decade serves as the anchor. In Conway’s method, years with doomsyear value of zero are used as the anchor.

3) Both equations use z as the number of years between the input year and the anchor year.

4) Both equations contain a leap count correction term that counts the number of leap years between the anchor year and the input year.

We now list down differences between the 2 equations and mention some advantages of our method over Conway’s method.

1) In our method, z is not computed. It is part of the input. In Conway’s method, z0 has to be calculated by subtracting the zero-anchor year from the input year.

2) In our method, one has to memorize 10 digits for the anchoring. In Conway’s method, one has to memorize 18 numbers for the anchoring.

3) In our method, the leap count correction term follows a regular pattern for a given decade and is amenable to another speedup via memorization.

4) In our method, one can always fall back to using the “2y + 3 (y mod 2)” calculation if entries in the lookup table are forgotten.

2) Let z0 be the difference between your input year and the selected zero-anchor. Ignore fractional values of half-numbers in zero-anchor years. That is, treat 11.5, 39.5, 67.5, and 95.5 as 11, 39, 67, and 95 respectively in calculating the difference

3) Count the number of leap years between the zero-anchor and your input year. If the zero-anchor year is a leap year, do not include it. On the other hand, if your input year is a leap year, include it in the leap count. Let us denote this count of leap years as leap0

4) Add z0 and leap0 to get the doomsyear value. If the selected zero-anchor is a half-number, subtract 1 from the sum. We denote this as the anchor adjustment term needed for half-number zero-anchors.

To sum it all up, Conway’s acceleration method can be described by the equation:

doomsyear = anchor_adjustment + z0 + leap0

Note that the anchor_anjustment term is almost always zero except for half-number years where it has a value of –1.

Examples:

1) 1974:

zero-anchor is 1973

z0 = 1974 – 1973 = 1

leap0 = 0

doomsyear = 1 + 0 = 1

2) 2040:

zero-anchor is 2039.5

z0 = 2040 – 2039 = 1

leap0 =1 because 2040 is a leap year

doomsyear = -1 + 1 + 1 = 1

3) 2010:

zero-anchor is 2006

z0 = 2010 – 2006 = 4

leap0 = 1 because 2008 is a leap year

doomsyear = 4 + 1 = 5

4) 1988:

zero-anchor is 1984

z0 = 1988 – 1984 = 4

leap0 = 1 because 1988 is a leap year. Remember, we don’t count the zero-anchor

doomsyear = 4 + 1 = 5

5) 2007:

zero-anchor is 2006

z0 = 2007 – 2006 = 1

leap0 = 0

doomsyear = 1 + 0 = 1

6) 1998:

zero-anchor is 1995.5

z0 = 1998 – 1995 = 3

leap0 = 1 because 1996 is a leap year

doomsyear = -1 + 3 + 1 = 3

7) 1914:

zero-anchor is 1911.5

z0 = 1914– 1911 = 3

leap0 = 1 because 1912is a leap year

doomsyear = -1 + 3 + 1 = 3

8) 1972:

zero-anchor is 1967.5

z0 = 1972 – 1967 = 5

leap0 = 2 because 1968 and 1972 are leap years

doomsyear = -1 + 5 + 2 = 6

**Appendix 3: A Comparison of Our Acceleration Method with Conway’s**As we mentioned in the tips and tricks section, our method is amenable to lookup table acceleration. In fact, we claim that after this lookup table acceleration, our method is very similar to Conway’s acceleration method. Let us compare and contrast the doomsyear equation for our method and Conway’s method. These are:

doomsyear(y,z) = decade_anchor(y) + z + leap

and

doomsyear(x) = anchor_adjustment(x) + z0 + leap0

respectively. We have carefully named different terms of the equations to highlight the similarities between both equations. Let us list down these similarities.

1) Both equations are the sum of 3 terms. Each of these terms correspond with a counterpart in the other method.

2) Both equations use memorization of an anchor year for the speedup. In our method, the starting year of the decade serves as the anchor. In Conway’s method, years with doomsyear value of zero are used as the anchor.

3) Both equations use z as the number of years between the input year and the anchor year.

4) Both equations contain a leap count correction term that counts the number of leap years between the anchor year and the input year.

We now list down differences between the 2 equations and mention some advantages of our method over Conway’s method.

1) In our method, z is not computed. It is part of the input. In Conway’s method, z0 has to be calculated by subtracting the zero-anchor year from the input year.

2) In our method, one has to memorize 10 digits for the anchoring. In Conway’s method, one has to memorize 18 numbers for the anchoring.

3) In our method, the leap count correction term follows a regular pattern for a given decade and is amenable to another speedup via memorization.

4) In our method, one can always fall back to using the “2y + 3 (y mod 2)” calculation if entries in the lookup table are forgotten.

Subscribe to:
Posts (Atom)