Project Euler 162: Find hexadecimal numbers containing at most 16 hexadecimal digits exist with all of the digits 0, 1 and A present at least once

Problem Description

In the hexadecimal number system numbers are represented using 16 different digits:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
The hexadecimal number AF when written in the decimal number system equals 10×16+15=175.

In the 3-digit hexadecimal numbers 10A, 1A0, A10, and A01 the digits 0,1 and A are all present.
Like numbers written in base ten we write hexadecimal numbers without leading zeroes.

How many hexadecimal numbers containing at most sixteen hexadecimal digits exist with all of the digits 0,1, and A present at least once?
Give your answer as a hexadecimal number.

(A,B,C,D,E and F in upper case, without any leading or trailing code that marks the number as hexadecimal and without leading zeroes , e.g. 1A3F and not: 1a3f and not 0x1a3f and not $1A3F and not #1A3F and not 0000001A3F)

Analysis

This is a typical application of the inclusion-exclusion principle. It is helpful in answering questions where the number of elements of a set are required but not the elements themselves. We just need to know the number of elements in two sets and subtract the number in the intersection.

The equation, after combining some terms looks like: 15 x 16^(n-1) + 41 x 14^(n-1) – (43 x 15^(n-1) + 13ⁿ) for each possible hex number containing n digits {3..16}.

Since the first digit is non zero the total possibilities without consideration for the constraints is 15 x 16^(n-1). Then remove those with no {0, 1, A}. But we need to add back in those that have no 1 or 0, no 1 or A, no 0 or A. Then remove the duplicates that, again, have no {0, 1, A}. There are 258 4 digit hex numbers that follow this pattern.

Project Euler 162 Solution

Afterthoughts

• This code could be modified to broaden the range of counting problems it could solve.