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

Project Euler Problem 170 Solution

EulerSolve provides an optimized solution for Project Euler Problem 170, Find the Largest 0 to 9 Pandigital That Can Be Formed by Concatenating Products, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We seek the largest 10-digit number $P$ that uses the digits $0,1,\dots,9$ exactly once and can be written as a concatenation of decimal products $$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$ for some positive integer multiplier $m$ and positive integers $x_1,\dots,x_t$. The input-side concatenation $$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$ must also be 0-to-9 pandigital. All numbers are interpreted in ordinary decimal notation, so a multi-digit block may not begin with 0. Mathematical Approach The crucial simplification is to search from the output side. Instead of guessing $m$ and the multiplicands first, the implementation scans possible 10-digit pandigital outputs in descending order and asks whether each one can be decomposed into valid product blocks. From a two-sided identity to a one-sided search Take a candidate output string $Y$. If $Y$ is valid, then some choice of block boundaries turns it into decimal integers $$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$ where each block satisfies $$p_i=m x_i.$$ So the entire problem becomes: choose a 10-digit pandigital output $Y$, choose block boundaries, and check whether there exists a common multiplier $m$ making the reconstructed input $m\Vert x_1\Vert\cdots\Vert x_t$ pandigital as well. Choosing the product blocks A 10-digit string has 9 gaps between consecutive digits....

Detailed mathematical approach

Problem Summary

We seek the largest 10-digit number $P$ that uses the digits $0,1,\dots,9$ exactly once and can be written as a concatenation of decimal products

$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$

for some positive integer multiplier $m$ and positive integers $x_1,\dots,x_t$. The input-side concatenation

$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$

must also be 0-to-9 pandigital. All numbers are interpreted in ordinary decimal notation, so a multi-digit block may not begin with 0.

Mathematical Approach

The crucial simplification is to search from the output side. Instead of guessing $m$ and the multiplicands first, the implementation scans possible 10-digit pandigital outputs in descending order and asks whether each one can be decomposed into valid product blocks.

From a two-sided identity to a one-sided search

Take a candidate output string $Y$. If $Y$ is valid, then some choice of block boundaries turns it into decimal integers

$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$

where each block satisfies

$$p_i=m x_i.$$

So the entire problem becomes: choose a 10-digit pandigital output $Y$, choose block boundaries, and check whether there exists a common multiplier $m$ making the reconstructed input $m\Vert x_1\Vert\cdots\Vert x_t$ pandigital as well.

Choosing the product blocks

A 10-digit string has 9 gaps between consecutive digits. Any nonempty subset of those gaps can be declared to be block boundaries, so there are

$$2^9-1=511$$

nontrivial partitions to test. This matches the decimal concatenation exactly: every valid identity produces one of these contiguous blockings, and every blocking gives a concrete list of product candidates $p_1,\dots,p_t$.

Whenever a block would have more than one digit and start with 0, that partition is impossible in standard decimal notation and is discarded immediately.

The gcd invariant for the common multiplier

Once a partition $p_1,\dots,p_t$ is fixed, the multiplier is heavily constrained. Since $p_i=m x_i$ for every $i$, the multiplier must divide every block, hence

$$m\mid p_i\quad\text{for all }i,$$

and therefore

$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$

This is the key invariant used by all three implementations. It turns an open-ended search over possible multipliers into a finite divisor search. For a fixed partition, every feasible multiplier must be a divisor of one specific integer $g$.

Reconstructing the input side uniquely

The gcd condition is not only necessary; it also tells us exactly what to test. If $d$ is a divisor of $g$, then the only possible multiplicands are

$$x_i=\frac{p_i}{d}.$$

So a fixed partition and a fixed divisor $d\mid g$ produce exactly one candidate input concatenation:

$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$

No further freedom remains. Therefore the validation step is simple: compute $g$, enumerate its divisors, rebuild $I_d$, and check whether $I_d$ uses the digits $0$ through $9$ exactly once. If it does, the chosen output partition is a genuine solution.

Worked example

The classic 1-to-9 sample already shows the whole mechanism. Consider

$$763859124=7638\Vert59124.$$

With this partition,

$$g=\gcd(7638,59124)=6.$$

So the only possible common multipliers are the divisors of 6. Testing $d=6$ gives

$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$$

hence the input-side concatenation

$$6\Vert1273\Vert9854=612739854,$$

which is 1-to-9 pandigital. Problem 170 asks for the same phenomenon with all ten digits $0,\dots,9$ used exactly once. The code applies the same gcd-and-divisors argument to every 10-digit pandigital output candidate.

Why the first accepted output is the maximum

The outer search visits pandigital outputs in descending order. Because every candidate is a 10-digit number with nonzero leading digit, descending lexicographic order is the same as descending numeric order. The search is exhaustive for each output: every valid identity determines a unique output string, one of the 511 partitions of that string, and a multiplier among the divisors of the partition gcd. So when the algorithm finds the first valid output, no larger valid output can still be waiting later in the scan.

How the Code Works

Enumerating output candidates

The C++, Python, and Java implementations all iterate over the digits $9,8,\dots,0$ in descending permutation order and interpret each permutation as a candidate output string. Any permutation beginning with 0 is skipped, since it would not represent a 10-digit number.

Testing every decimal partition

For each output candidate, the implementation inspects every nonempty split mask on the 9 digit gaps. Each mask determines a contiguous partition into product blocks. Partitions that create a multi-digit block with a leading zero are rejected on the spot, and the remaining blocks are parsed as decimal integers.

Filtering multipliers with the gcd

After forming the product blocks, the implementation computes their gcd. It then enumerates the divisors of that gcd in descending order. For each divisor, it divides every block by that candidate multiplier, concatenates the multiplier and the resulting quotients, and performs a pandigital check on the 10-character input string.

If the reconstructed input is 0-to-9 pandigital, the output candidate is valid and the whole search stops immediately. The C++ and Java versions walk the descending permutations directly; the Python version reaches the same order by generating permutations and scanning them in reverse-sorted order. The mathematical test is identical in all three languages.

Complexity Analysis

There are at most $10!=3{,}628{,}800$ permutations of the digits $0,\dots,9$, although candidates with leading zero are skipped. For each candidate output, the implementation examines all

$$2^9-1=511$$

nontrivial contiguous partitions. For one partition, it computes a gcd over a small number of blocks, enumerates the divisors of that gcd by trial division, and performs constant-size string checks because both the input and output concatenations always have length 10.

If $M$ denotes the largest block value in a partition, a simple worst-case description is

$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$$

with $M\le 987654321$ because at least one split is always present. The memory usage is $O(1)$ apart from short temporary lists of blocks and divisors. In practice the runtime is much smaller than the pessimistic bound because the scan terminates as soon as the largest valid output is found.

Footnotes and References

Project Euler problem page: Project Euler 170
Pandigital numbers: Wikipedia - Pandigital number
Permutations and lexicographic order: Wikipedia - Permutation
Greatest common divisor: Wikipedia - Greatest common divisor
Euclidean algorithm: Wikipedia - Euclidean algorithm

Problem 170 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

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_pandigital_0_to_9(const std::string& s) {
    if (s.size() != 10U) {
        return false;
    }
    std::array<int, 10> freq{};
    for (char c : s) {
        if (c < '0' || c > '9') {
            return false;
        }
        ++freq[static_cast<std::size_t>(c - '0')];
    }
    for (int f : freq) {
        if (f != 1) {
            return false;
        }
    }
    return true;
}

bool is_pandigital_1_to_9(const std::string& s) {
    if (s.size() != 9U) {
        return false;
    }
    std::array<int, 10> freq{};
    for (char c : s) {
        if (c < '1' || c > '9') {
            return false;
        }
        ++freq[static_cast<std::size_t>(c - '0')];
    }
    for (int d = 1; d <= 9; ++d) {
        if (freq[static_cast<std::size_t>(d)] != 1) {
            return false;
        }
    }
    return true;
}

void collect_divisors(const int n, std::vector<int>& divisors) {
    divisors.clear();
    for (int d = 1; static_cast<long long>(d) * d <= n; ++d) {
        if (n % d != 0) {
            continue;
        }
        divisors.push_back(d);
        if (d * d != n) {
            divisors.push_back(n / d);
        }
    }
    std::sort(divisors.begin(), divisors.end(), std::greater<int>());
}

bool output_has_valid_input(const std::string& output) {
    std::vector<int> divisors;

    for (int split_mask = 1; split_mask < (1 << 9); ++split_mask) {
        std::vector<int> products;
        int start = 0;
        bool good_partition = true;
        for (int bit = 0; bit < 9; ++bit) {
            if (((split_mask >> bit) & 1) == 0) {
                continue;
            }
            const int end = bit + 1;
            if (output[static_cast<std::size_t>(start)] == '0' && (end - start) > 1) {
                good_partition = false;
                break;
            }
            products.push_back(std::stoi(output.substr(static_cast<std::size_t>(start),
                                                       static_cast<std::size_t>(end - start))));
            start = end;
        }
        if (!good_partition) {
            continue;
        }
        if (output[static_cast<std::size_t>(start)] == '0' &&
            (static_cast<int>(output.size()) - start) > 1) {
            continue;
        }
        products.push_back(std::stoi(output.substr(static_cast<std::size_t>(start))));
        if (products.size() < 2U) {
            continue;
        }

        int g = products.front();
        for (int value : products) {
            g = std::gcd(g, value);
        }

        collect_divisors(g, divisors);
        for (int multiplier : divisors) {
            if (multiplier == 0) {
                continue;
            }

            std::string input_concat = std::to_string(multiplier);
            bool divisible = true;
            for (int value : products) {
                if (value % multiplier != 0) {
                    divisible = false;
                    break;
                }
                input_concat += std::to_string(value / multiplier);
            }
            if (!divisible) {
                continue;
            }
            if (is_pandigital_0_to_9(input_concat)) {
                return true;
            }
        }
    }

    return false;
}

u64 solve() {
    std::array<int, 10> digits{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    do {
        if (digits[0] == 0) {
            continue;
        }
        std::string output;
        output.reserve(10);
        for (int d : digits) {
            output.push_back(static_cast<char>('0' + d));
        }

        if (output_has_valid_input(output)) {
            return static_cast<u64>(std::stoull(output));
        }
    } while (std::prev_permutation(digits.begin(), digits.end()));

    return 0;
}

bool run_checkpoints() {
    const int k = 6;
    const int a = 1273;
    const int b = 9854;
    const std::string product_concat = std::to_string(k * a) + std::to_string(k * b);
    const std::string input_concat = std::to_string(k) + std::to_string(a) + std::to_string(b);
    if (!is_pandigital_1_to_9(product_concat) || !is_pandigital_1_to_9(input_concat)) {
        std::cerr << "Checkpoint failed for 1-to-9 sample" << '\n';
        return false;
    }

    const u64 ans = solve();
    const std::string ans_s = std::to_string(ans);
    if (!is_pandigital_0_to_9(ans_s) || !output_has_valid_input(ans_s)) {
        std::cerr << "Checkpoint failed for final candidate validation" << '\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

from itertools import permutations
from math import gcd

def is_pandigital_0_to_9(s):
    return len(s) == 10 and sorted(s) == list('0123456789')

def collect_divisors(n):
    divs = []
    d = 1
    while d * d <= n:
        if n % d == 0:
            divs.append(d)
            if d * d != n:
                divs.append(n // d)
        d += 1
    divs.sort(reverse=True)
    return divs

def output_has_valid_input(output):
    for split_mask in range(1, 1 << 9):
        products = []
        start = 0
        good_partition = True
        for bit in range(9):
            if not ((split_mask >> bit) & 1):
                continue
            end = bit + 1
            part = output[start:end]
            if len(part) > 1 and part[0] == '0':
                good_partition = False
                break
            products.append(int(part))
            start = end
        if not good_partition:
            continue
        last = output[start:]
        if len(last) > 1 and last[0] == '0':
            continue
        products.append(int(last))
        if len(products) < 2:
            continue
        g = products[0]
        for v in products[1:]:
            g = gcd(g, v)
        for multiplier in collect_divisors(g):
            if multiplier == 0:
                continue
            input_concat = str(multiplier)
            divisible = True
            for v in products:
                if v % multiplier != 0:
                    divisible = False
                    break
                input_concat += str(v // multiplier)
            if not divisible:
                continue
            if is_pandigital_0_to_9(input_concat):
                return True
    return False

def solve():
    digits = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    # Generate all permutations in descending order
    all_perms = sorted(permutations(range(10)), reverse=True)
    for perm in all_perms:
        if perm[0] == 0:
            continue
        output = ''.join(str(d) for d in perm)
        if output_has_valid_input(output):
            return output
    return '0'

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler170 {
    static boolean isPandigital(String s) {
        if (s.length() != 10)
            return false;
        char[] c = s.toCharArray();
        Arrays.sort(c);
        return new String(c).equals("0123456789");
    }

    static List<Integer> divisors(int n) {
        List<Integer> d = new ArrayList<>();
        for (int i = 1; (long) i * i <= n; i++)
            if (n % i == 0) {
                d.add(i);
                if (i != n / i)
                    d.add(n / i);
            }
        d.sort(Collections.reverseOrder());
        return d;
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static boolean hasValid(String output) {
        int n = output.length();
        for (int mask = 1; mask < (1 << (n - 1)); mask++) {
            List<Integer> parts = new ArrayList<>();
            int start = 0;
            boolean ok = true;
            for (int bit = 0; bit < n - 1; bit++) {
                if (((mask >> bit) & 1) == 0)
                    continue;
                String p = output.substring(start, bit + 1);
                if (p.length() > 1 && p.charAt(0) == '0') {
                    ok = false;
                    break;
                }
                parts.add(Integer.parseInt(p));
                start = bit + 1;
            }
            if (!ok)
                continue;
            String last = output.substring(start);
            if (last.length() > 1 && last.charAt(0) == '0')
                continue;
            parts.add(Integer.parseInt(last));
            if (parts.size() < 2)
                continue;
            int g = parts.get(0);
            for (int p : parts)
                g = gcd(g, p);
            for (int mult : divisors(g)) {
                if (mult == 0)
                    continue;
                StringBuilder sb = new StringBuilder();
                sb.append(mult);
                boolean div = true;
                for (int p : parts) {
                    if (p % mult != 0) {
                        div = false;
                        break;
                    }
                    sb.append(p / mult);
                }
                if (div && isPandigital(sb.toString()))
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] digits = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        do {
            if (digits[0] == 0)
                continue;
            StringBuilder sb = new StringBuilder();
            for (int d : digits)
                sb.append(d);
            if (hasValid(sb.toString())) {
                System.out.println(sb);
                return;
            }
        } while (prevPerm(digits));
    }

    static boolean prevPerm(int[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] <= a[i + 1])
            i--;
        if (i < 0)
            return false;
        int j = a.length - 1;
        while (a[j] >= a[i])
            j--;
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
        for (int l = i + 1, r = a.length - 1; l < r; l++, r--) {
            t = a[l];
            a[l] = a[r];
            a[r] = t;
        }
        return true;
    }
}