Problem 162: Hexadecimal Numbers

Definitions

Definition 1. An $n$-digit hexadecimal number is a string $d_1 d_2 \cdots d_n$ over the alphabet $\{0,1,\ldots,9,A,\ldots,F\}$ with $d_1 \neq 0$ and $n \geq 1$.

Definition 2. For a subset $T \subseteq \{0,1,\ldots,F\}$ and an $n$-digit hex number $x$, we write $T \subseteq \mathrm{digits}(x)$ to mean every element of $T$ appears among the digits of $x$.

Mathematical Development

Theorem 1 (Inclusion-exclusion formula). Let $S_n$ denote the set of $n$-digit hex numbers (no leading zero). Let $N(n) = |\{x \in S_n : \{0, 1, A\} \subseteq \mathrm{digits}(x)\}|$. Then:

Proof. We apply the inclusion-exclusion principle. Define:

Then $N(n) = |S_n| - |A_0 \cup A_1 \cup A_A|$, and by inclusion-exclusion:

We compute each term. An $n$-digit hex number has first digit from $\{1,\ldots,F\}$ (15 choices) and subsequent digits from $\{0,\ldots,F\}$ (16 choices each).

Singleton terms:

• $|A_0|$: No digit 0 allowed. First digit: 15 choices ($\{1,\ldots,F\}$). Each subsequent digit: 15 choices ($\{1,\ldots,F\}$). Total: $15^n$.
• $|A_1|$: No digit 1 allowed. First digit: 14 choices ($\{2,\ldots,9,A,\ldots,F\} \cup \{0\} \setminus \{0\} = \{2,\ldots,F\} \setminus \{1\}$, which has 14 elements). Subsequent digits: 15 choices ($\{0,\ldots,F\} \setminus \{1\}$). Total: $14 \cdot 15^{n-1}$.
• $|A_A|$: No digit $A$ allowed. By symmetry with $|A_1|$ (both exclude one non-zero digit): $14 \cdot 15^{n-1}$.

Pairwise terms:

• $|A_0 \cap A_1|$: No 0 or 1. First and all digits from $\{2,\ldots,F\}$ (14 elements). Total: $14^n$.
• $|A_0 \cap A_A|$: No 0 or $A$. Digits from $\{1,\ldots,9,B,\ldots,F\}$ (14 elements). Total: $14^n$.
• $|A_1 \cap A_A|$: No 1 or $A$. First digit from $\{2,\ldots,9,B,\ldots,F\}$ (13 choices). Subsequent from $\{0,2,\ldots,9,B,\ldots,F\}$ (14 choices). Total: $13 \cdot 14^{n-1}$.

Triple term:

• $|A_0 \cap A_1 \cap A_A|$: No 0, 1, or $A$. All digits from $\{2,\ldots,9,B,\ldots,F\}$ (13 elements). Total: $13^n$.

Substituting:

Theorem 2 (Summation). The total count is:

Proof. The problem asks for hex numbers with at most 16 digits containing all three target digits. A 1-digit number cannot contain three distinct digits, so $N(1) = 0$, but it is harmless to include in the sum. The result follows by linearity of summation. $\square$

Corollary (Closed-form summation). Each component of $T$ is a geometric series. For instance:

Similarly for the other five terms. All intermediate values fit in 64-bit unsigned integers.

Editorial

Count hexadecimal numbers with at most 16 digits containing all of 0, 1, and A at least once. Uses the inclusion-exclusion principle.

Pseudocode

    total = 0
    For n from 1 to 16:
        N_n = 15 * 16^(n-1)
              - 15^n
              - 2 * 14 * 15^(n-1)
              + 2 * 14^n
              + 13 * 14^(n-1)
              - 13^n
        total += N_n
    Return TO_HEX_UPPERCASE(total)

Complexity Analysis

Time. The loop runs 16 iterations, each requiring $O(1)$ big-integer multiplications. Alternatively, six geometric series can be evaluated in $O(1)$, making the total cost $O(1)$.

Space. $O(1)$.

Answer

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

/*
 * Project Euler Problem 162: Hexadecimal Numbers
 *
 * Count hex numbers with at most 16 digits containing all of {0, 1, A}.
 * Inclusion-exclusion over missing-digit sets.
 */

typedef unsigned __int128 u128;

int main() {
    auto power = [](u128 base, int exp) -> u128 {
        u128 r = 1;
        for (int i = 0; i < exp; i++) r *= base;
        return r;
    };

    u128 total = 0;
    for (int n = 1; n <= 16; n++) {
        u128 S   = 15 * power(16, n - 1);
        u128 A0  = power(15, n);
        u128 A1  = 14 * power(15, n - 1);
        u128 AA  = 14 * power(15, n - 1);
        u128 A01 = power(14, n);
        u128 A0A = power(14, n);
        u128 A1A = 13 * power(14, n - 1);
        u128 A01A = power(13, n);
        u128 bad = A0 + A1 + AA - A01 - A0A - A1A + A01A;
        total += S - bad;
    }

    // Convert to uppercase hexadecimal
    string hex;
    u128 v = total;
    if (v == 0) hex = "0";
    while (v > 0) {
        int d = (int)(v % 16);
        hex += (d < 10) ? ('0' + d) : ('A' + d - 10);
        v /= 16;
    }
    reverse(hex.begin(), hex.end());
    cout << hex << endl;
    return 0;
}

"""
Project Euler Problem 162: Hexadecimal Numbers

Count hexadecimal numbers with at most 16 digits containing all of 0, 1, and A
at least once.  Uses the inclusion-exclusion principle.
"""


def solve():
    total = 0
    for n in range(1, 17):
        S = 15 * 16 ** (n - 1)
        A0 = 15 ** n
        A1 = 14 * 15 ** (n - 1)
        AA = 14 * 15 ** (n - 1)
        A01 = 14 ** n
        A0A = 14 ** n
        A1A = 13 * 14 ** (n - 1)
        A01A = 13 ** n
        bad = A0 + A1 + AA - A01 - A0A - A1A + A01A
        total += S - bad
    print(f"{total:X}")


solve()