5 ms·

I believe Zeller's Congruence had already solved this, no? Zeller's is based upon calculating the day of the week, but it also calculates days in the month and

I believe Zeller's Congruence had already solved this, no? Zeller's is based upon calculating the day of the week, but it also calculates days in the month and accounts for leap years. Plus, it's been around since the 19th century and is used in many major programming languages to calculate date (its implementation is sometimes a first year Comp Sci course project for introductory programming): http://en.wikipedia.org/wiki/Zeller%27s_congruence http://en.wikipedia.org/wiki/Zeller%27s_congruence For a programming example that does this same thing: https://github.com/mwhawkins/JavaZellers https://github.com/mwhawkins/JavaZellers How did this make the front page of HN being a problem which has already been solved and well documented for almost 200 years? Not to knock the author, as they put in some time apparently, but was just curious.

cristianpascu 12y ago
The age of the solution and number of people knowing about it... Well. :)
burkaman 12y ago
Well, a lot of people have never heard of Zeller's Congruence. Also, the process is kind of interesting, not just the result. That's why that article on deriving the fast inverse square root constant did well here, even though many people already know the result.
Iazel 12y ago
I can't find any way to calculate days in month using Zeller's Congruence °_° That's seems to calculate only the day of the month (and it's awesome!). Even the Java program use a fixed array to output the days in month! XD
tzs 12y ago
If you give up on February and just resign yourself to treating it as an exception, then the formula in the article, 30 + (x + [x/8])%2, is trivial to compute in your head. Zeller's Congruence is quite a bit harder to do in your head. For mental calculation of day of week, I use a method given in a Martin Gardner book, but this only works for 1900-1999. I'll give a fix to extend it to other centuries. Let Y be the last two digits of the year, let M be the month (1-12), and D be the day of the month (1-31). Let [X] denote the integer part of X. Compute w = [Y/12] + Y%12 + [Y%12/4] Compute w = w + month_offset(M), where month_offset is defined by this table: M month_offset 1 1 2 4 3 4 4 0 5 2 6 5 7 0 8 3 9 6 10 1 11 4 12 6 Compute w = w + D w%7 gives the day of the week, with Saturday being day 0. A couple notes. 1. You can reduce mod 7 as you go. For example, to get the day of the week of 1969-07-16, you could think "[69/12] = 5, add 9 (69%12) giving 14 == 0 mod 7. [9/4] = 2, so we are at 2. Add month_offset(7) == 0, giving 0. Add 16 (D), and we have 3 mod 7, so Wednesday". 2. Month_offset is easy to remember if you think of it this way: 1 4 4 0 2 5 0 3 6 1 4 6 That's 12^2, 5^2, 6^2, and 12^2+2. I don't know why that makes it easy, but Gardner suggested it, and I have not forgotten it in something like 40 years, even though I rarely use it. 3. If the year is a leap year, subtract 1 for dates in January and February. 4. For years in 2000-2099, subtract 1 from the result. For years in 1800-1899, add 2. If you forget what the century correction is, you can work it out in your head. For instance, to find the correction for 20xx, work out the day of week of 1999-12-31: 99=12x8+3, [3/4]=0, month_offset(12)=6, so 8+3+0+6+31==6 mod 7, or Friday. Now work out 2000-01-01 without a century correction: 0=0x12+0, [0/4]=0, month_offset(1)=1. 2000 is a leap year, so need to subtract 1 in January, so we have 0+0+0+0+1-1+1==1 mod 7, so Sunday. However, it should be Saturday since it comes after Friday, and so the century correction must be -1 for 20xx. 5. Gardner's method is really one of the other well known methods (I forget which one) adjusted to make mental calculation easier. Addendum: this is described in chapter 7, "Tricks of Lightning Calculators" from the Martin Gardner collection "Mathematical Carnival".
- anonetal 12y ago
  Regarding day of the week, this simple trick/observation seems surprisingly unknown (called Doomsday Rule: http://en.wikipedia.org/wiki/Doomsday_rule http://en.wikipedia.org/wiki/Doomsday_rule). In any year, 4/4, 6/6, 8/8, 10/10, 12/12 fall on the same day, so do 9/5, 5/9, 7/11, 11/7 (mnemonic: 9-to-5, 7-11). If you know what day that is for the year (Friday for 2014, Sat for 2015), you can quickly calculate the day of the week for many of the days. Jan/Feb/Mar require a little bit thought, but with practice reasonably quick.
chime 12y ago
> How did this make the front page of HN being a problem which has already been solved and well documented for almost 200 years? Not to knock the author, as they put in some time apparently, but was just curious. Zeller's Congruence is an algorithm. This is a formula. It made it to the front page because it was a clever hack and people like me love those.
- thaumasiotes 12y ago
  Zeller's Congruence is a formula as well (well, more than one depending on which calendar you want to use). Go look at the wikipedia article. More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. What distinction are you trying to draw?
  - JadeNB 12y ago
    > More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'. For example, what is the formula for the algorithm "on input `n`, output the first position in the decimal expansion of `pi` at which a copy of the decimal expansion of `n` begins"?
    - thaumasiotes 12y ago
      The fact that I can't tell you a formula doesn't mean there isn't one. For example, it's trivial for me to come up with input for that problem that you (or anyone else in the world) would be unable to solve. When the answers are unknown, I don't find it all that surprising that it's difficult to list or otherwise classify them. If you believe that f(x) = |x| is a "formula" giving the distance of a real number from zero, it's just as conditionally defined as (but less infinite than) the infinite lookup table you hypothesize. On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose.

cristianpascu 12y ago

The age of the solution and number of people knowing about it... Well. :)

burkaman 12y ago

Well, a lot of people have never heard of Zeller's Congruence. Also, the process is kind of interesting, not just the result. That's why that article on deriving the fast inverse square root constant did well here, even though many people already know the result.

Iazel 12y ago

I can't find any way to calculate days in month using Zeller's Congruence °_° That's seems to calculate only the day of the month (and it's awesome!). Even the Java program use a fixed array to output the days in month! XD

tzs 12y ago

If you give up on February and just resign yourself to treating it as an exception, then the formula in the article, 30 + (x + [x/8])%2, is trivial to compute in your head. Zeller's Congruence is quite a bit harder to do in your head. For mental calculation of day of week, I use a method given in a Martin Gardner book, but this only works for 1900-1999. I'll give a fix to extend it to other centuries. Let Y be the last two digits of the year, let M be the month (1-12), and D be the day of the month (1-31). Let [X] denote the integer part of X. Compute w = [Y/12] + Y%12 + [Y%12/4] Compute w = w + month_offset(M), where month_offset is defined by this table: M month_offset 1 1 2 4 3 4 4 0 5 2 6 5 7 0 8 3 9 6 10 1 11 4 12 6 Compute w = w + D w%7 gives the day of the week, with Saturday being day 0. A couple notes. 1. You can reduce mod 7 as you go. For example, to get the day of the week of 1969-07-16, you could think "[69/12] = 5, add 9 (69%12) giving 14 == 0 mod 7. [9/4] = 2, so we are at 2. Add month_offset(7) == 0, giving 0. Add 16 (D), and we have 3 mod 7, so Wednesday". 2. Month_offset is easy to remember if you think of it this way: 1 4 4 0 2 5 0 3 6 1 4 6 That's 12^2, 5^2, 6^2, and 12^2+2. I don't know why that makes it easy, but Gardner suggested it, and I have not forgotten it in something like 40 years, even though I rarely use it. 3. If the year is a leap year, subtract 1 for dates in January and February. 4. For years in 2000-2099, subtract 1 from the result. For years in 1800-1899, add 2. If you forget what the century correction is, you can work it out in your head. For instance, to find the correction for 20xx, work out the day of week of 1999-12-31: 99=12x8+3, [3/4]=0, month_offset(12)=6, so 8+3+0+6+31==6 mod 7, or Friday. Now work out 2000-01-01 without a century correction: 0=0x12+0, [0/4]=0, month_offset(1)=1. 2000 is a leap year, so need to subtract 1 in January, so we have 0+0+0+0+1-1+1==1 mod 7, so Sunday. However, it should be Saturday since it comes after Friday, and so the century correction must be -1 for 20xx. 5. Gardner's method is really one of the other well known methods (I forget which one) adjusted to make mental calculation easier. Addendum: this is described in chapter 7, "Tricks of Lightning Calculators" from the Martin Gardner collection "Mathematical Carnival".

anonetal 12y ago
Regarding day of the week, this simple trick/observation seems surprisingly unknown (called Doomsday Rule: http://en.wikipedia.org/wiki/Doomsday_rule http://en.wikipedia.org/wiki/Doomsday_rule). In any year, 4/4, 6/6, 8/8, 10/10, 12/12 fall on the same day, so do 9/5, 5/9, 7/11, 11/7 (mnemonic: 9-to-5, 7-11). If you know what day that is for the year (Friday for 2014, Sat for 2015), you can quickly calculate the day of the week for many of the days. Jan/Feb/Mar require a little bit thought, but with practice reasonably quick.

chime 12y ago

> How did this make the front page of HN being a problem which has already been solved and well documented for almost 200 years? Not to knock the author, as they put in some time apparently, but was just curious. Zeller's Congruence is an algorithm. This is a formula. It made it to the front page because it was a clever hack and people like me love those.

thaumasiotes 12y ago
Zeller's Congruence is a formula as well (well, more than one depending on which calendar you want to use). Go look at the wikipedia article. More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. What distinction are you trying to draw?
- JadeNB 12y ago
  > More seriously, any algorithm that doesn't do user I/O is expressible as a fixed formula. This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'. For example, what is the formula for the algorithm "on input `n`, output the first position in the decimal expansion of `pi` at which a copy of the decimal expansion of `n` begins"?
  - thaumasiotes 12y ago
    The fact that I can't tell you a formula doesn't mean there isn't one. For example, it's trivial for me to come up with input for that problem that you (or anyone else in the world) would be unable to solve. When the answers are unknown, I don't find it all that surprising that it's difficult to list or otherwise classify them. If you believe that f(x) = |x| is a "formula" giving the distance of a real number from zero, it's just as conditionally defined as (but less infinite than) the infinite lookup table you hypothesize. On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose.