Project Euler

Find the Largest 0 to 9 Pandigital That Can Be Formed by Concatenating Products

Take the number 6 and multiply it by each of 1273 and 9854: 6 x 1273 = 7638 6 x 9854 = 59124 By concatenating these products we get the 1 to 9 pandigital 763859124. Notice that the concatenation of...

Source sync Apr 19, 2026

Problem #0170

Level Level 10

Solved By 2,342

Languages C++, Python

Answer 9857164023

Length 581 words

dynamic_programmingsearchmodular_arithmetic

Take the number $6$ and multiply it by each of $1273$ and $9854$: \begin {align*} 6 \times 1273 &= 7638\\ 6 \times 9854 &= 59124 \end {align*}

By concatenating these products we get the $1$ to $9$ pandigital $763859124$. We will call $763859124$ the "concatenated product of $6$ and $(1273,9854)$". Notice too, that the concatenation of the input numbers, $612739854$, is also $1$ to $9$ pandigital.

The same can be done for $0$ to $9$ pandigital numbers.

What is the largest $0$ to $9$ pandigital $10$-digit concatenated product of an integer with two or more other integers, such that the concatenation of the input numbers is also a $0$ to $9$ pandigital $10$-digit number?

Problem 170: Find the Largest 0 to 9 Pandigital That Can Be Formed by Concatenating Products

Mathematical Foundation

Definition. A 0-to-9 pandigital is a 10-digit string using each of the digits $\{0, 1, 2, \ldots, 9\}$ exactly once.

Theorem 1 (Digit conservation). If $n \| c_1 \| c_2 \| \cdots \| c_m$ is a 10-digit 0-9 pandigital and $n \cdot c_1 \| n \cdot c_2 \| \cdots \| n \cdot c_m$ is also a 10-digit 0-9 pandigital, then the total number of digits in $\{n, c_1, \ldots, c_m\}$ is 10 and the total number of digits in $\{n \cdot c_1, \ldots, n \cdot c_m\}$ is also 10.

Proof. A 0-9 pandigital has exactly 10 digits. The concatenation of the inputs uses each digit exactly once across all the input numbers, so the total digit count is 10. Similarly for the products. $\square$

Theorem 2 (Digit-set disjointness). The digit sets of $n, c_1, c_2, \ldots, c_m$ must be pairwise disjoint and their union must be $\{0, 1, \ldots, 9\}$ . Likewise for $n \cdot c_1, n \cdot c_2, \ldots, n \cdot c_m$ .

Proof. Since the concatenation is a pandigital (each digit exactly once), no digit can appear in more than one of the input numbers, and every digit must appear in some input number. The same argument applies to the products. $\square$

Lemma 1 (Multiplier count). We require $m \geq 2$ , i.e., at least two multipliers.

Proof. This is given in the problem statement. $\square$

Lemma 2 (Bitmask DP for optimal concatenation). Given a set of valid $(c_i, p_i)$ pairs where $p_i = n \cdot c_i$ , with associated digit masks, the problem of selecting a subset of size $\geq 2$ whose input masks partition the available digits and whose output masks partition $\{0, \ldots, 9\}$ can be solved via bitmask DP over $2^{10} = 1024$ states.

Proof. Define $\text{dp}[\text{in\_mask}][\text{out\_mask}]$ = maximum concatenated product achievable using multipliers whose combined input digit mask is $\text{in\_mask}$ and combined output digit mask is $\text{out\_mask}$ . Transitions add one $(c_i, p_i)$ pair at a time, requiring the new masks to be disjoint from the accumulated masks. The state space is at most $1024 \times 1024 = 2^{20} \approx 10^6$ , and the answer is $\text{dp}[\text{all\_remaining}][2^{10}-1]$ maximized over valid $n$ . When combining groups, both concatenation orders are tried to select the larger result. $\square$

Theorem 3 (Search strategy). To find the largest pandigital result, we search $n$ starting from values that can produce large leading digits (e.g., $n$ such that $n \cdot c_1$ starts with 9). The search terminates early once a candidate is found that cannot be exceeded.

Proof. The output is a 10-digit pandigital, so the largest possible starts with 9876543… . For a fixed $n$ , the largest product is obtained by choosing the largest valid multiplier. By searching $n$ values in an order that prioritizes large leading output digits and pruning branches where the partial result cannot exceed the current best, we guarantee finding the global maximum. $\square$

Editorial

Products nc_1 || nc_2 || … must be a 10-digit pandigital (0-9). Inputs n || c_1 || c_2 || … must also be a 10-digit pandigital (0-9). At least 2 multipliers required. We generate all valid (c, p) pairs. We then bitmask DP to find best combination of >= 2 pairs. Finally, iterate over each state in dp with compatible masks.

Pseudocode

Generate all valid (c, p) pairs
Bitmask DP to find best combination of >= 2 pairs
whose c-masks partition 'remaining' and p-masks partition {0..9}
for each state in dp with compatible masks
Check complete states with count >= 2
for valid complete states

Complexity Analysis

Time: For each $n$ , generating multipliers is $O(k!)$ where $k = 10 - \text{digits}(n)$ (permutations of remaining digits). The bitmask DP has $O(2^{20})$ states. With pruning by early termination and ordering $n$ values to find large results first, the practical runtime is a few seconds.
Space: $O(2^{20})$ for the DP table.

Answer

\boxed{9857164023}

C++ project_euler/problem_170/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 170: Largest pandigital concatenated product.
 *
 * Products n*c_i concatenated = pandigital (0-9, 10 digits)
 * n || c_1 || ... || c_m concatenated = pandigital (0-9, 10 digits), m >= 2
 *
 * Answer: 9857164023
 *
 * Approach: for each n (small, 1-4 digits typically), enumerate c values
 * with digits from available pool. Compute products, check digit constraints.
 * Use bitmask DP on (input_mask_used, output_mask_used).
 */

long long p10[11];

int dmask(long long x) {
    if (x == 0) return 1;
    int m = 0;
    while (x > 0) {
        int d = x % 10;
        if (m & (1<<d)) return -1;
        m |= (1<<d);
        x /= 10;
    }
    return m;
}

int ndig(long long x) {
    int c = 0; while (x) { c++; x /= 10; } return c ? c : 1;
}

const int FULL = (1<<10)-1;

int main(){
    p10[0]=1;
    for(int i=1;i<=10;i++) p10[i]=p10[i-1]*10;

    long long best = 0;

    // n can be any positive integer. Its digits must be distinct.
    // n uses d_n digits. Multipliers use 10-d_n digits. Need 10-d_n >= 2.
    // So d_n <= 8. But practically, n*c must have reasonable number of digits,
    // and products concatenated = 10 digits. So n is usually small.

    // For each n from 1 to ~10000 (4 digits max for reasonable search)
    for (long long n = 2; n <= 9999; n++) {
        int nm = dmask(n);
        if (nm < 0) continue;
        int nnd = ndig(n);
        int avail = FULL ^ nm;
        int avail_nd = 10 - nnd;
        if (avail_nd < 2) continue;

        // Enumerate c: positive integer whose digits are subset of 'avail', no repeats
        // c from 1 to ... we limit by product size: n*c < 10^10
        // For n=2, c < 5*10^9. Too many.
        // Better: enumerate c by DFS on available digits.

        // But DFS on available digits generates up to P(avail_nd, 1) + P(avail_nd, 2) + ... numbers
        // For avail_nd=8: sum of P(8,k) for k=1..8 = 8+56+336+1680+6720+20160+40320+40320 = 109600
        // For avail_nd=9: about 986000. Manageable.

        struct CandPair {
            int cm, pm, pnd;
            long long pv;
        };

        // Use DFS to enumerate c values
        vector<CandPair> cpairs;

        struct F { long long v; int m; int d; };
        vector<F> stk;
        for (int d = 0; d <= 9; d++) {
            if (!(avail & (1<<d))) continue;
            if (d == 0) continue; // no leading zero for c
            stk.push_back({(long long)d, 1<<d, 1});
        }

        while (!stk.empty()) {
            auto [v, m, d] = stk.back();
            stk.pop_back();

            long long prod = n * v;
            int pm = dmask(prod);
            if (pm >= 0) {
                int pnd = ndig(prod);
                if (__builtin_popcount(pm) == pnd) {
                    cpairs.push_back({m, pm, pnd, prod});
                }
            }

            if (d < avail_nd) {
                for (int dd = 0; dd <= 9; dd++) {
                    if (!(avail & (1<<dd))) continue;
                    if (m & (1<<dd)) continue;
                    stk.push_back({v*10+dd, m|(1<<dd), d+1});
                }
            }
        }

        if ((int)cpairs.size() < 2) continue;

        // Keep best product per (cm, pm) pair
        unordered_map<long long, pair<long long,int>> best_cp; // key=cm*1024+pm -> (pv, pnd)
        for (auto& cp : cpairs) {
            long long key = (long long)cp.cm * 1024 + cp.pm;
            auto it = best_cp.find(key);
            if (it == best_cp.end() || cp.pv > it->second.first)
                best_cp[key] = {cp.pv, cp.pnd};
        }

        // DP: state = (cu, pu) -> (best_concat_val, nd, nseg)
        // Transition: add one (cm, pm) pair with no overlap
        // Process by increasing popcount of cu

        // Use array indexed by cu (subset of avail) and pu (subset of FULL)
        // Too large: 2^avail_nd * 1024. For avail_nd=9: 512*1024 = 512k. Possible.
        // But we have avail with specific bits set. Let's use unordered_map.

        struct DPV { long long val; int nd; int nseg; };
        unordered_map<long long, DPV> dp;

        // Init: single pairs
        for (auto& [key, val] : best_cp) {
            auto it = dp.find(key);
            if (it == dp.end() || val.first > it->second.val)
                dp[key] = {val.first, val.second, 1};
        }

        // Combine: iterate over existing states and try adding each pair
        // Sort by popcount of cu for correct ordering
        // We do multiple passes until no change
        // Max passes = max number of segments ~ 10
        for (int pass = 0; pass < 9; pass++) {
            bool changed = false;
            vector<pair<long long, DPV>> entries(dp.begin(), dp.end());

            for (auto& [ekey, eval] : entries) {
                int ecu = ekey / 1024;
                int epu = ekey % 1024;

                for (auto& [pkey, pval] : best_cp) {
                    int pcm = pkey / 1024;
                    int ppm = pkey % 1024;
                    if (ecu & pcm) continue;
                    if (epu & ppm) continue;

                    int ncu = ecu | pcm;
                    int npu = epu | ppm;
                    long long nkey = (long long)ncu * 1024 + npu;

                    long long c1 = eval.val * p10[pval.second] + pval.first;
                    long long c2 = pval.first * p10[eval.nd] + eval.val;
                    long long bv = max(c1, c2);
                    int nnd = eval.nd + pval.second;
                    int ns = eval.nseg + 1;

                    auto it = dp.find(nkey);
                    if (it == dp.end() || bv > it->second.val) {
                        dp[nkey] = {bv, nnd, ns};
                        changed = true;
                    }
                }
            }
            if (!changed) break;
        }

        long long target = (long long)avail * 1024 + FULL;
        auto it = dp.find(target);
        if (it != dp.end() && it->second.nseg >= 2 && it->second.nd == 10) {
            if (it->second.val > best) {
                best = it->second.val;
                fprintf(stderr, "n=%lld: %lld (nseg=%d)\n", n, best, it->second.nseg);
            }
        }
    }

    cout << best << endl;
    return 0;
}

Python project_euler/problem_170/solution.py

"""
Problem 170: Find the largest 0-9 pandigital formed by concatenating products.

Products n*c_1 || n*c_2 || ... must be a 10-digit pandigital (0-9).
Inputs n || c_1 || c_2 || ... must also be a 10-digit pandigital (0-9).
At least 2 multipliers required.

Answer: 9857164023

For each n, enumerate multipliers c with digits from the available pool,
compute products, and use bitmask DP to find the best covering.
"""

def solve():
    FULL = (1 << 10) - 1
    p10 = [1] * 11
    for i in range(1, 11):
        p10[i] = p10[i-1] * 10

    def dmask(x):
        if x == 0:
            return -1
        m = 0
        while x > 0:
            d = x % 10
            if m & (1 << d):
                return -1
            m |= (1 << d)
            x //= 10
        return m

    def ndig(x):
        c = 0
        while x > 0:
            c += 1
            x //= 10
        return c if c else 1

    global_best = 0

    for n in range(2, 100):
        nm = dmask(n)
        if nm < 0:
            continue
        nnd = ndig(n)
        avail = FULL ^ nm
        avail_nd = 10 - nnd
        if avail_nd < 2:
            continue

        # DFS to enumerate multipliers c with digits from avail
        pairs = []  # list of (c_mask, p_mask, p_nd, p_val)
        stack = []
        for d in range(10):
            if not (avail & (1 << d)):
                continue
            if d == 0:
                continue
            stack.append((d, 1 << d, 1))

        while stack:
            val, mask, nd = stack.pop()
            prod = n * val
            pm = dmask(prod)
            if pm >= 0:
                pnd = ndig(prod)
                if bin(pm).count('1') == pnd:
                    pairs.append((mask, pm, pnd, prod))
            if nd < avail_nd:
                for d in range(10):
                    if not (avail & (1 << d)):
                        continue
                    if mask & (1 << d):
                        continue
                    stack.append((val * 10 + d, mask | (1 << d), nd + 1))

        if len(pairs) < 2:
            continue

        # Keep best product per (c_mask, p_mask)
        best_cp = {}
        for cm, pm, pnd, pv in pairs:
            key = (cm, pm)
            if key not in best_cp or pv > best_cp[key][0]:
                best_cp[key] = (pv, pnd)

        # Bitmask DP
        dp = {}  # key=(cu, pu) -> (best_val, nd, nseg)

        for (cm, pm), (pv, pnd) in best_cp.items():
            key = (cm, pm)
            if key not in dp or pv > dp[key][0]:
                dp[key] = (pv, pnd, 1)

        for _pass in range(9):
            changed = False
            entries = list(dp.items())
            for (ecu, epu), (ev, end, ens) in entries:
                for (cm, pm), (pv, pnd) in best_cp.items():
                    if ecu & cm:
                        continue
                    if epu & pm:
                        continue
                    ncu = ecu | cm
                    npu = epu | pm
                    c1 = ev * p10[pnd] + pv
                    c2 = pv * p10[end] + ev
                    bv = max(c1, c2)
                    nnd = end + pnd
                    ns = ens + 1
                    nkey = (ncu, npu)
                    if nkey not in dp or bv > dp[nkey][0]:
                        dp[nkey] = (bv, nnd, ns)
                        changed = True
            if not changed:
                break

        target = (avail, FULL)
        if target in dp and dp[target][2] >= 2 and dp[target][1] == 10:
            if dp[target][0] > global_best:
                global_best = dp[target][0]

    print(global_best)

solve()