Problem 162: Hexadecimal Numbers

Mathematical Development

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$.

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

This is a direct inclusion-exclusion count done independently for each possible length. For a fixed number of digits $n$, the total number of valid hexadecimal strings is easy, and the only work is subtracting the strings that miss at least one of 0, 1, or A. The mathematical development already gives closed formulas for every singleton, pairwise, and triple omission case.

The program simply evaluates that formula for each length from 1 through 16 and accumulates the result. Because the problem asks for the final answer in hexadecimal, the only post-processing step is formatting the total with uppercase hexadecimal digits.

Pseudocode

Initialize the total count to zero.

For each digit length from 1 to 16:
    Count all length-$n$ hexadecimal numbers with no leading zero.
    Subtract the numbers missing `0`, missing `1`, or missing `A`.
    Add back the numbers missing each pair of these digits.
    Subtract the numbers missing all three digits.
    Add the resulting valid count into the running total.

Convert the final total to uppercase hexadecimal and return it.

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()