Problem 172: Investigating Numbers with Few Repeated Digits

Project Euler Problem 172 Solution

EulerSolve provides an optimized solution for Project Euler Problem 172, Investigating Numbers with Few Repeated Digits, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Project Euler 172 asks for the number of 18-digit decimal numbers in which no digit appears more than three times. The first digit cannot be 0, so the leading position is the only asymmetric part of the count; after that, the ten digits $0,1,\dots,9$ are handled uniformly. The implementations are written around the slightly more general parameters $L$ for the length and $R$ for the repetition cap. For this problem, $L=18$ and $R=3$. Mathematical Approach The key move is to stop thinking about concrete 18-digit strings and instead count how many times each digit is used. Once those multiplicities are fixed, the remaining work is a multinomial count with a correction for leading zero. The Right State Space: Bounded Digit Counts Let $c_d$ denote the number of occurrences of digit $d$. Every valid number determines a vector $$c=(c_0,c_1,\dots,c_9)$$ such that $$\sum_{d=0}^{9} c_d=L,\qquad 0\le c_d\le R.$$ For Euler 172 this becomes $$\sum_{d=0}^{9} c_d=18,\qquad 0\le c_d\le 3.$$ So the problem is really a sum over all bounded compositions of 18 into 10 parts. The recursion in the implementations enumerates exactly these vectors, one digit at a time. Counting One Multiplicity Vector Fix one admissible vector $c$....

Detailed mathematical approach

Problem Summary

We must count the $18$-digit numbers, the integers from $10^{17}$ to $10^{18}-1$, in which none of the ten digits $0,1,\dots,9$ occurs more than three times. Numbers are written without leading zeros, so the first digit is never $0$. For example, $112233445566778899$ qualifies, while $100000000000000000$, with seventeen zeros, does not. The statement gives no example values. ^[1] For positive integers $L$ and $R$ we write $A(L,R)$ for the number of $L$-digit numbers in which no digit occurs more than $R$ times; the task asks for $A(18,3)$.

The whole solution in one sentence: whether a number qualifies depends only on how often each digit occurs, so we run through the $82885$ possible lists of ten digit frequencies, each at most $3$ and together $18$, count the numbers with each list by a multinomial coefficient corrected for a leading $0$, and add up these counts.

Mathematical Approach

Testing all $9\cdot10^{17}$ numbers one by one is out of the question. Instead we group the numbers by their digit frequencies and count each group with one formula.

1. The first lengths by hand

A number with $L$ digits is a string $d_1d_2\cdots d_L$ of digits with $d_1\ne0$, so there are $9\cdot10^{L-1}$ of them. With at most three digits no digit can occur four times, so $A(1,3)=9$, $A(2,3)=90$ and $A(3,3)=900$. Among the four-digit numbers only $1111,2222,\dots,9999$ have a digit four times, since $0000$ is not a four-digit number, so $A(4,3)=9000-9=8991$.

For five digits we remove the numbers in which some digit occurs four or five times. Five equal digits give $9$ numbers. If a nonzero digit $a$ occurs exactly four times, the fifth digit $b\ne a$ has $9$ values and $5$ places, but $b=0$ may not stand in front, which leaves $5\cdot9-1=44$ numbers for each $a$, $396$ in all. Four zeros force the fifth digit to the front: $10000,20000,\dots,90000$. Hence $A(5,3)=90000-9-396-9$${}=89586$, and a computer count gives $A(6,3)=888570$. The cases multiply with every further digit, so we need a systematic method.

2. Only the digit counts matter

For a string of digits let $c_d$ be the number of times the digit $d$ occurs, and call $c=(c_0,c_1,\dots,c_9)$ its count vector; for example, $123456789012345678$ has the count vector $(1,2,2,2,2,2,2,2,2,1)$. The entries add up to the length,

$$c_0+c_1+\dots+c_9=L,$$

and a number qualifies exactly when every entry is at most $R$. We call such vectors admissible and write $\mathcal C(L,R)$ for their set. Every number has exactly one count vector, and the numbers with count vector $c$ are the orders of its digits that do not begin with $0$. With $N(c)$ the number of these orders,

$$A(L,R)=\sum_{c\in\mathcal C(L,R)}N(c).$$

3. Arranging a multiset of digits

Claim. The number of strings of length $L$ in which each digit $d$ occurs exactly $c_d$ times is the multinomial coefficient ^[2]

$$M(c)=\frac{L!}{c_0!\,c_1!\cdots c_9!}.$$

Proof. Label the copies of each digit, for instance $0_1$ and $0_2$ for two zeros. The $L$ labelled symbols are all different and can be put in $L!$ orders. Erasing the labels turns each labelled order into a digit string, and each digit string comes from exactly $c_0!\,c_1!\cdots c_9!$ labelled orders, because the copies of each digit $d$ can be permuted among their places in $c_d!$ ways. Dividing gives $M(c)$; digits that do not occur contribute $0!=1$. $\square$

For the digits $0,0,1,2$ this gives $4!/2!=12$ strings: $0012$, $0021$, $0102$, $0120$, $0201$, $0210$, $1002$, $1020$, $1200$, $2001$, $2010$ and $2100$.

4. The first digit must not be 0

Six of these twelve strings begin with $0$. In general, a string that begins with $0$ is a $0$ followed by an order of the other digits, whose count vector is $c$ with $c_0$ lowered by one. By Section 3 there are

$$\frac{(L-1)!}{(c_0-1)!\,c_1!\cdots c_9!}=\frac{c_0}{L}\,M(c)$$

of them if $c_0\ge1$, and none if $c_0=0$. Intuitively, in the labelled orders of Section 3 each of the $L$ symbols stands in front equally often, and $c_0$ of them are zeros. Subtracting gives

$$N(c)=\frac{(L-c_0)\,(L-1)!}{c_0!\,c_1!\cdots c_9!},$$

which also holds for $c_0=0$. For $0,0,1,2$ it gives $(4-2)\cdot3!/2!=6$, the numbers $1002$, $1020$, $1200$, $2001$, $2010$ and $2100$.

5. Worked example: all four-digit numbers

For $L=4$ and $R=3$ we sort the admissible vectors by their nonzero entries and take $N(c)$ from Section 4.

Four different digits, $M=24$: the $\binom94=126$ vectors without $0$ give $N=24$ each, and the $\binom93=84$ vectors with $c_0=1$ give $N=18$ each, together $3024+1512=4536$.
One digit twice and two digits once, $M=12$: $9\cdot\binom82=252$ vectors without $0$ give $N=12$, $9\cdot8=72$ vectors with $c_0=1$ give $N=9$, and $\binom92=36$ vectors with $c_0=2$ give $N=6$, together $3024+648+216=3888$.
Two digits twice, $M=6$: $36$ vectors without $0$ give $N=6$, and $9$ vectors with $c_0=2$ give $N=3$, together $243$.
One digit three times and one digit once, $M=4$: $72$ vectors without $0$ give $N=4$, $9$ with $c_0=1$ give $N=3$, and $9$ with $c_0=3$ give $N=1$, together $324$.

The four groups add up to $4536+3888+243+324=8991$, the value of $A(4,3)$ from Section 1, using $210+360+45+90=705$ admissible vectors. The excluded vectors, one digit four times, give $N=1$ for each nonzero digit and $N=0$ for $c_0=4$, and indeed $8991+9=9000$.

6. How many count vectors there are

Without the cap, a count vector with sum $n$ is a row of $n$ stars cut by nine bars into ten groups, one per digit. Choosing the places of the bars among $n+9$ places gives $\binom{n+9}{9}$ vectors, the stars and bars count; ^[3] for $n=18$ that is $\binom{27}9=4686825$. The cap removes the vectors with an entry of at least $4$, and the inclusion–exclusion principle removes each of them exactly once: it subtracts the vectors with one chosen large entry, adds back those with two, and so on, and a vector with $j\ge1$ large entries is removed $\binom j1-\binom j2+\dots=1$ time, by the binomial theorem. ^[4] Lowering $k$ chosen entries by $4$ leaves an arbitrary vector with sum $L-4k$, so

$$|\mathcal C(L,3)|=\sum_{k\ge0}(-1)^k\binom{10}{k}\binom{L-4k+9}{9},$$

with only the terms $4k\le L$. For $L=4$ this is $715-10=705$, the count of Section 5, and for $L=18$

$$\begin{aligned}&4686825-8171900+4157010\\&\quad-600600+11550=82885.\end{aligned}$$

So the sum of Section 2 has only $82885$ terms.

7. Nine tenths of all digit strings

Let $W(L,R)$ count all strings of $L$ digits, leading zeros allowed, in which no digit occurs more than $R$ times; it is the sum of $M(c)$ over $\mathcal C(L,R)$. Replacing each digit $d$ by $d+1$, and $9$ by $0$, maps these strings one-to-one onto themselves, since it only permutes the entries of the count vector, and it maps the strings that begin with $d$ onto those that begin with $d+1$. So each digit begins a tenth of the strings, and

$$A(L,R)=\frac{9}{10}\,W(L,R).$$

For $L=4$ only the ten strings $0000,1111,\dots,9999$ fail, so $W(4,3)=9990$, and nine tenths of it is $8991$. $W$ can also be read off a polynomial. In

$$\Bigl(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\Bigr)^{10}$$

taking $x^{c_d}/c_d!$ from the bracket of each digit $d$ produces $x^L/(c_0!\cdots c_9!)$ once for every admissible vector, so $L!$ times the coefficient of $x^L$ is $W(L,3)$. This is the exponential generating function of the strings, the standard tool for counting orders of labelled positions. ^[5]

8. Running through the vectors digit by digit

The programs run through the vectors with a depth-first search, a recursion that fixes $c_0$, then $c_1$, and so on, and returns to the last open choice when a branch is finished. ^[6] A call at level $d\le9$ knows the number $r=L-(c_0+\dots+c_{d-1})$ of free places and the product $D=c_0!\cdots c_{d-1}!$; it tries every $c_d$ from $0$ to $\min(R,r)$ and calls level $d+1$ with $r-c_d$ and $D\cdot c_d!$. At level $10$ we have $D=c_0!\cdots c_9!$. If $r\gt0$, the entries add up to less than $L$ and the vector is dropped; otherwise it is admissible, and the call adds

$$\frac{L!}{D}-\frac{(L-1)!}{D'},$$

where $D'=(c_0-1)!\,c_1!\cdots c_9!$ and the second term, the strings that begin with $0$, is used only if $c_0\ge1$. By Sections 3 and 4 this is $N(c)$. For example, with $L=4$ and $R=3$ the choices $c_0=2$, $c_1=1$, $c_2=1$ leave $2$, $1$ and $0$ free places, so all later entries are $0$; at level $10$ we have $D=2$ and $D'=1$, and the call adds $4!/2-3!/1=6$, the six numbers of Section 4. Every vector with entries from $0$ to $R$ and sum at most $L$ is reached by exactly one chain of choices, so every admissible vector is counted once and the total is $A(L,R)$.

Since only the bound $r$ is tested, many chains end with $r\gt0$: for $L=18$ the recursion makes $1207833$ calls and reaches $877470$ vectors at level $10$, of which $82885$ are kept. Pruning the branches that cannot succeed, those with $r-c_d$ above $3$ times the number of digits still to come, would reach only the admissible vectors, with $218591$ calls; at this size the difference hardly matters.

How the Code Works

The C++ program ^[7] keeps the length and the cap in Options, with the defaults $18$ and $3$. parse_arguments accepts --length=L, --max-repeats=R and --skip-checkpoints, with parse_int_after_prefix reading the digits; an unknown argument or a value below $1$ gives exit code $1$. Unless skipped, run_checkpoints requires solve(4, 3) to be $8991$ and solve(3, 3) to be $900$, the values of Section 1, or the program ends with exit code $2$. Finally main prints solve(length, max_repeats), that is $A(L,R)$, through to_string_u128, which builds the decimal digits by repeated division by $10$, since the standard streams cannot print 128-bit integers.

solve stores $0!,1!,\dots,L!$ in the vector fact as unsigned __int128 values, the 128-bit integers that GCC and Clang offer as an extension, ^[8] and keeps the array counts for $c_0,\dots,c_9$ and the sum total. The search of Section 8 is the lambda dfs. Since dfs is declared with auto, its name cannot be used inside its own initializer, so the lambda receives itself as the argument self and recurses with self(self, digit + 1, remaining - c, denom * fact[c]), where digit, remaining and denom are $d$, $r$ and $D$. Each choice is stored in counts[digit] before the call, so at level $10$ the array holds the current vector. There fact[length] / denom is $M(c)$; if counts[0] > 0, then denom2 = (denom / fact[counts[0]]) * fact[counts[0] - 1] is $D'$, and fact[length - 1] / denom2 counts the strings that begin with $0$. Both divisions are exact, since they give multinomial coefficients, and total grows by their difference.

For the default parameters all values are small: $18!=6402373705728000$ is below $2^{63}$, the largest denominator is $(3!)^6=46656$, and the total is below $9\cdot10^{17}$. The 128-bit type keeps the factorials exact up to $L=34$, since $34!\lt2^{128}\lt35!$, and the count, below $9\cdot10^{L-1}$, fits as well. From $L=35$ on, the factorials wrap around modulo $2^{128}$ and the results can no longer be trusted: --length=35 --max-repeats=4 prints a wrong number without warning, and for $L=R=130$ a denominator even becomes $0$, because $130!$ contains the factor $2$ exactly $128$ times, so that the division is undefined. Huge option values are not guarded either: the digits are accumulated in an int without an overflow check, and signed overflow is undefined behaviour. ^[9] The default run is not affected.

The Python program fixes length = 18 and max_rep = 3 and runs the same recursion as a nested function dfs that updates total through nonlocal. The list counts is created after dfs is defined, which works because Python looks names up at call time, and Python integers are unbounded. The Java program uses static fields and a static method dfs, with the factorials, the denominators and the total in long, whose range up to $2^{63}-1$ suffices by the bounds above. ^[10] Neither has options or checkpoints.

Complexity and Verification

Creating a call costs one multiplication, for its denominator, and an admissible vector at level $10$ a few more operations, so the running time is proportional to the number of calls, $1207833$ for $L=18$. Each level has at most $R+1$ times as many calls as the one above it, which bounds the total by $1+4+\dots+4^{10}=1398101$ for $R=3$, and by $O((R+1)^{10})$ in general. The memory holds $L+1$ factorials, ten counters and a recursion eleven calls deep. On a desktop computer each program takes well under a second.

The C++ checkpoints test $A(4,3)$ and $A(3,3)$. For this article we also checked:

Testing every integer with at most six digits confirms $A(L,R)$ for $L\le6$ and $R\le4$, for instance $A(6,3)=888570$.
A copy of the published recursion with assertions confirms at every admissible vector that both divisions are exact and that the two terms of Section 8 give the formula of Section 4. It also produced the search statistics above.
A dynamic programme, which builds the answer from the stored results of smaller subproblems, ^[11] walks along the number and stores how many prefixes lead to each state, the state saying how many digits have been used exactly $0,1,\dots,R$ times. After the first digit, with $9$ choices, all ten digits play the same role, so appending one of the $h_k$ digits used $k\lt R$ times moves one digit from class $k$ to class $k+1$ and multiplies the number of prefixes by $h_k$. Without any multinomial coefficient it agrees with the recursion for all $L\le30$ and $R\le5$, including $L=18$, $R=3$, and so does $\tfrac{9}{10}W(L,R)$ from Section 7.
The three published programs, the C++ one built with both GCC and Clang, print the same number, equal to both independent counts. With options, the C++ program agrees with the dynamic programme for all $L\le34$ and $R\le4$, and for $R=34$ with $L\le12$; it fails for $L=35$, $36$ and $40$ with $R=4$.

These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The leading-zero correction, the number of admissible vectors, the nine-tenths symmetry and the search statistics are derived in this article.

Project Euler 172 — Few Repeated Digits. The official statement asks how many 18-digit numbers n, written without leading zeros, have no digit that occurs more than three times in n. It gives no example values.
Wikipedia — Permutation. The number of distinct permutations of a multiset whose multiplicities m₁, …, mₗ add up to n is the multinomial coefficient n!/(m₁!⋯mₗ!).
Wikipedia — Stars and bars (combinatorics). Theorem two: the number of k-tuples of non-negative integers with sum n is C(n + k − 1, k − 1); Section 6 uses it with k = 10.
Wikipedia — Inclusion–exclusion principle. The principle for n finite sets is an alternating sum over all intersections; its complementary form counts the elements that lie in none of the sets.
Wikipedia — Generating function. The exponential generating function of a sequence aₙ is Σ aₙxⁿ/n!; such functions are generally more convenient than ordinary ones for enumeration problems with labelled objects.
Wikipedia — Backtracking. Backtracking builds candidates step by step, explores the tree of partial candidates in depth-first order, and prunes a subtree as soon as its partial candidate cannot be completed to a solution.
C++ — Euler172.cpp. The linked immutable C++ revision contains parse_arguments, solve with the recursive lambda dfs, run_checkpoints and to_string_u128. It is the implementation record for this article.
GCC manual — 128-bit Integers. As an extension, the types __int128 and unsigned __int128 are supported for targets that have an integer mode wide enough to hold 128 bits.
cppreference — Arithmetic operators. Unsigned integer arithmetic is always performed modulo 2ⁿ, where n is the number of bits of the type, while signed integer overflow and division by zero are undefined behaviour.
Python — numeric types documents that integers have unlimited precision, and the Java Language Specification, §4.2.1 gives the range of long as −9223372036854775808 to 9223372036854775807.
Wikipedia — Dynamic programming. The method breaks a problem down into simpler sub-problems in a recursive manner and solves each sub-problem only once.

Problem 172 source code

C++

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

namespace {

using u128 = unsigned __int128;

struct Options {
    int length = 18;
    int max_repeats = 3;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return 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;
        }
        if (parse_int_after_prefix(arg, "--length=", options.length) ||
            parse_int_after_prefix(arg, "--max-repeats=", options.max_repeats)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.length >= 1 && options.max_repeats >= 1;
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

u128 solve(const int length, const int max_repeats) {
    std::vector<u128> fact(static_cast<std::size_t>(length + 1), 1);
    for (int i = 1; i <= length; ++i) {
        fact[static_cast<std::size_t>(i)] = fact[static_cast<std::size_t>(i - 1)] * static_cast<u128>(i);
    }

    std::array<int, 10> counts{};
    u128 total = 0;

    const auto dfs = [&](auto&& self, int digit, int remaining, u128 denom) -> void {
        if (digit == 10) {
            if (remaining != 0) {
                return;
            }

            const u128 all_permutations = fact[static_cast<std::size_t>(length)] / denom;
            u128 leading_zero = 0;
            if (counts[0] > 0) {
                const u128 denom2 = (denom / fact[static_cast<std::size_t>(counts[0])]) *
                                    fact[static_cast<std::size_t>(counts[0] - 1)];
                leading_zero = fact[static_cast<std::size_t>(length - 1)] / denom2;
            }

            total += all_permutations - leading_zero;
            return;
        }

        const int max_take = std::min(max_repeats, remaining);
        for (int c = 0; c <= max_take; ++c) {
            counts[static_cast<std::size_t>(digit)] = c;
            self(self, digit + 1, remaining - c, denom * fact[static_cast<std::size_t>(c)]);
        }
    };

    dfs(dfs, 0, length, 1);
    return total;
}

bool run_checkpoints() {
    if (to_string_u128(solve(4, 3)) != "8991") {
        std::cerr << "Checkpoint failed for length=4" << '\n';
        return false;
    }
    if (to_string_u128(solve(3, 3)) != "900") {
        std::cerr << "Checkpoint failed for length=3" << '\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 << to_string_u128(solve(options.length, options.max_repeats)) << '\n';
    return 0;
}

Python

# Problem 172: Investigating numbers with few repeated digits
# Count 18-digit numbers where no digit occurs more than 3 times.

import math

def solve():
    length = 18
    max_rep = 3
    fact = [math.factorial(i) for i in range(length+1)]
    total = 0

    def dfs(digit, remaining, denom):
        nonlocal total
        if digit == 10:
            if remaining != 0: return
            all_perm = fact[length] // denom
            lz = 0
            if counts[0] > 0:
                denom2 = (denom // fact[counts[0]]) * fact[counts[0]-1]
                lz = fact[length-1] // denom2
            total += all_perm - lz
            return
        mx = min(max_rep, remaining)
        for c in range(mx+1):
            counts[digit] = c
            dfs(digit+1, remaining-c, denom * fact[c])

    counts = [0]*10
    dfs(0, length, 1)
    print(total)

solve()

Java

public class Euler172 {
    static int LENGTH = 18, MAX_REP = 3;
    static long[] fact;
    static int[] counts = new int[10];
    static long total = 0;

    static void dfs(int digit, int remaining, long denom) {
        if (digit == 10) {
            if (remaining != 0)
                return;
            long all = fact[LENGTH] / denom;
            long lz = 0;
            if (counts[0] > 0) {
                long d2 = (denom / fact[counts[0]]) * fact[counts[0] - 1];
                lz = fact[LENGTH - 1] / d2;
            }
            total += all - lz;
            return;
        }
        int mx = Math.min(MAX_REP, remaining);
        for (int c = 0; c <= mx; c++) {
            counts[digit] = c;
            dfs(digit + 1, remaining - c, denom * fact[c]);
        }
    }

    public static void main(String[] args) {
        fact = new long[LENGTH + 1];
        fact[0] = 1;
        for (int i = 1; i <= LENGTH; i++)
            fact[i] = fact[i - 1] * i;
        dfs(0, LENGTH, 1);
        System.out.println(total);
    }
}