Project Euler Problem 162

Solution

Answer: 3D58725572C62302

We count hexadecimal numbers of length at most $16$ that contain each of the digits $0$, $1$, and $\mathrm A$ at least once, with no leading zero.

The key idea is inclusion–exclusion.

Let:

$S_n$ = set of valid $n$-digit hexadecimal numbers (first digit nonzero),
We want numbers containing all of ${0,1,\mathrm A}$.

Instead of counting directly, count numbers that avoid some subset of these digits.

For a forbidden set $F\subseteq{0,1,\mathrm A}$:

there are $16-|F|$ allowed hexadecimal digits overall,
the first digit cannot be $0$.

So the first digit has

$$(16-|F|)-[0\notin F]$$

choices, where $[0\notin F]$ is $1$ if zero is allowed (because then we must exclude it from the leading position).

The remaining $n-1$ positions each have $16-|F|$ choices.

Hence:

$$f(n,F) = \text{first}\times (16-|F|)^{n-1}$$

Now apply inclusion–exclusion:

$$#(\text{contains }0,1,A) = \sum_{F\subseteq{0,1,A}} (-1)^{|F|} f(n,F)$$

and sum this over $n=1,\dots,16$.

The supplied Python code implements exactly this:

def f(n, fb):  # n-digit hex numbers avoiding digits in fb set
    a = 16 - len(fb)
    first = a - (0 not in fb)
    return (first * a**(n-1)) if first > 0 and a > 0 else 0

ans = 0
for n in range(1, 17):
    for mask in range(8):
        fb = {[0,1,10][i] for i in range(3) if mask>>i&1}
        ans += ((-1)**bin(mask).count('1')) * f(n, fb)

print(hex(ans)[2:].upper())

Code walkthrough

Function `f(n, fb)`

a = 16 - len(fb)

If fb contains forbidden digits, then a is the number of allowed hexadecimal digits.

Example:

forbid {0,1} → $16-2=14$ allowed digits.

first = a - (0 not in fb)

If zero is allowed, we must exclude it from the leading digit.

So:

if 0 is not forbidden, subtract 1,
otherwise all a digits are valid for the first position.

return (first * a**(n-1))

Choose:

first digit in first ways,
remaining digits independently in a ways.

Inclusion–exclusion loop

for mask in range(8):

There are $2^3=8$ subsets of ${0,1,A}$.

fb = {[0,1,10][i] for i in range(3) if mask>>i&1}

Construct the forbidden subset.

10 represents hexadecimal digit A.

ans += ((-1)**bin(mask).count('1')) * f(n, fb)

Apply inclusion–exclusion:

add subsets of even size,
subtract subsets of odd size.

Small sanity check

For $n=3$:

The only valid numbers are permutations of $0,1,A$ with no leading zero:

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

Exactly $4$, matching the statement.

Final verification

The count is large, as expected for all hexadecimal strings up to length $16$, but still far below the total number of 16-digit hexadecimal numbers ($\approx 16^{16}$).

Running the code gives:

$$\boxed{\texttt{3D58725572C62302}}$$

Answer: 3D58725572C62302