147 lines
4.8 KiB
Plaintext
147 lines
4.8 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "819ff42e",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Counting Sundays](https://projecteuler.net/problem=19)\n",
|
|
"\n",
|
|
"Quick one-liner (with an import) does the trick."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "1483f1d8",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"171"
|
|
]
|
|
},
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"from calendar import weekday\n",
|
|
"\n",
|
|
"sum(1 for y in range(1901, 2001) for m in range(1, 13) if weekday(y, m, 1) == 6)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "5b91ad75",
|
|
"metadata": {},
|
|
"source": [
|
|
"But what if the standard library wasn't so generous?\n",
|
|
"\n",
|
|
"Here's a simple function to give us the number of days in any given month and year."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "0f09cadc",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def days_in_month(month, year):\n",
|
|
" key = {1: 31,\n",
|
|
" 2: 28,\n",
|
|
" 3: 31,\n",
|
|
" 4: 30,\n",
|
|
" 5: 31,\n",
|
|
" 6: 30,\n",
|
|
" 7: 31,\n",
|
|
" 8: 31,\n",
|
|
" 9: 30,\n",
|
|
" 10: 31,\n",
|
|
" 11: 30,\n",
|
|
" 12: 31}\n",
|
|
" \n",
|
|
" if year % 400 == 0 or (year % 4 == 0 and year % 100 != 0):\n",
|
|
" key[2] = 29\n",
|
|
" \n",
|
|
" return key[month]"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "1537a949",
|
|
"metadata": {},
|
|
"source": [
|
|
"Let's talk briefly about the days of the week. If someone asked you on a Monday what day it will be in eight days, you could naively count up (one day from now is Tuesday, two days from now is Wednesday, etc.), but it's quicker to observe that since the days of the week repeat every seven days, seven days from now will also be a Monday, and therefore eight days later is a Tuesday. Likewise, if someone wanted to know what day is 17 days from now, you know 14 days from now is also a Monday, so 17 (14+3) days later would be Thursday (3 days after Monday).\n",
|
|
"\n",
|
|
"Now, let's reframe this concept mathematically. Let's assign a number to every day of the week: Monday is 0, Tuesday is 1, and so on. Using [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic), we can add the number of days later to our day-number, then compute the remainder modulo 7 to find the day of our new date. Restating what we found above, if today is a Monday (0), we just add 17 and compute the remainder modulo 7 to see that 17 days from now will be Thursday (3). As a formula: if the day-number is $s$, the day it will be $n$ days later is $(s + n) \\bmod 7$.\n",
|
|
"\n",
|
|
"Knowing this, to find the day each month started on, we can just iterate through every month from 1900 through 2000, and each time add the length of the month to the day the last month started on, compute the modulus, and check if the result is 6, indicating that month started on a Sunday. (Note that the question gives us the starting day of 1900, but only asked about months from 1901 through 2000, so we'll take care to not add any months from 1900 that fell on a Sunday.)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "1c8f38fa",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"171\n"
|
|
]
|
|
}
|
|
],
|
|
"source": [
|
|
"total = 0\n",
|
|
"day = 0\n",
|
|
"for year in range(1900, 2001):\n",
|
|
" for month in range(1, 13):\n",
|
|
" day += days_in_month(month, year)\n",
|
|
" day %= 7\n",
|
|
" if day == 6 and year >= 1901:\n",
|
|
" total += 1\n",
|
|
"\n",
|
|
"print(total)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "83b6e18e",
|
|
"metadata": {},
|
|
"source": [
|
|
"One last note, just for fun: did you know you can learn how to calculate what day of the week any date falls on [in your head](https://en.wikipedia.org/wiki/Doomsday_rule)?\n",
|
|
"\n",
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 3
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython3",
|
|
"version": "3.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|