55 lines
2.8 KiB
Plaintext
55 lines
2.8 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "dee40daf",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Number Spiral Diagonals](https://projecteuler.net/problem=28)\n",
|
|
"\n",
|
|
"Whether you choose to program or just use pen and paper, there's a lot of different ways to tackle this problem. Here's one approach.\n",
|
|
"\n",
|
|
"If we have an $n \\times n$ spiral (note that $n$ must be odd!), it's pretty easy to get a formula for just the sum of the corners. The top right corner will always be $n^2$, and since it's an $n \\times n$ spiral (as mentioned one sentence ago), the top left corner will just be $n^2 - (n - 1)$. We can continue subtracting $n-1$ to get the values of the other corners. Adding these up, we get\n",
|
|
"$$f(n) = n^2 + (n^2 - (n-1)) + (n^2 - 2(n-1)) + (n^2 - 3(n-1)) = 4n^2 - 6n + 6$$\n",
|
|
"\n",
|
|
"Of course, we want the sums of the *diagonals*, not just the outermost corners. We can think about this as getting the sum of the corners of the $n \\times n$ spiral, plus the sum of the corners of the $(n-2) \\times (n-2)$ spiral one layer deeper, and so on until we reach the 1 at the center.\n",
|
|
"$$g(n) = f(n) + f(n-2) + f(n-4) + \\cdots + f(5) + f(3) + 1 = 1 + \\sum_{k=1}^{(n-1)/2} f(2k + 1) = 1 + \\sum_{k=1}^{(n-1)/2} (16k^2 + 4k + 4)$$\n",
|
|
"\n",
|
|
"Now we can apply [summation identities](https://en.wikipedia.org/wiki/Summation) (including the return of triangular numbers and square pyramidal numbers from [problem 6](https://projecteuler.net/problem=6)) to get a closed formula:\n",
|
|
"$$g(n) = \\frac{2}{3}n^3 + \\frac{1}{2}n^2 + \\frac{4}{3}n - \\frac{3}{2}$$\n",
|
|
"Plugging in 1001, we get our answer: $g(1001) = 669171001$.\n",
|
|
"\n",
|
|
"Side note: this practice of writing the natural numbers in a spiral, combined with marking the prime numbers, has been coined the [Ulam spiral](https://en.wikipedia.org/wiki/Ulam_spiral). Somewhat interestingly, lots of primes appear in vertical, horizontal, and diagonal lines when laid out this way.\n",
|
|
"\n",
|
|
"## Relevant sequences\n",
|
|
"* Numbers on diagonals: [A200975](https://oeis.org/A200975)\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
|
|
}
|