Problem 38

Programmatically Finding Pandigital Multiples

Shai Asher

20 Jul 2025 • 3 min read

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 Task in Code-Friendly Terms

Input space: We need to test every integer k from 1 up to 9999. Why 9999? Because if k has 5 or more digits, even k×1||k×2 becomes longer than 9 digits immediately.
Checking length and pandigitality: Accept only those s of exactly length 9 whose characters include each digit '1'–'9' exactly once.
Bookkeeping: Track the maximum numeric value of those valid s, and record which k (and how many multipliers n) produced it.

Building the concatenation: For each k,build the string:

s = str(k*1) + str(k*2) + str(k*3) + …

until len(s) ≥ 9.

2. A Straightforward Python Implementation

First, here’s a clear, direct translation of the above steps into Python:

def is_pandigital_1to9(s: str) -> bool:
    """
    Returns True if s is 9 characters long and contains exactly the digits '1' through '9'.
    """
    return len(s) == 9 and set(s) == set('123456789')

max_val = 0
best_k  = None
best_n  = None

for k in range(1, 10000):
    concat = ''
    n = 1
    # Build up until at least 9 characters
    while len(concat) < 9:
        concat += str(k * n)
        n += 1
    # Check for exactly 9 and pandigital
    if is_pandigital_1to9(concat):
        val = int(concat)
        if val > max_val:
            max_val = val
            best_k  = k
            best_n  = n - 1

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

How it works:

We loop k from 1 to 9999 inclusive.
For each, we keep appending k×n to a string until its length is ≥9.
If it’s exactly 9 and uses each digit once, we compare it to our running maximum.

This brute-force approach finishes in a fraction of a second on modern machines, and finds 932718654 (from k=9327, n=2).

3. Breaking Down Key Functions

3.1. Checking Pandigitality

def is_pandigital_1to9(s: str) -> bool:
    return len(s) == 9 and set(s) == set('123456789')

len(s) == 9 ensures we only consider 9-character strings.
set(s) builds the unique characters; compared to {'1',...,'9'} guarantees every digit appears once.

3.2. Building the Concatenation

concat = ''
n      = 1
while len(concat) < 9:
    concat += str(k*n)
    n += 1

We start with n=1 and append k*n each time.
We stop as soon as the string length reaches 9 or more—there’s no need to build further.

3.3. Tracking the Maximum

if is_pandigital_1to9(concat):
    val = int(concat)
    if val > max_val:
        max_val = val
        best_k  = k
        best_n  = n - 1

We convert concat back to an integer for numeric comparison.
We store the best triple (max_val, best_k, best_n).

4. Optimizations and Enhancements

Although the brute-force is already fast enough for k<10000, you can refine it:

Early Prune Non-Pandigital Digits:
As you extract each digit of prod, you can accumulate a bitmask and abort early if you see a repeat or a zero.
Search Space Reduction:
Only n=2 and n=3 need be considered for k >= 100,since more multipliers will overshoot 9 digits or never reach them exactly.

Quick Digit-Count:
Replace len(str(prod)) with a small lookup or comparisons:

if prod < 10: d = 1
elif prod < 100: d = 2
# … up to 5 digits

Avoid String Operations:
Instead of str() and string concatenation, you can build an integer by tracking digit counts and powers of ten. Example:

val = 0
length = 0
n = 1
while length < 9:
    prod = k * n
    d = len(str(prod))            # or a small digit-count helper
    val = val * (10**d) + prod
    length += d
    n += 1

In a follow‑up post, we’ll explore these optimizations in code and show how to leverage Python’s data structures for even cleaner implementations.

5. Conclusion

We’ve walked through a clear, end‑to‑end Python solution: from looping over candidates to checking pandigitality and recording the maximum. This problem illustrates how simple arithmetic and string checks can combine into an elegant search,

In upcoming posts, we’ll dive deeper into numeric (non‑string) concatenation, bit‑masking for digit presence, and even parallel strategies to push this solution to its absolute speed limit. Stay tuned!