notes.html

problem 38 · 13 lines

<article>
<h3>Problem Analysis</h3>
<p>The task is to find the largest <a class="reference-source" href="https://en.wikipedia.org/wiki/Pandigital_number" rel="noopener noreferrer" target="_blank">1-to-9 pandigital</a> number - one that uses each of the digits 1 through 9 exactly once, and so is exactly nine digits long - that can be written as the concatenation of the products x*1, x*2, ..., x*n for some integer x and some n greater than 1. The phrase "concatenated product" is purely textual: we write out the decimal forms of the successive multiples side by side, with no arithmetic between them.</p>
<p>The observation that makes this tractable is a counting argument on digit lengths. The concatenation must total exactly nine digits, no more and no fewer. If x has k digits, then x*1 already contributes at least k digits, and each further multiple contributes at least k more. Since n must be at least 2, the products by 1 and 2 alone account for roughly 2k digits, so a 5-digit x is impossible (its double is at least five digits, giving at least ten total). This caps x at four digits. Each digit-length of x then pairs with a maximum n: a 4-digit x admits only (1,2); a 3-digit x admits (1,2,3); a 2-digit x admits up to (1,2,3,4); a single-digit x admits up to (1,...,9). The whole search therefore reduces to a few thousand candidates - effectively constant work, bounded by the largest x we test (9876). This is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Brute-force_search" rel="noopener noreferrer" target="_blank">brute-force search</a> made fast by mathematical pruning rather than by any clever data structure, with effective complexity O(X_max).</p>
<h3>Solution Approach</h3>
<h4>Bounded Descending Brute-Force Search (Python and C)</h4>
<p>Both p0038_s0.py and p0038_s0.c implement the same algorithm; I describe it once and note the language differences at the end.</p>
<p>I start from a static table of (n, max_x) pairs: <code>(2, 9876)</code>, <code>(3, 987)</code>, <code>(4, 98)</code>, <code>(5, 9)</code>, <code>(6, 9)</code>, <code>(7, 9)</code>, <code>(8, 9)</code>, <code>(9, 9)</code>. Each pair encodes the digit-count reasoning above: with n=2 the largest x worth trying is 9876 (a 4-digit value whose double is five digits, giving nine total); with n=3 a 3-digit x up to 987 yields 3+3+3=9 digits; and so on down to single-digit x for the larger n values. Baking the bounds into the table avoids recomputing them inside the loop and doubles as documentation of the case analysis.</p>
<p>For each pair I count x downward from its maximum to 1. For each x I build the concatenated product by converting x*1, x*2, ..., x*n to strings, joining them, and parsing the result back into an integer. I then test that integer with <code>is_nine_pandigital</code>. Because a larger x produces a larger concatenation within a fixed n, the first pandigital number I find for a given pair is automatically the largest for that pair. The pairs are ordered so the most promising case (n=2, which produces the largest values) is visited first, which lets me return on the first global hit. The answer 932718654 is the concatenated product of 9327 and (1,2): 9327*1 = 9327 and 9327*2 = 18654, concatenating to 932718654.</p>
<p>The validator <code>is_nine_pandigital</code> first applies a range guard, rejecting anything outside [100000000, 999999999], then walks the digits using a <a class="reference-source" href="https://en.wikipedia.org/wiki/Frequency_(statistics)" rel="noopener noreferrer" target="_blank">frequency</a> array <code>digits[10]</code>. It returns false on a zero digit or a repeat, and finally confirms that all nine non-zero slots are set exactly once.</p>
<p><strong>Language-specific details.</strong> In Python I build the concatenation with the idiom <code>int("".join([str(i * x) for i in range(1, n + 1)]))</code>, leaning on the language's effortless integer/string interconversion. In C I format each product into a temporary buffer with <code>snprintf</code>, append it to a fixed-size buffer with <code>strcat</code>, then convert the whole string with <code>atoll</code> into a <code>long long</code>. The C frequency array is a stack-allocated <code>int digits[10] = {0}</code>; the Python equivalent is <code>[0] * 10</code>. The two are logically equivalent.</p>
</article>