tag:blogger.com,1999:blog-39852377095153178362017-03-25T07:09:39.717-07:00An Easier Doomsday AlgorithmThe Doomsday Algorithm is commonly used to mentally calculate the day of the week for any date. Here I describe an even easier way to find Doomsday for arbitrary years, which is simpler than the commonly described method.Mikehttp://www.blogger.com/profile/09902477043993196546noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3985237709515317836.post-61877952699121232492008-04-15T15:49:00.000-07:002009-03-26T18:10:45.732-07:00An Improved Doomsday Algorithm<p></p><p></p><h4>Introduction</h4>The Doomsday Algorithm can be used to mentally calculate the day of the week on which any date falls. With a little effort most people can learn to apply the algorithm mentally without pencil or paper. If you're interested, you can learn the method behind the Doomsday algorithm at <a href="http://rudy.ca/doomsday.html">rudy.ca</a> or at <a href="http://firstsundaydoomsday.blogspot.com/">Bob Goddard's site</a>.<br /><p></p><p>My purpose is not to describe the details of the Doomsday algorithm, but to describe an improved method to implement part of it (calculating Doomsday for an arbitrary year) which I have discovered. Below, I'll describe the method first using mathematical notation, which unfortunately appears needlessly complicated, but then I'll show how to easily perform the calculations mentally without the need for memorizing cumbersome equations.<br /></p><p></p><h4>Background</h4>First, a key component of using the Doomsday Algorithm is knowing how to calculate Doomsday for an arbitrary year, after which you can figure out the day of the week for any date in that year. The usual formula described to make this calculation can be written as<p></p><p style="font-family: courier new; text-align: center;">int(y/12) + y mod 12 + int((y mod 12)/4)</p><p>where y is the last two digits of the year. The notation "int (a/b)" means to take only the integer part of a/b; "a mod b" means to divide a by b and take the remainder. For example, int (4/3) = 1, and 10 mod 7 = 3.<br /></p><p>This result mod 7 is added to Doomsday for the base year of the century (e.g. 1900 or 2000) to get the final answer. For 1900, Doomsday is Wednesday (3, where Sunday is 0).</p><p>For example, Doomsday 1953 is</p><p style="font-family: courier new; text-align: center;">int(53/12) + 53 mod 12 + int ((53 mod 12)/4)</p><p style="text-align: center;"><span style="font-family:courier new;">= 4 + 5 + int(5/4) = 4 + 5 + 1 = 10 mod 7 = 3</span><br /></p><p>Adding 3 (Doomsday for 1900) to Wednesday gives Saturday.</p><p>This formula is not as bad as it looks, but it does require modular arithmetic, four divisions, and remembering three different numbers to add together. For me, this was always the most tedious part of applying the Doomsday algorithm.<br /></p><p></p><h4>An Easier Way!</h4>Fortunately I have discovered an easier way to make the same calculation with much less effort!<p></p><p>For a leap year only, my new simpler formula is</p><p style="font-family: courier new; text-align: center;">7 - (y/2) mod 7</p><p>where y is the last two digits of the year. This result is added to the Doomsday for the base century year as before.<br /></p><p>For example, for 1980 Doomsday is</p><p style="text-align: center;"><span style="font-family:courier new;">7 - (80/2) mod 7 = 7 - 40 mod 7 = 7 - 5 = 2</span>.<br /></p><p>Adding to Doomsday 1900, the final answer is 2 + Wednesday = Friday. While my formula is simpler than the original, it still involves some modular arithmetic and divisions. But there is a simple shortcut which makes applying the formula easy.<br /></p><p>Here's the trick: To apply this in practice mentally, you would simply divide the leap year by 2 and subtract the result from the next largest multiple of 7. No divisions by 12 or 4, no modular arithmetic, and less memory effort is needed. If you can divide an even number by 2 and add and subtract, you can do it quickly and easily.<br /></p><p>Even better: If the year is not a leap year, just repeatedly add 11 to the year until you get a leap year and apply the same formula. At most this will require adding 33 to the year.<br /></p><p></p><h4>Examples</h4>Returning to the first example, Doomsday 1953 is the same as Doomsday 1953 + 11 = Doomsday 1964.<p></p><p>Dividing 64 by 2, the result is 32 which subtracted from 35, the next multiple of 7 to give 3, the same as above. Added to Wednesday (Doomsday 1900) the result is again Saturday.<br /></p><p>Another example: 1962 is not a leap year, so we add 22 to get 1984. 84/2 = 42, which is a multiple of 7 so the result is 0 and Doomsday is Wednesday. (In this case the original formula might be easier since 84 is a multiple of 12). If you're familiar with the traditional method given above and my easier method, it is easy to apply the simplest one for any case, which I believe is usually the newer formula given here. I only find the older method easier if the year is a multiple of 12. I especially like the new method for finding the Doomsday of an odd year, which I always hated to do using the older method.<br /></p><p>Update: When the process of adding 11 takes you across a century boundary which is not a leap year (e.g. 1900 or 2100), the process is similar as pointed out by Robert Goddard in a comment to this post. As an example of crossing non leap year centuries, I'll use his example of 2095. We add 95+33=128. Since we crossed a non leap year (2100) use "128" instead of "28". We divide by 2 to get 64, and subtract from a big multiple of 7, to get 70-64=6. Added to Tuesday (Doomsday 2000, the century we started in) and the result is Monday. When crossing century years that are leap years, like 2000, the original method works without adjustment.<br /></p><p>It is easy to verify this method of adding 11 works by examining the following table which I have borrowed from <a href="http://rudy.ca/doomsday.html">rudy.ca</a>. In this table the leap years are bold. You can see that every leap year is the final year in a chain of 4 years which differ by 11 and which have the same Doomsday. Every non leap year is a member of such a chain. Because it is easy to find Doomsday for a leap year with my method, it is therefore simple to find Doomsday for any year.<br /></p><center><div><pre class="highlight"><strong> Sun Mon Tue Wed Thu Fri Sat</strong><br />---- ---- ---- 1900 1901 1902 1903<br />---- <strong>1904</strong> 1905 1906 1907 ---- <strong>1908</strong><br />1909 1910 1911 ---- <strong>1912</strong> 1913 1914<br />1915 ---- <strong>1916</strong> 1917 1918 1919 ----<br /><strong>1920</strong> 1921 1922 1923 ---- <strong>1924</strong> 1925<br />1926 1927 ---- <strong>1928</strong> 1929 1930 1931<br />---- <strong>1932</strong> 1933 1934 1935 ---- <strong>1936</strong><br />1937 1938 1939 ---- <strong>1940</strong> 1941 1942<br />1943 ---- <strong>1944</strong> 1945 1946 1947 ----<br /><strong>1948</strong> 1949 1950 1951 ---- <strong>1952</strong> 1953<br />1954 1955 ---- <strong>1956</strong> 1957 1958 1959<br />---- <strong>1960</strong> 1961 1962 1963 ---- <strong>1964</strong><br />1965 1966 1967 ---- <strong>1968</strong> 1969 1970<br />1971 ---- <strong>1972</strong> 1973 1974 1975 ----<br /><strong>1976</strong> 1977 1978 1979 ---- <strong>1980</strong> 1981<br />1982 1983 ---- <strong>1984</strong> 1985 1986 1987<br />---- <strong>1988</strong> 1989 1990 1991 ---- <strong>1992</strong><br />1993 1994 1995 ---- <strong>1996</strong> 1997 1998<br />1999 ---- <strong>2000</strong> ---- ---- ---- ----<br /></pre></div></center><div><p>Also, if you examine the table you will notice that the first year in a chain is always 6 more than another year with the same doomsday, the last year in a chain is 6 less than a year with the same doomsday, and the two years on either end are members of different chains. Understanding this relationship makes it very easy to come up with all the years in a century on which a certain date falls on the same day of the week.</p></div>Mikehttp://www.blogger.com/profile/09902477043993196546noreply@blogger.com13