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

• value: the running concatenation of each product.
• lengthHow 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.

Programmatically Finding Pandigital Multiples

In this post we’ll go step by step through a clear, Python-based approach to solve the “concatenated pandigital multiples” problem. We’ll explain each part in simple terms, provide complete code examples, and ensure every detail is fully understandable—even if you’re new to programming. 1. Restating the

Slow is SmothShai Asher

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

Slow is SmothShai Asher