Problem 162: Hexadecimal Numbers

Project Euler Problem 162 Solution

EulerSolve provides an optimized solution for Project Euler Problem 162, Hexadecimal Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

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

Detailed mathematical approach

Problem Summary

Hexadecimal numbers are written with the sixteen digits $0,1,\dots,9$ and $\mathrm A,\mathrm B,\mathrm C,\mathrm D,\mathrm E,\mathrm F$, where the letters stand for the values $10$ to $15$; for example $\mathrm{AF}=10\cdot16+15=175$. As in base ten, numbers are written without leading zeros. Among all hexadecimal numbers with at most sixteen digits we must count those in which each of the three digits $0$, $1$ and $\mathrm A$ appears at least once, and give the count in hexadecimal, with upper-case letters, without leading zeros and without any marker such as 0x. The statement shows the four three-digit examples $10\mathrm A$, $1\mathrm A0$, $\mathrm A10$ and $\mathrm A01$. ^[1]

The whole solution in one sentence: for every length $n$ from $1$ to $16$ we count all numbers with $n$ digits, remove with the inclusion–exclusion principle those in which $0$, $1$ or $\mathrm A$ is missing, taking care that the first digit can never be $0$, and finally add the sixteen counts and write the sum in base $16$.

Mathematical Approach

1. Numbers as strings of digits

A hexadecimal number with exactly $n$ digits is a string $d_1d_2\cdots d_n$ of hexadecimal digits with $d_1\ne0$, and its value is $\sum_{i=1}^{n}d_i\,16^{n-i}$. ^[2] Because leading zeros are never written, every positive integer has exactly one such string, and the numbers with at most sixteen digits are the integers from $1$ to $16^{16}-1$. Zero, written $0$, contains neither $1$ nor $\mathrm A$, so it never counts. Let $U_n$ be the set of strings of length $n$ whose first digit is not $0$. The first digit has $15$ choices and each of the other $n-1$ digits has $16$, so by the rule of product ^[3]

$$|U_n|=15\cdot16^{n-1}.$$

Let $C_n$ be the number of strings in $U_n$ that contain $0$, $1$ and $\mathrm A$. Every number has exactly one length, so the requested count is $S(16)$, where $S(L)=C_1+C_2+\cdots+C_L$ is the number of valid numbers with at most $L$ digits.

2. The first lengths by hand

One or two digits cannot hold three different digits, so $C_1=C_2=0$. Three digits must be exactly $0$, $1$ and $\mathrm A$ in one of $3!=6$ orders; the two orders $01\mathrm A$ and $0\mathrm A1$ begin with $0$, which is not allowed, and the four numbers of the statement remain, $C_3=4$.

Four digits consist of $0$, $1$, $\mathrm A$ and one more digit $x$. If $x$ is one of the $13$ other digits, the four digits are different; of their $4!=24$ orders, the $3!=6$ that begin with $0$ are excluded, which gives $13\cdot18=234$ numbers. If $x$ repeats a required digit, the digits $0,0,1,\mathrm A$ have $4!/2!=12$ orders, of which $6$ begin with $0$, and each of $0,1,1,\mathrm A$ and $0,1,\mathrm A,\mathrm A$ has $12$ orders, of which $3$ begin with $0$. That adds $6+9+9=24$, so $C_4=234+24=258$. With more digits such case distinctions multiply quickly, so we need a systematic method.

3. Counting what is missing

"Contains $0$" is a condition on the string as a whole, but "does not contain $0$" is a condition on every position separately, and the rule of product counts such conditions at once. So we count the complement. For a digit $d\in\{0,1,\mathrm A\}$ let $M_d\subseteq U_n$ be the set of strings in which $d$ does not appear. A string of $U_n$ is valid exactly when it lies in none of the three sets, so

$$C_n=|U_n|-|M_0\cup M_1\cup M_{\mathrm A}|.$$

4. Inclusion–exclusion for three sets

For finite sets $X$, $Y$ and $Z$, the inclusion–exclusion principle states ^[4]

$$\begin{aligned}|X\cup Y\cup Z|&=|X|+|Y|+|Z|-|X\cap Y|\\&\quad-|X\cap Z|-|Y\cap Z|+|X\cap Y\cap Z|.\end{aligned}$$

To see why, take an element that lies in exactly $j\ge1$ of the three sets. The right side counts it once for each of these $j$ sets, subtracts it once for each of the $\binom j2$ pairs among them and adds it back for each of the $\binom j3$ triples, so it is counted $j-\binom j2+\binom j3$ times: $1$ time for $j=1$, $2-1=1$ time for $j=2$ and $3-3+1=1$ time for $j=3$. An element of none of the sets is not counted at all. Both sides therefore agree.

5. Strings that avoid given digits

Claim. Let $F\subseteq\{0,1,\mathrm A\}$ be a set of $f$ forbidden digits and $N(F)$ the number of strings in $U_n$ that use no digit of $F$. Then $N(F)=(16-f)^n$ if $0\in F$, and $N(F)=(15-f)\,(16-f)^{n-1}$ if $0\notin F$.

Proof. Every position may use the $16-f$ digits outside $F$. If $0\in F$, none of them is $0$, so the rule that the first digit is not $0$ holds automatically, and all $n$ positions have $16-f$ choices. If $0\notin F$, the first position must also avoid $0$ and has $15-f$ choices, while the other $n-1$ positions have $16-f$. The rule of product gives both formulas. $\square$

For $F=\varnothing$ the claim gives $|U_n|$ again, and the seven sets of inclusion–exclusion have the sizes

$$\begin{aligned}|M_0|&=15^n,\\|M_1|=|M_{\mathrm A}|&=14\cdot15^{n-1},\\|M_0\cap M_1|=|M_0\cap M_{\mathrm A}|&=14^n,\\|M_1\cap M_{\mathrm A}|&=13\cdot14^{n-1},\\|M_0\cap M_1\cap M_{\mathrm A}|&=13^n.\end{aligned}$$

This is the one trap of the problem: $0$ behaves differently from $1$ and $\mathrm A$. Forbidding $0$ costs the first position nothing, because $0$ was never allowed there, while forbidding $1$ or $\mathrm A$ removes one choice from every position. A formula that always gave the first position $15-f$ choices would remove one choice too many whenever $0\in F$; it gives $C_3=6$ instead of $4$.

6. The count for one length

Putting these sizes into Sections 3 and 4 gives

$$\begin{aligned}C_n&=15\cdot16^{n-1}-\bigl(15^n+2\cdot14\cdot15^{n-1}\bigr)\\&\quad+\bigl(2\cdot14^n+13\cdot14^{n-1}\bigr)-13^n.\end{aligned}$$

Since $15^n=15\cdot15^{n-1}$ and $14^n=14\cdot14^{n-1}$, the two brackets collect to $43\cdot15^{n-1}$ and $41\cdot14^{n-1}$:

$$\begin{aligned}C_n&=15\cdot16^{n-1}-43\cdot15^{n-1}\\&\quad+41\cdot14^{n-1}-13^n.\end{aligned}$$

7. Worked example: three and four digits

For $n=3$ the universe has $|U_3|=15\cdot256=3840$ strings. The three single sets have $3375+3150+3150=9675$ strings, the three pairwise intersections $2744+2744+2548=8036$, and the triple intersection $13^3=2197$. Hence $C_3=3840-9675+8036-2197=4$, the four numbers of Section 2. For $n=4$ the same steps give $61440-145125+112504-28561$${}=258$, again the count found by hand. The partial result $3840-9675$ is negative: midway through inclusion–exclusion the running value need not be the size of any set, which matters for the C++ program.

8. A second derivation by the first digit

The coefficients $43$ and $41$ have a direct meaning. Write $m=n-1$ and sort the strings of $U_n$ by their first digit. If it is $1$ or $\mathrm A$, the other $m$ digits, now free to be any of the $16$ digits, must contain the two required digits not yet seen, which inclusion–exclusion with two sets counts as $16^m-2\cdot15^m+14^m$. If the first digit is one of the other $13$ nonzero digits, the remaining $m$ digits must contain all three required digits, in $16^m-3\cdot15^m+3\cdot14^m-13^m$ ways. Therefore

$$\begin{aligned}C_n&=2\bigl(16^m-2\cdot15^m+14^m\bigr)\\&\quad+13\bigl(16^m-3\cdot15^m+3\cdot14^m-13^m\bigr).\end{aligned}$$

Here $2\cdot2+13\cdot3=43$ copies of $15^m$ are subtracted and $2\cdot1+13\cdot3=41$ copies of $14^m$ are added, which is the formula of Section 6. For $n=4$, with $m=3$, the brackets are $90$ and $6=3!$, and $2\cdot90+13\cdot6=258$.

9. Adding up the lengths

Summed over $n$, each of the four terms of $C_n$ gives a geometric series, and for $r\ne1$ ^[5]

$$\sum_{n=1}^{L}r^{\,n-1}=\frac{r^L-1}{r-1}.$$

Applying this with $r=16,15,14,13$ gives a closed form for the count with at most $L$ digits:

$$\begin{aligned}S(L)&=\bigl(16^L-1\bigr)-\frac{43\,(15^L-1)}{14}\\&\quad+\frac{41\,(14^L-1)}{13}-\frac{13\,(13^L-1)}{12}.\end{aligned}$$

Each division is exact, because $r^L-1$ is divisible by $r-1$. The first term $16^L-1$ is the sum of all $|U_n|$, the number of positive integers with at most $L$ digits. For $L=4$ the four terms are $65535$, $155488$, $121155$ and $30940$, and $65535-155488+121155-30940$${}=262$, which is $4+258$. The first values are $S(3)=4$, $S(4)=262$, $S(5)=10190$ and $S(6)=309680$.

10. A shortcut that overcounts

It is tempting to count instead all strings of exactly $L$ digits with leading zeros allowed, that is, all numbers below $16^L$ padded on the left with zeros. Every position then has $16$ choices, and inclusion–exclusion gives

$$P(L)=16^L-3\cdot15^L+3\cdot14^L-13^L.$$

But padding writes zeros that the number does not contain: for $L=3$ the number $1\mathrm A$ becomes $01\mathrm A$ and seems to contain $0$. Indeed $P(3)=6$ while $S(3)=4$, and $P(4)=348$ while $S(4)=262$. A padded number with fewer than $L$ digits always shows a $0$, and it shows $1$ and $\mathrm A$ exactly when the number contains them. So the excess counts the numbers with fewer than $L$ digits that contain $1$ and $\mathrm A$ but no $0$; these use only the $15$ nonzero digits, and by inclusion–exclusion

$$P(L)-S(L)=\sum_{k=1}^{L-1}\bigl(15^k-2\cdot14^k+13^k\bigr),$$

which is $0+2+84=86$ for $L=4$.

11. Writing the count in base 16

Division by $16$ with remainder splits off the last hexadecimal digit, so repeated division produces the digits from right to left. ^[2] From $262=16\cdot16+6$, $16=1\cdot16+0$ and $1=0\cdot16+1$ we read that $262$ is written $106$; likewise $10190$ is written $27\mathrm{CE}$. As one hexadecimal digit corresponds to four bits, the remainder $v\bmod16$ is the lowest four bits of $v$ and the quotient is $v$ shifted right by four bits, the operations the programs use.

How the Code Works

All three programs evaluate the formula of Sections 5 and 6 for $n=1,\dots,16$, add the values and print the sum in hexadecimal. In the C++ program, ^[10] parse_arguments accepts --skip-checkpoints and --max-digits=K (default $16$, read by parse_int_after_prefix); an unknown argument or $K\lt1$ gives exit code $1$. Unless skipped, run_checkpoints requires count_for_length(3) to equal $4$, the four numbers of the statement, or the program stops with exit code $2$. Then solve_value adds count_for_length(len) for len from $1$ to $K$, and to_hex produces the output string.

count_for_length is Section 5 line by line: total is $|U_n|$, miss0, miss1 and missA are the single sets, miss01, miss0A and miss1A the pairwise intersections and miss01A the triple one, with the powers from pow_u128, a loop of plain multiplications. All values have the type unsigned __int128, a 128-bit extension of GCC and Clang. ^[6] The returned expression total - (miss0 + miss1 + missA) + (miss01 + miss0A + miss1A) - miss01A is evaluated from left to right, and its first difference is negative for every length up to $17$, as in Section 7. Unsigned arithmetic is performed modulo $2^N$ for a type of $N$ bits, ^[7] here $N=128$, so the difference wraps around and comes back when the pairwise sizes are added; since the true $C_n$ lies between $0$ and $2^{128}$, the result is exact. to_hex takes the last digit as value & 0xF, writes $10$ to $15$ as A to F, shifts value right by four bits and reverses the string at the end, as in Section 11.

Other digit limits work too: all terms and sums stay below $2^{128}=16^{32}$ for $K\le32$, so the output is exact up to $32$ digits. Beyond that the count no longer fits, and the program silently prints it reduced modulo $2^{128}$, as runs with $K=33$, $34$ and $40$ show. Huge values of $K$ are not guarded: the digits of $K$ are accumulated in an int without an overflow check, the loop counter of solve_value would overflow at the largest int, and signed overflow is undefined behaviour. ^[7] None of this affects the default run.

The Python program has no options and no checkpoint. Its function solve computes the same eight terms, named t, m0, m1, mA, m01, m0A, m1A and m01A, with ** for the powers. Python integers have unlimited precision, ^[8] so there the partial sums really are negative and nothing wraps around. The output is built by prepending "0123456789ABCDEF"[d] with d = v & 0xF and shifting v >>= 4 until v is $0$. Java uses BigInteger, immutable integers of arbitrary precision, with pow for the powers and mA = m1 for the equal single term; toString(16) writes lower-case letters, so the result passes through toUpperCase(). ^[8]

Complexity and Verification

For each length, C++ and Python compute eight powers and Java seven, since mA = m1 reuses one. pow_u128 multiplies $e$ times for the exponent $e$, so its loops make $8n-4$ multiplications for the length $n$, and the four multiplications by the coefficients $15$, $14$, $14$ and $13$ bring this to $8n$: $1088$ for the sixteen lengths and $24$ more for the checkpoint, as an instrumented copy of the program confirms. For $L\le32$ digits the C++ method thus needs $O(L^2)$ multiplications of 128-bit numbers and $O(1)$ memory; the closed form of Section 9 would need only four powers. Python and Java work with integers of at most $65$ bits here. Measured on a desktop computer, a whole run takes well under a tenth of a second in each language, almost all of it process start-up.

The C++ checkpoint tests $C_3=4$. For this article we checked more:

A C program tested every positive integer below $16^8=2^{32}$ and found the counts $0$, $0$, $4$, $258$, $9928$, $299490$, $7823824$ and $185801658$ for the lengths $1$ to $8$, the values of Section 6.
For every $n\le40$ the formula of Section 6 agrees with the first-digit formula of Section 8 and with a dynamic programme ^[9] that chooses the first digit from the $15$ nonzero digits and every later digit from all $16$, and keeps, for each of the $2^3=8$ subsets of $\{0,1,\mathrm A\}$, the number of strings whose required digits seen so far form that subset; for every $L\le40$ the closed form of Section 9 and the identity of Section 10 hold as well.
The three published programs print the same hexadecimal string, which agrees with an independent evaluation of the formula.
With --max-digits=4, 5 and 6 the C++ program prints $106$, $27\mathrm{CE}$ and $4\mathrm B9\mathrm B0$, the hexadecimal forms of $262$, $10190$ and $309680$, and its output agrees with the exact count for every $K\le32$.

These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The set sizes of Section 5, the closed form of Section 9 and the overcount of Section 10 are derived in this article.

Project Euler 162 — Hexadecimal Numbers. The official statement gives AF = 10 × 16 + 15 = 175 and the examples 10A, 1A0, A10 and A01, and asks how many hexadecimal numbers with at most sixteen digits, written without leading zeros, contain all of the digits 0, 1 and A, the answer to be given in upper-case hexadecimal.
Wikipedia — Hexadecimal. The digits 0 to 9 and A to F stand for the values 0 to 15, one hexadecimal digit represents four bits, and repeated division by 16 yields the digits of an integer, the remainders giving them from the last one onwards.
Wikipedia — Rule of product. If one action can be performed in a ways and another in b ways, there are a · b ways of performing both.
Wikipedia — Inclusion–exclusion principle. The article gives the three-set formula of Section 4, proves the general principle with the binomial theorem by showing that every element of the union is counted exactly once, and states the complementary form, which counts the elements in none of the sets.
Wikipedia — Geometric series. For r ≠ 1 the sum a + ar + ⋯ + arⁿ equals a(1 − rⁿ⁺¹)/(1 − r); Section 9 uses it with a = 1.
GCC manual — 128-bit Integers. As an extension, the types __int128 and unsigned __int128 are supported for targets that have an integer mode wide enough to hold 128 bits.
cppreference — Arithmetic operators. Unsigned integer arithmetic is always performed modulo 2ⁿ, where n is the number of bits of the type, while signed integer overflow is undefined behaviour.
Python — numeric types documents that integers have unlimited precision. Java — BigInteger describes immutable arbitrary-precision integers and toString(radix), which uses the digit characters of Character.forDigit, lower-case letters for the values from 10 on.
Wikipedia — Dynamic programming. The method breaks a problem down into simpler sub-problems and solves each sub-problem only once, storing its result.
C++ — Euler162.cpp. The linked immutable C++ revision contains count_for_length, solve_value, to_hex and run_checkpoints. It is the implementation record for this article.

Problem 162 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using u128 = unsigned __int128;

struct Options {
    int max_digits = 16;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--max-digits=", options.max_digits)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.max_digits >= 1;
}

u128 pow_u128(const u128 base, int exp) {
    u128 result = 1;
    for (int i = 0; i < exp; ++i) {
        result *= base;
    }
    return result;
}

u128 count_for_length(const int len) {
    const u128 total = 15U * pow_u128(16U, len - 1);

    const u128 miss0 = pow_u128(15U, len);
    const u128 miss1 = 14U * pow_u128(15U, len - 1);
    const u128 missA = 14U * pow_u128(15U, len - 1);

    const u128 miss01 = pow_u128(14U, len);
    const u128 miss0A = pow_u128(14U, len);
    const u128 miss1A = 13U * pow_u128(14U, len - 1);

    const u128 miss01A = pow_u128(13U, len);

    return total - (miss0 + miss1 + missA) + (miss01 + miss0A + miss1A) - miss01A;
}

u128 solve_value(const int max_digits) {
    u128 total = 0;
    for (int len = 1; len <= max_digits; ++len) {
        total += count_for_length(len);
    }
    return total;
}

std::string to_hex(u128 value) {
    if (value == 0) {
        return "0";
    }

    std::string out;
    while (value > 0) {
        const int digit = static_cast<int>(value & 0xFULL);
        if (digit < 10) {
            out.push_back(static_cast<char>('0' + digit));
        } else {
            out.push_back(static_cast<char>('A' + (digit - 10)));
        }
        value >>= 4;
    }
    std::reverse(out.begin(), out.end());
    return out;
}

bool run_checkpoints() {
    if (count_for_length(3) != 4U) {
        std::cerr << "Checkpoint failed for 3-digit hexadecimal numbers" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << to_hex(solve_value(options.max_digits)) << '\n';
    return 0;
}

Python

# Problem 162: Hexadecimal numbers containing 0, 1, and A

def solve():
    max_digits = 16
    total = 0
    for n in range(1, max_digits + 1):
        # Inclusion-exclusion: count n-digit hex numbers (no leading zero) containing 0, 1, A
        t = 15 * 16**(n-1)  # total n-digit hex
        m0 = 15**n           # missing 0
        m1 = 14 * 15**(n-1)  # missing 1
        mA = 14 * 15**(n-1)  # missing A
        m01 = 14**n
        m0A = 14**n
        m1A = 13 * 14**(n-1)
        m01A = 13**n
        total += t - (m0 + m1 + mA) + (m01 + m0A + m1A) - m01A
    # Output in hex
    result = ""
    v = total
    if v == 0:
        result = "0"
    else:
        while v > 0:
            d = v & 0xF
            result = "0123456789ABCDEF"[d] + result
            v >>= 4
    print(result)

solve()

Java

import java.math.BigInteger;

public class Euler162 {
    public static void main(String[] args) {
        BigInteger total = BigInteger.ZERO;
        for (int n = 1; n <= 16; n++) {
            BigInteger b16 = BigInteger.valueOf(16);
            BigInteger b15 = BigInteger.valueOf(15);
            BigInteger b14 = BigInteger.valueOf(14);
            BigInteger b13 = BigInteger.valueOf(13);
            BigInteger t = BigInteger.valueOf(15).multiply(b16.pow(n - 1));
            BigInteger m0 = b15.pow(n);
            BigInteger m1 = BigInteger.valueOf(14).multiply(b15.pow(n - 1));
            BigInteger mA = m1;
            BigInteger m01 = b14.pow(n);
            BigInteger m0A = b14.pow(n);
            BigInteger m1A = BigInteger.valueOf(13).multiply(b14.pow(n - 1));
            BigInteger m01A = b13.pow(n);
            total = total.add(t.subtract(m0).subtract(m1).subtract(mA).add(m01).add(m0A).add(m1A).subtract(m01A));
        }
        System.out.println(total.toString(16).toUpperCase());
    }
}