Problem 38: Pandigital Multiples

Project Euler Problem 38 Solution

EulerSolve provides an optimized solution for Project Euler Problem 38, Pandigital Multiples, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For a positive integer $b$, form the concatenated product $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ We want $C(b,m)$ to be a 9-digit number whose digits are exactly $1,2,\dots,9$ in some order, and we must find the largest such value. The standard example is $$C(192,3)=192384576,$$ which is already 1-to-9 pandigital. The full problem is to determine which base $b$ and which final multiplier $m$ produce the maximum pandigital concatenation. Mathematical Approach The implementations solve the problem by turning it into a tiny exhaustive search, but that search is only convincing after we understand the exact digit-length and digit-usage constraints. The decisive length sum Let $\ell(x)$ be the number of decimal digits of $x$, and define $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ A base $b$ can be valid only if there is some $m \ge 2$ with $L_b(m)=9$. This quantity is the real state variable of the search: after appending the first $t$ products, the current string has length $L_b(t)$. Because every appended block contributes at least one digit, $L_b(t)$ is strictly increasing in $t$. So for any fixed base there is at most one relevant stopping point: the first $t$ for which $L_b(t)\ge 9$. If $L_b(t)=9$, we have the only possible candidate for that base....

Detailed mathematical approach

Problem Summary

For a positive integer $b$, form the concatenated product $$C(b,m)=\operatorname{concat}(b,2b,3b,\dots,mb), \qquad m \ge 2.$$ We want $C(b,m)$ to be a 9-digit number whose digits are exactly $1,2,\dots,9$ in some order, and we must find the largest such value.

The standard example is $$C(192,3)=192384576,$$ which is already 1-to-9 pandigital. The full problem is to determine which base $b$ and which final multiplier $m$ produce the maximum pandigital concatenation.

Mathematical Approach

The implementations solve the problem by turning it into a tiny exhaustive search, but that search is only convincing after we understand the exact digit-length and digit-usage constraints.

The decisive length sum

Let $\ell(x)$ be the number of decimal digits of $x$, and define $$L_b(t)=\sum_{r=1}^{t}\ell(rb).$$ A base $b$ can be valid only if there is some $m \ge 2$ with $L_b(m)=9$. This quantity is the real state variable of the search: after appending the first $t$ products, the current string has length $L_b(t)$.

Because every appended block contributes at least one digit, $L_b(t)$ is strictly increasing in $t$. So for any fixed base there is at most one relevant stopping point: the first $t$ for which $L_b(t)\ge 9$. If $L_b(t)=9$, we have the only possible candidate for that base. If $L_b(t) \gt 9$, then no larger multiplier can ever repair the overshoot.

Why the base never needs five digits

Since $m \ge 2$, any valid concatenation must include both $b$ and $2b$. Therefore $$\ell(b)+\ell(2b)\le 9.$$ If $\ell(b)\ge 5$, then already $\ell(b)+\ell(2b)\ge 10$, which is impossible. Hence every solution satisfies $$1 \le b \le 9999.$$ This is exactly why the C++, Python, and Java implementations enumerate bases only in that range.

There is also a useful structural consequence. A 4-digit base can only work with $m=2$, because three 4-digit blocks would already contribute at least 12 digits. A 3-digit base can only survive a few multipliers, and a 1-digit base needs many of them. The code does not hard-code those cases; it lets the length sum $L_b(t)$ discover them automatically.

Pandigitality is a digit-count invariant

For each decimal digit $j\in\{0,1,\dots,9\}$, let $c_j$ be the number of times $j$ appears in $C(b,m)$. The 1-to-9 pandigital condition is $$c_0=0,\qquad c_j=1 \quad (1\le j\le 9).$$ Because the candidate length is already fixed at 9, this condition becomes very cheap to verify: reject 0 immediately, reject any repeated nonzero digit immediately, and if no rejection occurs then the nine used digits must be exactly $\{1,2,\dots,9\}$.

This is why the implementations only need a small boolean table indexed by digit. There is no deeper combinatorial machinery here; once the length is right, the entire problem reduces to a constant-size occupancy check.

Worked examples and the maximal candidate

The given example $$C(192,3)=192384576$$ has length $3+3+3=9$ and uses each nonzero digit exactly once. A stronger benchmark comes from $$C(9,5)=918273645,$$ which starts with 9 and is also pandigital.

The winning case found by the exhaustive scan is $$C(9327,2)=932718654,$$ because $9327$ contributes 4 digits, $18654$ contributes 5 digits, and together they use the digits $1$ through $9$ exactly once. Since every admissible base $1\le b\le 9999$ is checked and each base contributes at most one 9-digit candidate, this value is the true maximum.

How the Code Works

The C++, Python, and Java implementations all follow the same algorithm. They iterate through every base $b$ from 1 to 9999, start with an empty decimal string, and append $b,2b,3b,\dots$ one block at a time. The loop stops for that base as soon as the concatenation length reaches 9 or exceeds 9, which is exactly the monotonicity argument from $L_b(t)$.

If the length lands on 9 and at least two products have been appended, the implementation performs the pandigital check with a 10-slot digit table. Encountering 0 or a repeated digit rejects the candidate immediately; otherwise the 9-digit value is compared with the current maximum. Because all valid candidates have the same length, a plain integer comparison is enough.

Each implementation also includes two tiny checkpoint tests before solving the full problem. One verifies that multiplying 192 by $1,2,3$ produces the known concatenation $192384576$, and the other verifies that the digit validator accepts $123456789$. Those checkpoints guard both the concatenation logic and the pandigital test.

Complexity Analysis

The outer loop tries exactly 9999 bases. For any one base, the inner loop appends products only until the running length reaches 9, so it performs at most 9 iterations and usually far fewer. The pandigital test scans exactly 9 characters and uses a fixed-size digit table.

So the running time is effectively constant for this Project Euler instance, and if the upper base bound is written as $B$ then the search is $O(B)$ time with $O(1)$ extra space. In practical terms the entire workload is only a few tens of thousands of primitive digit operations.

Footnotes and References

Problem page: Project Euler Problem 38
Pandigital numbers: Wikipedia - Pandigital number
Positional notation: Wikipedia - Positional notation
Concatenation: Wikipedia - Concatenation

Problem 38 source code

C++

#include <algorithm>
#include <iostream>
#include <string>

namespace {

struct Options {
    bool run_checkpoints = true;
};

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

bool is_1_to_9_pandigital(const std::string& s) {
    if (s.size() != 9U) {
        return false;
    }

    bool used[10] = {false};
    for (const char c : s) {
        const int d = c - '0';
        if (d <= 0 || d >= 10 || used[d]) {
            return false;
        }
        used[d] = true;
    }
    for (int d = 1; d <= 9; ++d) {
        if (!used[d]) {
            return false;
        }
    }
    return true;
}

std::string concatenated_product(const int base, const int max_multiplier) {
    std::string out;
    out.reserve(16U);

    for (int n = 1; n <= max_multiplier; ++n) {
        out += std::to_string(base * n);
    }

    return out;
}

int solve() {
    int best = 0;
    for (int base = 1; base <= 9999; ++base) {
        std::string concat;
        for (int n = 1; concat.size() < 9U; ++n) {
            concat += std::to_string(base * n);
            if (concat.size() == 9U && n >= 2 && is_1_to_9_pandigital(concat)) {
                best = std::max(best, std::stoi(concat));
            }
        }
    }
    return best;
}

bool run_checkpoints() {
    if (concatenated_product(192, 3) != "192384576") {
        std::cerr << "Checkpoint failed for base=192" << '\n';
        return false;
    }
    if (!is_1_to_9_pandigital("123456789")) {
        std::cerr << "Checkpoint failed for pandigital helper" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve() << '\n';
    return 0;
}

Python

import sys

def is_1_to_9_pandigital(s):
    if len(s) != 9:
        return False
    
    used = [False] * 10
    for c in s:
        d = ord(c) - ord('0')
        if d <= 0 or d >= 10 or used[d]:
            return False
        used[d] = True
    
    for d in range(1, 10):
        if not used[d]:
            return False
    
    return True

def concatenated_product(base, max_multiplier):
    out = []
    for n in range(1, max_multiplier + 1):
        out.append(str(base * n))
    return ''.join(out)

def solve():
    best = 0
    for base in range(1, 10000):
        concat = ""
        n = 1
        while len(concat) < 9:
            concat += str(base * n)
            if len(concat) == 9 and n >= 2 and is_1_to_9_pandigital(concat):
                best = max(best, int(concat))
            n += 1
    return best

def run_checkpoints():
    if concatenated_product(192, 3) != "192384576":
        print("Checkpoint failed for base=192", file=sys.stderr)
        return False
    if not is_1_to_9_pandigital("123456789"):
        print("Checkpoint failed for pandigital helper", file=sys.stderr)
        return False
    return True

def main():
    args = sys.argv[1:]
    run_checkpoints_flag = True
    
    for arg in args:
        if arg == "--skip-checkpoints":
            run_checkpoints_flag = False
        else:
            print(f"Unknown argument: {arg}", file=sys.stderr)
            return 1
    
    if run_checkpoints_flag and not run_checkpoints():
        return 2
    
    print(solve())
    return 0

if __name__ == "__main__":
    sys.exit(main())

Java

class Euler38 {

    private static class Options {
        boolean runCheckpoints = true;
    }

    private static boolean parseArguments(String[] args, Options options) {
        for (int i = 0; i < args.length; ++i) {
            String arg = args[i];
            if ("--skip-checkpoints".equals(arg)) {
                options.runCheckpoints = false;
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            return false;
        }
        return true;
    }

    private static boolean is1To9Pandigital(String s) {
        if (s.length() != 9) {
            return false;
        }

        boolean[] used = new boolean[10];
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            int d = c - '0';
            if (d <= 0 || d >= 10 || used[d]) {
                return false;
            }
            used[d] = true;
        }
        for (int d = 1; d <= 9; ++d) {
            if (!used[d]) {
                return false;
            }
        }
        return true;
    }

    private static String concatenatedProduct(int base, int maxMultiplier) {
        StringBuilder out = new StringBuilder();

        for (int n = 1; n <= maxMultiplier; ++n) {
            out.append(base * n);
        }

        return out.toString();
    }

    private static int solve() {
        int best = 0;
        for (int base = 1; base <= 9999; ++base) {
            StringBuilder concat = new StringBuilder();
            for (int n = 1; concat.length() < 9; ++n) {
                concat.append(base * n);
                if (concat.length() == 9 && n >= 2 && is1To9Pandigital(concat.toString())) {
                    int candidate = Integer.parseInt(concat.toString());
                    if (candidate > best) {
                        best = candidate;
                    }
                }
            }
        }
        return best;
    }

    private static boolean runCheckpoints() {
        if (!"192384576".equals(concatenatedProduct(192, 3))) {
            System.err.println("Checkpoint failed for base=192");
            return false;
        }
        if (!is1To9Pandigital("123456789")) {
            System.err.println("Checkpoint failed for pandigital helper");
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parseArguments(args, options)) {
            System.exit(1);
        }
        if (options.runCheckpoints && !runCheckpoints()) {
            System.exit(2);
        }

        System.out.println(solve());
    }
}