notes.html

problem 45 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem asks me to find a number that appears simultaneously in three <a class="reference-source" href="https://en.wikipedia.org/wiki/Figurate_number" rel="noopener noreferrer" target="_blank">figurate number</a> sequences - triangular, pentagonal, and hexagonal. A <a class="reference-source" href="https://en.wikipedia.org/wiki/Figurate_number" rel="noopener noreferrer" target="_blank">figurate number</a> is one that can be arranged into a regular geometric shape, and each of the three sequences here has a closed-form <a class="reference-source" href="https://en.wikipedia.org/wiki/Quadratic_function" rel="noopener noreferrer" target="_blank">quadratic</a> generator: T(n) = n(n+1)/2, P(n) = n(3n-1)/2, and H(n) = n(2n-1). I am told that 40755 is the smallest such common value (after the trivial 1) and must find the next one. A brute-force scan that generates all three sequences and intersects them would work, but there is a much sharper structural observation to be had first.
</p>
<p>
The decisive insight is an algebraic identity: every hexagonal number is also triangular. Substitute m = 2n-1 into the triangular formula and you get T(2n-1) = (2n-1)(2n)/2 = n(2n-1) = H(n). In other words, the hexagonal numbers are exactly the triangular numbers with odd index, so any number that is hexagonal is automatically triangular. That collapses a three-way intersection into a two-way one: I only need values that are simultaneously triangular (or equivalently hexagonal) and pentagonal. To test pentagonal membership efficiently I invert the formula. Solving P(k) = x with the <a class="reference-source" href="https://en.wikipedia.org/wiki/Quadratic_formula" rel="noopener noreferrer" target="_blank">quadratic formula</a> gives k = (1 + sqrt(1 + 24x))/6, so x is pentagonal exactly when the <a class="reference-source" href="https://en.wikipedia.org/wiki/Discriminant" rel="noopener noreferrer" target="_blank">discriminant</a> 1 + 24x is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect square</a> whose root is congruent to 5 mod 6 (making k a positive integer). Each test is constant-time arithmetic plus one square root, so scanning candidate triangular numbers and testing each is O(k) where k is the number of candidates examined before a hit - a tiny count in practice.
</p>
<h3>Solution Approach</h3>
<h4>Analytical Inverse-Formula Check (Python and C)</h4>
<p>
Both files implement the same algorithm. I start from a supplied index n - 285, which is the index of the known solution T(285) = 40755 - and increment n by one each iteration. For each n I compute the triangular number T(n) = n(n+1)/2 and apply two membership filters.
</p>
<p>
The first filter tests whether T(n) is pentagonal. From the inverse k = (1 + sqrt(1 + 24x))/6, k is a positive integer precisely when 1 + sqrt(1+24x) is divisible by 6, which means sqrt(1+24x) must be congruent to 5 mod 6. The code checks this directly: <code>(1 + 24 * t) ** 0.5 % 6 == 5.0</code> in Python, and <code>fmod(sqrt(1 + 24*t), 6.0) != 5.0</code> in C. This one comparison implicitly verifies that the <a class="reference-source" href="https://en.wikipedia.org/wiki/Discriminant" rel="noopener noreferrer" target="_blank">discriminant</a> is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Square_number" rel="noopener noreferrer" target="_blank">perfect square</a> - if it were not, the floating-point remainder would not land exactly on 5.0.
</p>
<p>
The second filter tests triangularity using k = (-1 + sqrt(1 + 8x))/2, which requires sqrt(1+8x) to be congruent to 3 mod 4: <code>(1 + 8 * t) ** 0.5 % 4 == 3.0</code>. Strictly this second filter is redundant - I am already iterating over triangular numbers, so T(n) is triangular by construction - but it keeps the formulation symmetric, self-contained, and trivially correct, and it costs almost nothing. When both filters pass, the value is returned. The answer is 1533776805.
</p>
<p>
The language-specific differences are purely mechanical. C uses <code>fmod</code> from <code>&lt;math.h&gt;</code> for the floating-point remainder and structures the filters with explicit <code>continue</code> statements; Python uses <code>%</code> on floats and nests two <code>if</code> blocks. Both rely on <a class="reference-source" href="https://en.wikipedia.org/wiki/Double-precision_floating-point_format" rel="noopener noreferrer" target="_blank">IEEE 754 double precision</a> being exact for the integers involved (the answer is about 1.5 billion, well below 2^53), so the floating-point square roots are reliable.
</p>
</article>