notes.html

problem 41 · 21 lines

<article>
<h3>Problem Analysis</h3>
<p>
    An <em>n</em>-digit number is <a class="reference-source" href="https://en.wikipedia.org/wiki/Pandigital_number" rel="noopener noreferrer" target="_blank">pandigital</a> if it uses each of the digits 1 through <em>n</em> exactly once. I want the largest such number that is also <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a>. The brute-force formulation is clear: for every length from 1 to 9, generate every <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutation</a> of the digit set, test each for primality, and take the maximum. That is feasible - the largest length, 9, has only 9! = 362880 arrangements - but a single piece of number theory collapses almost all of the work before I write a search loop.
  </p>
<p>
    The decisive observation is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_3" rel="noopener noreferrer" target="_blank">divisibility rule for 3</a>: a number is divisible by 3 exactly when the sum of its digits is divisible by 3. For an <em>n</em>-digit pandigital number, the digit sum does not depend on the arrangement - it is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Triangular_number" rel="noopener noreferrer" target="_blank">triangular number</a> <em>n</em>(<em>n</em>+1)/2. Evaluating it: n=9 gives 45, n=8 gives 36, n=6 gives 21, n=5 gives 15, n=3 gives 6, n=2 gives 3 - all divisible by 3, so every pandigital of those lengths is composite. Only n=1 (sum 1, but the value 1 is not prime), n=4 (sum 10), and n=7 (sum 28) survive. That single analytic step cuts nine candidate lengths down to two. What remains is to enumerate the permutations of {1,2,3,4} and {1,2,3,4,5,6,7} - 4! = 24 and 7! = 5040 candidates - and test each for primality. Since the largest candidate is below 8 million, <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> up to the square root (about 2800) is far more than fast enough. The overall complexity is O(k! * sqrt(N)) with k at most 7 - microseconds in practice.
  </p>
<h3>Solution Approach</h3>
<h4>Descending Permutation Search (C and Python)</h4>
<p>
    Both files implement the same algorithm: enumerate the permutations of each viable digit set in <em>descending</em> numeric order, length 7 before length 4, and return the first arrangement that passes a primality test. Because I walk from the largest value downward, the first prime I encounter is necessarily the largest pandigital prime - there is no need to collect every prime and take a maximum. This turns "find the maximum element with property P" into "stop at the first match", which holds the result count at one and avoids any sorting.
  </p>
<p>
    In the C version I store the surviving lengths as the literal array <code>{7, 4}</code>, encoding the digit-sum pruning conclusion directly in the code. For each length I initialise the digit array in descending order (7,6,5,4,3,2,1) and then call <code>prev_permutation</code> after every test. <code>prev_permutation</code> is the mirror image of the classic <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order" rel="noopener noreferrer" target="_blank">next_permutation</a>: it finds the rightmost position where the array descends, swaps that element with the largest element smaller than it in the tail, and reverses the tail - producing every arrangement in strictly descending lexicographic order, in O(n) time and O(1) extra space per step. (The file also carries a forward <code>next_permutation</code> for symmetry, though the search itself only uses the descending walk.) The helper <code>digits_to_number</code> folds the digit array into an integer with the standard <code>num = num * 10 + digit</code> accumulation, keeping the number-building step cleanly separate from the primality test. The test itself, <code>is_prime</code>, handles 2 specially, rejects evens, then trial-divides by odd numbers up to the square root, guarding the multiplication with <code>long long</code> to avoid overflow.
  </p>
<p>
    The Python version achieves the same descending order by reversing the digit tuple before handing it to <a class="reference-source" href="https://docs.python.org/3/library/itertools.html#itertools.permutations" rel="noopener noreferrer" target="_blank"><code>itertools.permutations</code></a>. Since <code>permutations</code> yields its results in the lexicographic order of its input, feeding it ("7","6",...,"1") produces numbers in descending order. The candidates are formed with <code>int("".join(digits))</code> and filtered lazily inside a generator expression; <code>next()</code> pulls the first prime and abandons the rest. The <code>is_prime</code> routine is identical in spirit to the C one, and <code>fast_is_prime</code> is a thin alias kept only for naming parity with other solutions.
  </p>
</article>