Detailed mathematical approach

Problem Summary

We consider hexadecimal integers with at most 16 digits, written in the usual way with no leading zero. The task is to count how many of them contain each of the three distinguished symbols \(0\), \(1\), and \(A\) at least once.

The counting is done length by length. If \(C_n\) denotes the number of valid \(n\)-digit hexadecimal numbers, then the Project Euler instance asks for

$S=\sum_{n=1}^{16} C_n,$

and the result is finally displayed in base 16. The main mathematical issue is that the first digit is restricted, so the digits \(0\), \(1\), and \(A\) do not play perfectly symmetric roles.

Mathematical Approach

For a fixed length \(n\), let the universe be all hexadecimal strings of length \(n\) whose first digit is nonzero. Among them we want exactly those that contain all three required symbols. This is a clean inclusion-exclusion problem, but the leading-digit rule changes several of the set sizes and must be handled explicitly.

Counting All \(n\)-Digit Hexadecimal Numbers

The first digit can be any of \(1,2,\dots,9,A,\dots,F\), so it has 15 choices. Every remaining position has 16 choices. Therefore

$T_n = 15 \cdot 16^{n-1}$

counts all admissible \(n\)-digit hexadecimal numbers before we impose the requirement that \(0\), \(1\), and \(A\) all appear.

The Three Forbidden Events

Define three events:

$E_0=\{\text{the digit }0\text{ never appears}\},\qquad E_1=\{\text{the digit }1\text{ never appears}\},\qquad E_A=\{\text{the digit }A\text{ never appears}\}.$

Then \(C_n\) is the number of elements of the universe that avoid none of these events, so

$C_n = T_n - |E_0 \cup E_1 \cup E_A|.$

Inclusion-exclusion expands this into single omissions, double omissions, and the triple omission.

Why Missing \(0\) Is Different from Missing \(1\) or \(A\)

This is the key asymmetry in the problem. If \(0\) is forbidden everywhere, then the leading-digit rule becomes irrelevant, because \(0\) could not have appeared in the first position anyway. But if \(1\) or \(A\) is forbidden, the first digit still cannot be \(0\), so the first position and the later positions must be counted separately.

That gives

$|E_0| = 15^n,$

because every position may use any hexadecimal symbol except \(0\). On the other hand,

$|E_1| = 14 \cdot 15^{n-1},\qquad |E_A| = 14 \cdot 15^{n-1},$

because the first digit may use any nonzero hexadecimal symbol except the forbidden one, giving 14 choices, while each later position may use any symbol except that forbidden one, giving 15 choices.

Double Omissions and the Triple Omission

Now count numbers missing two of the required symbols at once.

If both \(0\) and \(1\) are absent, the available alphabet has 14 symbols and none of them is zero, so again the leading-digit restriction disappears:

$|E_0 \cap E_1| = 14^n.$

Exactly the same reasoning gives

$|E_0 \cap E_A| = 14^n.$

If instead \(1\) and \(A\) are absent, zero is still available in later positions but not at the front, so

$|E_1 \cap E_A| = 13 \cdot 14^{n-1}.$

Finally, if all three symbols \(0\), \(1\), and \(A\) are absent, only 13 symbols remain and none of them is zero, hence

$|E_0 \cap E_1 \cap E_A| = 13^n.$

Inclusion-Exclusion for \(C_n\)

Substituting all pieces into the inclusion-exclusion formula gives

$C_n = T_n - (|E_0| + |E_1| + |E_A|) + (|E_0 \cap E_1| + |E_0 \cap E_A| + |E_1 \cap E_A|) - |E_0 \cap E_1 \cap E_A|,$

so

$C_n = 15 \cdot 16^{n-1} - \bigl(15^n + 14 \cdot 15^{n-1} + 14 \cdot 15^{n-1}\bigr) + \bigl(14^n + 14^n + 13 \cdot 14^{n-1}\bigr) - 13^n.$

Combining like terms produces the compact equivalent form

$C_n = 15 \cdot 16^{n-1} - 43 \cdot 15^{n-1} + 41 \cdot 14^{n-1} - 13^n.$

Either version is mathematically identical. The implementations follow the unsimplified inclusion-exclusion pieces directly, which keeps the combinatorial meaning visible.

Worked Example: The Case \(n=3\)

The smallest interesting length is \(n=3\), because a string cannot contain \(0\), \(1\), and \(A\) all at least once unless it has at least three positions. Plugging \(n=3\) into the formula gives

$C_3 = 15 \cdot 16^2 - 15^3 - 2 \cdot 14 \cdot 15^2 + 2 \cdot 14^3 + 13 \cdot 14^2 - 13^3 = 4.$

There is also a direct sanity check: with three positions, the digits must be exactly \(0\), \(1\), and \(A\) in some order. There are \(3! = 6\) permutations, but the two starting with \(0\) are invalid, leaving exactly four valid numbers:

$10A,\qquad 1A0,\qquad A01,\qquad A10.$

This agrees with the formula and is used by one implementation as a checkpoint.

Summing Over All Lengths

Different lengths describe disjoint sets of hexadecimal integers, so the final answer is just

$S = \sum_{n=1}^{16} C_n.$

Notice that \(C_1=C_2=0\), which the formula automatically reproduces. Because the target bound is only 16 digits, there is no need for a more elaborate recurrence or dynamic program: a short exact sum is already sufficient.

How the Code Works

The C++, Python, and Java implementations all evaluate the same length-by-length inclusion-exclusion formula. They iterate over \(n=1,2,\dots,16\), compute the seven ingredient counts for that length, and accumulate the contribution \(C_n\) into a running total.

Per-Length Arithmetic

For each \(n\), the implementation computes the total number of \(n\)-digit hexadecimal numbers, then the counts missing \(0\), missing \(1\), missing \(A\), missing each pair, and missing all three. No search tree, digit DP, or memoization is needed; everything comes from direct power expressions such as \(16^{n-1}\), \(15^n\), \(14^n\), and \(13^n\).

The three language versions differ only in the integer type used for exact arithmetic. Python relies on built-in arbitrary precision, Java uses arbitrary-precision integers explicitly, and C++ uses a fixed-width integer type large enough for this range.

Accumulation and Base-16 Output

After summing all \(C_n\), the implementation converts the final integer to uppercase hexadecimal for printing. One version also verifies the small fact \(C_3=4\) before producing the answer, which is a useful check that the inclusion-exclusion terms were assembled correctly.

Conceptually, the code is just a faithful transcription of the mathematical formula: count each forbidden pattern, combine them with signs \(+\,-\,+\,-\), then add the lengths together.

Complexity Analysis

For each length \(n\), the solver performs a constant amount of arithmetic, so if the maximum length is \(L\), the running time is \(O(L)\). In the Project Euler instance \(L=16\), this is effectively constant time.

The memory usage is \(O(1)\) beyond the storage required by the final integer itself. There are no large tables, no recursion stack, and no dependence on the number of valid hexadecimal strings. The only growth comes from exact integer arithmetic, which remains very small for this problem size.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=162
2. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
3. Hexadecimal numeral system: Wikipedia - Hexadecimal
4. Positional notation: Wikipedia - Positional notation
5. Rule of product in combinatorics: Wikipedia - Rule of product