← Writing

Optimizing Pandigital Multiples in Python

3 min readProject EulerProblem 38Project Euler

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. We keep track of:

  • value: the running concatenation of each product.
  • **length**How many digits have we added so far?
def concatenated_value(k):
    value, length, n = 0, 0, 1
    while length < 9:
        prod = k * n
        # fast digit count (1 ≤ prod < 100000)
        if     prod < 10:   d = 1
        elif prod < 100:  d = 2
        elif prod < 1000: d = 3
        elif prod < 10000:d = 4
        else:               d = 5
        # append prod by shifting and adding
        value = value * (10**d) + prod
        length += d
        n += 1
        if length > 9:
            return None, None
    return value, n-1  # returns (concat, n)
  • Why? Eliminating string conversion removes allocation and parsing overhead.
  • Early exit With length > 9 avoids wasted work.

2. Bitmask‑Based Digit Check

We can test pandigitality by building a 10‑bit mask (bits 1–9). If a digit repeats or is zero, we bail immediately.

def is_pandigital_mask(x):
    mask = 0
    for _ in range(9):
        d = x % 10
        x //= 10
        bit = 1 << d
        # reject zero or repeated
        if d == 0 or (mask & bit):
            return False
        mask |= bit
    return mask == 0b1111111110  # bits 1–9 set
  • Uses integer arithmetic only.
  • No sorting or set allocations.

3. Pruning the Search Space

Observe:

  • Any base k With five digits or more is invalid: even k*1||k*2 exceeds nine digits.
  • For k with 1–3 digits, n may need to be 2 or 3 to reach exactly 9 digits; for k with 4 digits, only n=2 works.
def valid_ks():
    # 1- to 4-digit k only
    for k in range(1, 10000):
        yield k

More precisely, you can group by the digit length of k and precompute the required n range, but often a simple 1..9999 loop with early exits is fast enough.

4. Putting It All Together

max_val, best_k, best_n = 0, 0, 0
for k in valid_ks():
    concat, n = concatenated_value(k)
    if concat is None:
        continue
    if is_pandigital_mask(concat):
        if concat > max_val:
            max_val, best_k, best_n = concat, k, n

print(f"Max pandigital: {max_val} (k={best_k}, n={best_n})")

This version runs in under a millisecond in CPython and maintains crystal‑clear logic:

  1. Build the integer concatenation, exit early on overflow.
  2. Mask‑check digits quickly, exit early on failure.
  3. Compare and record the maximum.

5. Advanced Pythonic Touches

  • functools.lru_cache can memoize digit counts or masks if reused.
  • itertools.takewhile Can replace the while length<9 loop for elegance.
  • NumPy vectorization (for extensive ranges) can offload candidate assembly to fast C loops.

Prev: Programmatically Finding Pandigital Multiples

Next: Solving Pandigital Multiples with C# and Length‑Based Pruning

More