notes.html

problem 58 · 26 lines

<article>
<h3>Problem Analysis</h3>
<p>
The spiral picture is a deliberate distraction. What actually matters is a single arithmetic observation: each time I wrap one new layer around the centre, I add exactly four corner cells - one at each corner of the larger square - and these corners lie precisely on the two diagonals. If I index layers as <code>k = 1, 2, 3, ...</code>, the side length at layer <code>k</code> is <code>2k+1</code>, an odd number, and the bottom-right corner is always the odd square <code>(2k+1)^2</code>. This is because the spiral fills clockwise to the bottom-right and the largest value on a side-<code>(2k+1)</code> spiral is <code>(2k+1)^2</code>. The remaining three corners are reached by repeatedly subtracting <code>2k</code> (the side length minus one), since each edge of the square spans exactly that many cells between consecutive corners. So the entire diagonal sequence is a closed-form function of <code>k</code> - I never need to build or store the grid.
</p>
<p>
The real work is counting how many diagonal entries are <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> and watching when the running ratio of primes to total diagonal entries first drops below 10%. I test primality with <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a>: for a candidate <code>n</code>, I check divisibility by odd numbers up to <code>sqrt(n)</code>, costing <code>O(sqrt(n))</code> per test. The largest corner at the answer (side length 26241) is about <code>26241^2 ~ 6.9 * 10^8</code>, so each test does at most ~13000 divisor checks. I process roughly <code>n/2</code> layers, and a corner near layer <code>k</code> costs <code>O(k)</code> work, so the total is <code>O(n^2)</code> in the side length <code>n</code> - comfortably within a single linear pass, which is why this sits at Level 2. The bottom-right corner is an odd square (and thus never prime for <code>k &gt;= 1</code>), so I could skip it, but testing it uniformly is harmless.
</p>
<h3>Solution Approach</h3>
<h4>Layer-by-Layer Diagonal Scan (Python and C)</h4>
<p>
Both files implement the same algorithm; only the language idioms differ. The core loop walks layers from <code>k = 1</code> upward. For each layer I compute <code>side_length = 2k+1</code> and the step <code>side_length - 1 = 2k</code>. From the bottom-right corner <code>bottom_right = side_length^2</code> I derive the other three by successive subtraction:
</p>
<ul>
<li><code>bottom_left = bottom_right - step</code></li>
<li><code>top_left = bottom_left - step</code></li>
<li><code>top_right = top_left - step</code></li>
</ul>
<p>
I keep two running accumulators: <code>num_prime_diagonals</code> (starting at 0) and <code>num_diagonal_elements</code> (starting at 1, to count the centre cell 1, which lies on both diagonals but is not prime). Each layer adds 4 to the total and adds 1 per prime corner. After updating, I check whether the ratio has dropped below the threshold and, if so, return the current side length.
</p>
<p>
In Python I expressed layer enumeration as a <a class="reference-source" href="https://docs.python.org/3/glossary.html#term-generator" rel="noopener noreferrer" target="_blank">generator</a> that yields a 5-tuple <code>(side_length, bottom_right, bottom_left, top_left, top_right)</code>, and the <code>solve</code> function consumes it with a <code>for</code> loop. This separates "how to produce corners" from "when to stop". The C version is a direct port: an unbounded <code>for (int layer = 1; ; layer++)</code> with the same arithmetic. The crucial difference is type width. The corner values exceed the 32-bit signed range (~<code>2.1 * 10^9</code>) well before the answer, so the C code uses <code>long long</code> throughout the corner arithmetic to avoid silent overflow - note in particular <code>(long long)side_length * side_length</code>, which casts before multiplying so the squaring itself does not overflow. Both programs accept the threshold as a command-line argument so they can be re-run at other ratios.
</p>
</article>