Problem 32: Pandigital Products

View on Project Euler

Project Euler Problem 32 Solution

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

Problem Summary A multiplicand \(a\), a multiplier \(b\), and a product \(p=ab\) form a valid identity when the decimal digits of \(a\), \(b\), and \(p\) together use each of \(1,2,\dots,9\) exactly once. The task is to find every such identity and sum the distinct product values, counting the same product only once even if it has more than one factorization. The standard example is \(39\times 186=7254\), because the concatenation \(391867254\) is a permutation of \(123456789\). Mathematical Approach The solution is a finite search, but it is not an arbitrary brute-force search. A short digit-length argument collapses the problem to two search families, and a simple invariant decides whether a candidate identity is truly 1-to-9 pandigital. The digit-length equation leaves only two possibilities Let \(x=d(a)\), \(y=d(b)\), and \(z=d(p)\), where \(d(n)\) is the number of decimal digits of \(n\). A valid pandigital identity uses exactly nine digits overall, so $$x+y+z=9.$$ For the product of an \(x\)-digit number and a \(y\)-digit number, the result has either \(x+y-1\) digits or \(x+y\) digits. Therefore $$z\in\{x+y-1,\ x+y\}.$$ If \(z=x+y\), then \(9=2(x+y)\), which is impossible because the left-hand side is odd. So the only remaining case is \(z=x+y-1\), giving $$9=x+y+(x+y-1)=2(x+y)-1,$$ hence \(x+y=5\) and \(z=4\)....

Detailed mathematical approach

Problem Summary

A multiplicand \(a\), a multiplier \(b\), and a product \(p=ab\) form a valid identity when the decimal digits of \(a\), \(b\), and \(p\) together use each of \(1,2,\dots,9\) exactly once. The task is to find every such identity and sum the distinct product values, counting the same product only once even if it has more than one factorization.

The standard example is \(39\times 186=7254\), because the concatenation \(391867254\) is a permutation of \(123456789\).

Mathematical Approach

The solution is a finite search, but it is not an arbitrary brute-force search. A short digit-length argument collapses the problem to two search families, and a simple invariant decides whether a candidate identity is truly 1-to-9 pandigital.

The digit-length equation leaves only two possibilities

Let \(x=d(a)\), \(y=d(b)\), and \(z=d(p)\), where \(d(n)\) is the number of decimal digits of \(n\). A valid pandigital identity uses exactly nine digits overall, so

$$x+y+z=9.$$

For the product of an \(x\)-digit number and a \(y\)-digit number, the result has either \(x+y-1\) digits or \(x+y\) digits. Therefore

$$z\in\{x+y-1,\ x+y\}.$$

If \(z=x+y\), then \(9=2(x+y)\), which is impossible because the left-hand side is odd. So the only remaining case is \(z=x+y-1\), giving

$$9=x+y+(x+y-1)=2(x+y)-1,$$

hence \(x+y=5\) and \(z=4\). After ordering the two factors by size of digit-length, the only admissible triples are

$$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $$

That exact deduction explains why the implementations search only the cases \(1\)-digit \(\times\) \(4\)-digit and \(2\)-digit \(\times\) \(3\)-digit. No other digit pattern can succeed.

The pandigital condition as a digit-usage invariant

For any candidate \((a,b,p)\), scan the decimal digits of \(a\), then \(b\), then \(p\). The triple is valid if and only if three conditions all hold: no digit is \(0\), no digit is repeated, and exactly nine digits are seen in total. Once those three conditions are satisfied, the digit set must be exactly \(\{1,2,\dots,9\}\).

The implementations encode this with a ten-entry boolean table indexed by the digit. Encountering a zero or a repeated digit causes immediate rejection, so most bad candidates fail before the full scan is finished.

Why distinct products must be deduplicated

The problem asks for the sum of distinct products, not the sum over successful factorizations. This matters because one product can arise from more than one pandigital identity. A well-known example is

$$12\times 483=5796,\qquad 42\times 138=5796.$$

Both identities are valid, but the product \(5796\) must contribute only once. That is why the implementations store successful products in a set before taking the final sum.

Worked examples

The positive checkpoint

$$39\times 186=7254$$

belongs to the \((2,3,4)\) case. Its digits are \(3,9,1,8,6,7,2,5,4\): there is no zero, no repetition, and the total count is nine, so it is valid.

The negative checkpoint

$$12\times 34=408$$

fails immediately because the product contains the digit \(0\). It also has only \(2+2+3=7\) digits altogether, so it cannot possibly be a 1-to-9 pandigital identity.

How the Code Works

Enumerating the only viable search regions

The C++, Python, and Java implementations run two nested-loop searches matching the two digit patterns above. The first search tests every \(a\in\{1,\dots,9\}\) against every four-digit \(b\in\{1234,\dots,9876\}\). The second tests every two-digit \(a\in\{12,\dots,98\}\) against every three-digit \(b\in\{123,\dots,987\}\). This removes impossible factor-length shapes such as \(3\)-digit \(\times\) \(3\)-digit before the digit checker is ever called.

Validating digits with a shared test

For each pair, the implementation computes \(p=ab\) and feeds \(a\), \(b\), and \(p\) into the same digit-usage test. The loops deliberately keep simple rectangular ranges instead of pre-filtering zeros or repeated digits inside the factors; the shared validator rejects those cases in constant time. A wrong product length is also handled naturally: if the combined digit count is not exactly nine, the candidate fails at the end of the scan.

Deduplication, summation, and sanity checks

Whenever a candidate passes the digit test, its product is inserted into a set. After both searches finish, the program sums the set elements to obtain the required answer. Before the main computation, each implementation also performs two small checkpoints: one known valid pandigital identity and one known invalid identity.

Complexity Analysis

The first search examines \(9\times 8643=77{,}787\) pairs, and the second examines \(87\times 865=75{,}255\) pairs, so the total number of tested products is \(153{,}042\). Each test performs one multiplication and a scan of at most ten decimal digits, so the work per candidate is \(O(1)\). For this fixed problem instance, the running time is therefore tiny.

The digit validator itself uses constant working memory. The only growing structure is the set of successful products, and for Problem 32 that set remains very small. In practice the computation completes essentially instantly.

Footnotes and References

  1. Problem page: Project Euler 32 - Pandigital products
  2. Pandigital numbers: Wikipedia - Pandigital number
  3. Decimal positional notation: Wikipedia - Positional notation
  4. Sets and distinct elements: Wikipedia - Set (mathematics)

Problem 32 source code

C++

#include <array>
#include <iostream>
#include <set>
#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_triplet(const int a, const int b, const int product) {
    std::array<bool, 10> used{};
    used.fill(false);

    int digits_seen = 0;
    auto add_digits = [&](int value) -> bool {
        while (value > 0) {
            const int d = value % 10;
            if (d == 0 || used[static_cast<std::size_t>(d)]) {
                return false;
            }
            used[static_cast<std::size_t>(d)] = true;
            ++digits_seen;
            value /= 10;
        }
        return true;
    };

    if (!add_digits(a) || !add_digits(b) || !add_digits(product)) {
        return false;
    }

    if (digits_seen != 9) {
        return false;
    }
    for (int d = 1; d <= 9; ++d) {
        if (!used[static_cast<std::size_t>(d)]) {
            return false;
        }
    }
    return true;
}

int solve() {
    std::set<int> products;

    for (int a = 1; a <= 9; ++a) {
        for (int b = 1234; b <= 9876; ++b) {
            const int p = a * b;
            if (is_1_to_9_pandigital_triplet(a, b, p)) {
                products.insert(p);
            }
        }
    }

    for (int a = 12; a <= 98; ++a) {
        for (int b = 123; b <= 987; ++b) {
            const int p = a * b;
            if (is_1_to_9_pandigital_triplet(a, b, p)) {
                products.insert(p);
            }
        }
    }

    int total = 0;
    for (const int p : products) {
        total += p;
    }
    return total;
}

bool run_checkpoints() {
    if (!is_1_to_9_pandigital_triplet(39, 186, 7254)) {
        std::cerr << "Checkpoint failed for example identity" << '\n';
        return false;
    }
    if (is_1_to_9_pandigital_triplet(12, 34, 408)) {
        std::cerr << "Checkpoint failed for non-pandigital identity" << '\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_triplet(a, b, product):
    used = [False] * 10
    digits_seen = 0
    
    def add_digits(value):
        nonlocal digits_seen
        while value > 0:
            d = value % 10
            if d == 0 or used[d]:
                return False
            used[d] = True
            digits_seen += 1
            value //= 10
        return True
    
    if not add_digits(a) or not add_digits(b) or not add_digits(product):
        return False
    
    if digits_seen != 9:
        return False
    
    for d in range(1, 10):
        if not used[d]:
            return False
    
    return True

def solve():
    products = set()
    
    for a in range(1, 10):
        for b in range(1234, 9877):
            p = a * b
            if is_1_to_9_pandigital_triplet(a, b, p):
                products.add(p)
    
    for a in range(12, 99):
        for b in range(123, 988):
            p = a * b
            if is_1_to_9_pandigital_triplet(a, b, p):
                products.add(p)
    
    return sum(products)

def run_checkpoints():
    if not is_1_to_9_pandigital_triplet(39, 186, 7254):
        sys.stderr.write("Checkpoint failed for example identity\n")
        return False
    if is_1_to_9_pandigital_triplet(12, 34, 408):
        sys.stderr.write("Checkpoint failed for non-pandigital identity\n")
        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:
            sys.stderr.write(f"Unknown argument: {arg}\n")
            return 1
    
    if run_checkpoints_flag and not run_checkpoints():
        return 2
    
    print(solve())
    return 0

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

Java

import java.util.*;

public class Euler32 {
    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 (arg.equals("--skip-checkpoints")) {
                options.runCheckpoints = false;
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            return false;
        }
        return true;
    }

    private static boolean is_1_to_9_pandigital_triplet(int a, int b, int product) {
        boolean[] used = new boolean[10];
        int digitsSeen = 0;

        digitsSeen = addDigits(a, used, digitsSeen);
        if (digitsSeen == -1) return false;
        digitsSeen = addDigits(b, used, digitsSeen);
        if (digitsSeen == -1) return false;
        digitsSeen = addDigits(product, used, digitsSeen);
        if (digitsSeen == -1) return false;

        if (digitsSeen != 9) {
            return false;
        }
        for (int d = 1; d <= 9; d++) {
            if (!used[d]) {
                return false;
            }
        }
        return true;
    }

    private static int addDigits(int value, boolean[] used, int digitsSeen) {
        int v = value;
        while (v > 0) {
            int d = v % 10;
            if (d == 0 || used[d]) {
                return -1;
            }
            used[d] = true;
            digitsSeen++;
            v /= 10;
        }
        return digitsSeen;
    }

    private static int solve() {
        Set<Integer> products = new HashSet<>();

        for (int a = 1; a <= 9; a++) {
            for (int b = 1234; b <= 9876; b++) {
                int p = a * b;
                if (is_1_to_9_pandigital_triplet(a, b, p)) {
                    products.add(p);
                }
            }
        }

        for (int a = 12; a <= 98; a++) {
            for (int b = 123; b <= 987; b++) {
                int p = a * b;
                if (is_1_to_9_pandigital_triplet(a, b, p)) {
                    products.add(p);
                }
            }
        }

        int total = 0;
        for (int p : products) {
            total += p;
        }
        return total;
    }

    private static boolean runCheckpoints() {
        if (!is_1_to_9_pandigital_triplet(39, 186, 7254)) {
            System.err.println("Checkpoint failed for example identity");
            return false;
        }
        if (is_1_to_9_pandigital_triplet(12, 34, 408)) {
            System.err.println("Checkpoint failed for non-pandigital identity");
            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());
    }
}