Solving Pandigital Multiples with C# and Length‑Based Pruning

In this post, we’ll explore a C# implementation that finds the largest 1–9 pandigital concatenated product by mathematically pruning the search space based on digit lengths, rather than brute-forcing all possibilities.

1. The Pandigital Multiples Problem Recap

We seek the maximum 9‑digit number formed by concatenating the products:

k×1 ‖ k×2 ‖ … ‖ k×n

so that the result uses each digit 1–9 exactly once. Brute‑force tries all k from 1 to 9999, builds and checks each concatenation, but we can do better by analyzing digit counts.

2. Key Insight: Digit‑Length Constraints

1. k’s digit length determines how many multipliers n can fit into exactly 9 digits.
   • If k is 4 digits, then k×1 has 4 digits and k×2 has 4 or 5 digits → total ~9. More multipliers overshoot.
   • If k is 3 digits, you may need n=3 to reach 9 digits (3+3+3).
2. For each possible n, you can solve for the ranges of k whose multiplied results exactly fill 9 digits:
   • Let d1 = digits(k×1), d2 = digits(k×2), …, dn = digits(k×n). Then d1+…+dn = 9.
   • Each di bounds k by inequalities like 10^{d1−1} ≤ k < 10^{d1}, and similarly for i*k.

By computing these bounds, we iterate only over valid k ranges for each (n, d1,d2,…), drastically reducing work.

3. C# Implementation Structure

class Program {
  static void Main() {
    int max = 0, bestK = 0, bestN = 0;
    // consider n = 2 and 3 only
    for (int n = 2; n <= 3; n++) {
      for (int d1 = 1; d1 <= 4; d1++) {
        // compute possible kMin/kMax for this (n, d1, …)
        // then EvaluateRange(kMin, kMax, n, ref max, ...)
      }
    }
    Console.WriteLine(...);
  }

  static void EvaluateRange(int kMin, int kMax, int n, ...) {
    for (int k = kMin; k <= kMax; k++) {
      // build concatenation: string s = k*1 || k*2 || …
      // if s.Length == 9 && IsPandigital(s): update max
    }
  }

  static bool IsPandigital(string s) {
    return s.Length==9 && s.Distinct().Count()==9 && !s.Contains('0');
  }
}

Key functions:

• Main loops over n=2,3, then over possible digit length d1 of k×1. Inside, it derives d2 (and d3 if n=3), calculates the lower/upper bounds for k, and calls EvaluateRange on that tight range.
• EvaluateRange(kMin,kMax,n,…) iterates only the mathematically valid k values, concatenates the first n products, and checks pandigitality.
• IsPandigital(s) ensures the 9-digit string uses each digit 1–9 exactly once.

4. Benefits of Length‑Based Pruning

• Huge reduction in candidate k values: instead of 9 999 tests, you often test only a few hundred or thousand.
• Deterministic bounds: by solving 10^{d−1} ≤ k*i < 10^d, we guarantee every considered k can produce exactly 9 digits with n multipliers.
• Clarity: the math-driven loops make explicit why each k is valid, simplifying reasoning and debugging.

5. Performance and Further Tuning

• This C# version runs in a few milliseconds on modern hardware, far outperforming naive brute-force.
• You can further optimize by:
  • Avoiding string concatenation inside EvaluateRange (use integer arithmetic and StringBuilder).
  • Parallelizing the outer loops (e.g., Parallel.For over d1 or k ranges).
  • Caching digit-length lookups in a small array.

6. Conclusion

By leveraging digit-length analysis to prune the search space, this C# implementation efficiently homes in on the few candidate ranges that can yield a 9‑digit concatenated product. It neatly balances mathematical insight with straightforward code, illustrating how a small theoretical observation can yield large practical speedups.

Optimizing Pandigital Multiples in Python

In this follow-up post, we’ll transform our straightforward brute-force solution into a lean, mean, Pythonic machine, avoiding strings, pruning early, and utilizing bitmasks and vectorized data structures for clarity and speed. 1. Integer‑Only Concatenation Instead of building a string, we’ll assemble the concatenated product as an integer.

Slow is SmothShai Asher