I can't readily think of an application in which this is a performance-critical computation, so I'd be tempted to optimise for size, but in the more general sense of "how to quickly obtain the modulus of dividing by 7", this becomes a much more practical use.
Excellent article, and very useful for programming. For figuring out the day of the week in your head, there's a different (and very useful) trick. It uses the month and day from the Gregorian calendar, rather than the day number, because 99% of the time that's what you'll be wanting: "Which day of the week will August 31st, 2026 be?"
The trick is to notice that in any year, leap year or not, the following dates will be the same day of the week in any year: 4/4, 6/6, 8/8, 10/10, and 12/12. (Whether you use the month/day style favored in America, or the day/month style that the rest of the world uses, either way those dates are the same, which is convenient). Which day of the week those dates are will vary from year to year: this year (2026) those are all Saturdays, last year they were all Fridays, next year they will all be Sundays. But in any given year, those dates are separated by 63 days, a multiple of seven, so they are always going to be the same day of the week.
And that's not all: look at 5/9, 9/5, 7/11, and 11/7 — those are also that same day of the week! (Again, conveniently, this works whether you're using the American calendar style or the rest of the world). Those odd-numbered dates can easily be remembered with the mnemonic phrase "a 9-to-5 job at 7-11". And voila, you have memorized one "special" day in nine of the twelve months. (What you do for January, February, and March I will cover later).
Now I'll pause and explain why this is useful. Many of you have already made the intuitive leap to figure this out, but it's still useful to see it spelled out. If you're trying to figure out what day of the week a certain date, let's say August 31st, is going to be, then you find the "key" date for that month (August 8th), and remember that this year, those key dates are Saturdays. (I don't yet have a good mnemonic for easily remembering which key date is which for each year; I'd welcome suggestions if you can think of one). So, 8/8 was a Saturday. Therefore, August 15th and 22nd and 29th are Saturdays. Therefore, August 31st will be a Monday this year. All of that is math you can easily do in your head in seconds.
Now, January, February, and March. March is always the same in every year: March 7th. 14th, 21st, and 28th are the "key days" that are the same day as 4/4 et al. But the way I prefer to memorize March is that "March 0th" (which isn't actually in March, it's the last day of February) is the "key day". That still lets me do the mental math for March easily enough, but it also reminds me that Feburary 28th or 29th, depending on whether you're in a leap year, is the "key day" for this year. Finally, for January, I use January 3rd in non-leap-years and January 4th in leap years as the "key day" that I memorize; the number 4 is strongly associated with leap years, so "leap year = January 4th" is easy to memorize, and I just have to remember that it's one day less in non-leap-years, January 3rd.
And so I just have to memorize "January 3rd or 4th" and "March 0th", plus the phrase "a 9-to-5 job at 7-11". And I can easily figure out in my head what day of the week any day of the year will be. For example, December 25th will be a Friday this year: that took me three seconds to work out in my head without looking at a calendar.
Wow, this is fantastic! That's what I expected from the original article! Instead it "merely" presented a quick signed-mod-7 trick for 32- and 64-bit architectures. Interesting, but given day/month/year is what I actually face and your trick here is exactly what I was looking for! Thanks so much, I'll use this the rest of my life!
For keeping track of the "key day of the week" from year to year: as you move forward through the years, it advances by one when you move into a non-leap-year, and advances by 2 when you move into a leap year. This year (2026) those days are all Saturdays. Next year, 2027, they will all be Sundays. And in 2028 those days will all be Tuesdays. (If 2028 were not a leap year than they would be Mondays, but since 2028-04-04 is 366 days away from 2027-04-04 due to 2028-02-29 being added in, that's two more than the nearest multiple of 7 (364) and therefore the "key day" advances by 2).
As I said, I don't have a good mnemonic worked out yet for remembering which "key day of the week" goes with which year. But the human mind remembers trauma, and I will probably never forget that September 11, 2001 was a Tuesday. (I clearly remember arriving at work and being asked "Did you hear about the plane crashes?" — both had happened during my 30-minute walk to the office). Which gives me a fixed point I can always calculate from: September 4th, 2001 was a Tuesday, so September 5th was a Wednesday. That means 2001's key day of the week was a Wednesday, and then I can work forward from there: 2002 = Thu, 2003 Fri, 2004 Sun. Then I can add five days for every four years: 2008 Fri, 2012 Wed, 2016 Mon, 2020 Sat, 2024 Thu. Then 2025 Fri, 2026 Sat, and I'm back to current year.
That's not a great mnemomic, because it takes me quite a while to work back up to the current year from 2001. If anyone can think of a better mnemonic, please let me know.
My comment isn't really about the content itself but... this is what I want the web to be. Documents that take advantage being on the web (visualizations, interactivity) while still remaining structured and simple. I really like the overall visual style too, incredible work. /glaze
Thanks! I'm pretty sure with this one I spent more time working on the blog post than I did developing the algorithms.
I would not normally spend such effort, but in this case I felt that the functions were too hard to understand without the visual aid, and too difficult to customise without the Function Explorer.
Then I think I just got a bit carried away with the detail.
The theory is trivial for anyone with a Number Theory background. That's not the point. Picking a good and interesting problem and going all the way to an elegant optimal solution, AND presenting it well, is all that counts. Without the good presentation and proof, it could look like a hack / weird trick to a random reviewer. I have personally seen a few good algorithms of this sort being dismissed in codebases because they were hard for people to understand (or more precisely, the author hadn't been skilled / diligent enough to leave a good demonstration linked in the code).
I wish there was a place for good algorithms like this, where, unlike plain wikipedia, the good visualized proof could stay and serve. Or perhaps there are such places and I don't know about them.
Bret Victor did a bunch of work around visualizations ~12 years ago (IIRC) for teaching and showing math, but I am not sure if there was any following on that path.
I can't readily think of an application in which this is a performance-critical computation, so I'd be tempted to optimise for size, but in the more general sense of "how to quickly obtain the modulus of dividing by 7", this becomes a much more practical use.
Excellent article, and very useful for programming. For figuring out the day of the week in your head, there's a different (and very useful) trick. It uses the month and day from the Gregorian calendar, rather than the day number, because 99% of the time that's what you'll be wanting: "Which day of the week will August 31st, 2026 be?"
The trick is to notice that in any year, leap year or not, the following dates will be the same day of the week in any year: 4/4, 6/6, 8/8, 10/10, and 12/12. (Whether you use the month/day style favored in America, or the day/month style that the rest of the world uses, either way those dates are the same, which is convenient). Which day of the week those dates are will vary from year to year: this year (2026) those are all Saturdays, last year they were all Fridays, next year they will all be Sundays. But in any given year, those dates are separated by 63 days, a multiple of seven, so they are always going to be the same day of the week.
And that's not all: look at 5/9, 9/5, 7/11, and 11/7 — those are also that same day of the week! (Again, conveniently, this works whether you're using the American calendar style or the rest of the world). Those odd-numbered dates can easily be remembered with the mnemonic phrase "a 9-to-5 job at 7-11". And voila, you have memorized one "special" day in nine of the twelve months. (What you do for January, February, and March I will cover later).
Now I'll pause and explain why this is useful. Many of you have already made the intuitive leap to figure this out, but it's still useful to see it spelled out. If you're trying to figure out what day of the week a certain date, let's say August 31st, is going to be, then you find the "key" date for that month (August 8th), and remember that this year, those key dates are Saturdays. (I don't yet have a good mnemonic for easily remembering which key date is which for each year; I'd welcome suggestions if you can think of one). So, 8/8 was a Saturday. Therefore, August 15th and 22nd and 29th are Saturdays. Therefore, August 31st will be a Monday this year. All of that is math you can easily do in your head in seconds.
Now, January, February, and March. March is always the same in every year: March 7th. 14th, 21st, and 28th are the "key days" that are the same day as 4/4 et al. But the way I prefer to memorize March is that "March 0th" (which isn't actually in March, it's the last day of February) is the "key day". That still lets me do the mental math for March easily enough, but it also reminds me that Feburary 28th or 29th, depending on whether you're in a leap year, is the "key day" for this year. Finally, for January, I use January 3rd in non-leap-years and January 4th in leap years as the "key day" that I memorize; the number 4 is strongly associated with leap years, so "leap year = January 4th" is easy to memorize, and I just have to remember that it's one day less in non-leap-years, January 3rd.
And so I just have to memorize "January 3rd or 4th" and "March 0th", plus the phrase "a 9-to-5 job at 7-11". And I can easily figure out in my head what day of the week any day of the year will be. For example, December 25th will be a Friday this year: that took me three seconds to work out in my head without looking at a calendar.
Wow, this is fantastic! That's what I expected from the original article! Instead it "merely" presented a quick signed-mod-7 trick for 32- and 64-bit architectures. Interesting, but given day/month/year is what I actually face and your trick here is exactly what I was looking for! Thanks so much, I'll use this the rest of my life!
For keeping track of the "key day of the week" from year to year: as you move forward through the years, it advances by one when you move into a non-leap-year, and advances by 2 when you move into a leap year. This year (2026) those days are all Saturdays. Next year, 2027, they will all be Sundays. And in 2028 those days will all be Tuesdays. (If 2028 were not a leap year than they would be Mondays, but since 2028-04-04 is 366 days away from 2027-04-04 due to 2028-02-29 being added in, that's two more than the nearest multiple of 7 (364) and therefore the "key day" advances by 2).
As I said, I don't have a good mnemonic worked out yet for remembering which "key day of the week" goes with which year. But the human mind remembers trauma, and I will probably never forget that September 11, 2001 was a Tuesday. (I clearly remember arriving at work and being asked "Did you hear about the plane crashes?" — both had happened during my 30-minute walk to the office). Which gives me a fixed point I can always calculate from: September 4th, 2001 was a Tuesday, so September 5th was a Wednesday. That means 2001's key day of the week was a Wednesday, and then I can work forward from there: 2002 = Thu, 2003 Fri, 2004 Sun. Then I can add five days for every four years: 2008 Fri, 2012 Wed, 2016 Mon, 2020 Sat, 2024 Thu. Then 2025 Fri, 2026 Sat, and I'm back to current year.
That's not a great mnemomic, because it takes me quite a while to work back up to the current year from 2001. If anyone can think of a better mnemonic, please let me know.
My comment isn't really about the content itself but... this is what I want the web to be. Documents that take advantage being on the web (visualizations, interactivity) while still remaining structured and simple. I really like the overall visual style too, incredible work. /glaze
Thanks! I'm pretty sure with this one I spent more time working on the blog post than I did developing the algorithms.
I would not normally spend such effort, but in this case I felt that the functions were too hard to understand without the visual aid, and too difficult to customise without the Function Explorer.
Then I think I just got a bit carried away with the detail.
Thanks for putting in the effort.
You might also https://www.redblobgames.com/ and learn a lot from how they do their presentations.
The theory is trivial for anyone with a Number Theory background. That's not the point. Picking a good and interesting problem and going all the way to an elegant optimal solution, AND presenting it well, is all that counts. Without the good presentation and proof, it could look like a hack / weird trick to a random reviewer. I have personally seen a few good algorithms of this sort being dismissed in codebases because they were hard for people to understand (or more precisely, the author hadn't been skilled / diligent enough to leave a good demonstration linked in the code).
I wish there was a place for good algorithms like this, where, unlike plain wikipedia, the good visualized proof could stay and serve. Or perhaps there are such places and I don't know about them.
Bret Victor did a bunch of work around visualizations ~12 years ago (IIRC) for teaching and showing math, but I am not sure if there was any following on that path.
Seconded. Ben, you have a great teaching style, thank you for sharing this.
look up table?