Problem 178: Step Numbers

Project Euler Problem 178 Solution

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

Problem Summary Project Euler 178 asks for the number of step numbers below $10^{40}$ that are pandigital, meaning that every digit $0,1,\dots,9$ appears at least once. A step number is a positive decimal integer whose adjacent digits differ by exactly 1, so every valid number traces a walk such as $45654$ or $1234567890$ along the digit line. Because the bound is $10^{40}$, we must count all valid lengths from 1 through 40, not only 40-digit numbers. Leading zero is forbidden, and any number with fewer than 10 digits is automatically too short to be pandigital, but the dynamic program can treat all lengths uniformly. Mathematical Approach The natural model is to view the digits as the vertices of the path graph $$0-1-2-3-4-5-6-7-8-9.$$ A step number of length $\ell$ is exactly a walk of $\ell-1$ edges on this graph, starting from one of the vertices $1,\dots,9$. The step condition itself is easy; the real issue is remembering which digits have already appeared so that we know when the walk has become pandigital. Digit Graph and State Space Let $M\subseteq\{0,1,\dots,9\}$ be the set of digits seen so far, and let $d$ be the last digit....

Detailed mathematical approach

Problem Summary

A step number is a positive integer in which every two consecutive digits differ by exactly $1$, such as $45656$ from the statement, and a number is pandigital if it contains every decimal digit from $0$ to $9$ at least once. We must count the pandigital step numbers below $10^{40}$, that is, those with at most $40$ digits, written as usual without leading zeros. The statement gives no counts to check against. ^[1]

The whole solution in one sentence: we build step numbers one digit at a time, group the beginnings of equal length by their last digit and their set of digits, keep only the size of each group, and add up the sizes of the groups that contain all ten digits, for every length up to $40$.

Mathematical Approach

We count short step numbers by hand, prove that their digits always fill an interval, and derive from this what a count must remember.

1. Step numbers are walks on the line of digits

Draw the ten digits as points in a row, $0,1,\dots,9$, and link every two neighbours; in graph theory this is a path graph. ^[2] A number is a step number exactly when each digit is a neighbour of the one before it, so a step number with $L$ digits is a walk of $L-1$ steps along the line, starting at one of the digits $1,\dots,9$ because a number does not begin with $0$. The walk may turn back: $45656$ walks $4\to5\to6\to5\to6$.

Let $T(L)$ be the number of step numbers with $L$ digits. The nine one-digit numbers have no pair of digits to check, so $T(1)=9$. A first digit from $1$ to $8$ has two possible successors and $9$ only one, so $T(2)=8\cdot2+1=17$; these are $10,12,21,23,\dots,89,98$. Only $10$ and $89$ end at an end point of the line, so $T(3)=2\cdot1+15\cdot2=32$. Then follow $61$, $116$, $222$, $424$, $813$, $1556$ and $2986$ for $L=4,\dots,10$; the OEIS lists step numbers, also called esthetic numbers, as A033075 and their counts as A090994. ^[3] Since a step has at most two choices, $T(L)\le9\cdot2^{L-1}$.

2. The shortest pandigital step number

A pandigital number has at least $10$ digits. With exactly $10$ digits each digit occurs exactly once, so the walk never visits a digit twice and therefore never turns back, since turning back returns to the digit it has just left. A walk that never turns back runs in one direction, and to visit all ten points it must run from one end of the line to the other. Of the two candidates $0123456789$ and $9876543210$, the first begins with $0$, so $9876543210$ is the only pandigital step number with $10$ digits. And $1234567890$ is not a step number at all: its last two digits differ by $9$.

3. The digits of a step number fill an interval

Claim. The digits of a step number form an interval $\{a,a+1,\dots,b\}$ of consecutive digits, and the last digit belongs to it.

Proof. By induction on the number of digits. A one-digit number $d$ has the interval $\{d\}$. Suppose the first $\ell$ digits fill the interval from $a$ to $b$ and the last of them is $d$, with $a\le d\le b$. The next digit, $d-1$ or $d+1$, lies between $a-1$ and $b+1$, so adding it gives the interval from $a$ to $b$, from $a-1$ to $b$, or from $a$ to $b+1$, each containing the new last digit. $\square$

In short, a walk along a line cannot jump over a point; $45656$, for example, has the interval $\{4,5,6\}$. Two consequences follow. First, a step number is pandigital exactly when it contains both $0$ and $9$. Second, a set of digits and a last digit can only occur together if the set is an interval containing the digit. An interval of $k$ digits can be placed in $11-k$ ways, which gives $\sum_{k=1}^{10}k(11-k)=220$ such pairs; without the pair $(\{0\},0)$, since no positive integer consists of zeros alone, at most $219$ of all $2^{10}\cdot10=10240$ pairs occur.

4. What the beginning of a number has to remember

A prefix, the beginning of a step number, is again a step number. How it can be continued depends on its last digit, and whether the finished number is pandigital depends on its set $M$ of digits and on the digits added later; nothing else matters:

Claim. If the step numbers $x$ and $y$ have the same last digit and the same set of digits, then for every string $z$ of further digits, $xz$ is a pandigital step number exactly when $yz$ is one.

Proof. A pair of consecutive digits of $xz$ lies inside $x$, where the digits differ by $1$, or consists of the last digit of $x$ and the first digit of $z$, or lies inside $z$; the pairs of the last two kinds are the same for $yz$, and those inside $y$ differ by $1$ too. The set of digits of $xz$ is $M$ together with the digits of $z$, again the same for $yz$. $\square$

The last digit alone would not do: $1012345678$ and $8$ both end in $8$, but appending $9$ makes only the first pandigital. So let $F(\ell,M,d)$ be the number of step numbers with $\ell$ digits, set of digits $M$ and last digit $d$.

5. Counting one digit at a time

Every step number with $\ell+1$ digits arises in exactly one way from a step number with $\ell$ digits, its prefix, by appending a neighbour $e$ of the prefix's last digit $d$; if the prefix has the set of digits $M$, the longer number has the set $M\cup\{e\}$ and the last digit $e$. Conversely, appending a neighbour of the last digit to any step number gives a step number. So, starting from

$$F(1,\{d\},d)=1\qquad(1\le d\le9)$$

and $0$ for every other set and digit, in particular for the digit $0$, the counts for $\ell+1$ digits are, for every set $M'$ that contains $e$,

$$F(\ell+1,M',e)=\sum F(\ell,M,d),$$

where $d$ runs over the neighbours $e\pm1$ between $0$ and $9$ and $M$ over the two sets $M'$ and $M'\setminus\{e\}$, the only sets that become $M'$ when $e$ is added. For example, $F(4,\{1,2,3\},2)=2$ collects two terms, from $123$ and $321$, which have the same set but different last digits and give $1232$ and $3212$; the terms with the set $\{1,3\}$ are $0$, since by Section 3 no step number has this set. The answer is the total over the full set $D=\{0,1,\dots,9\}$,

$$\sum_{\ell=1}^{40}\ \sum_{d=0}^{9}F(\ell,D,d),$$

where the lengths $\ell\le9$ contribute nothing by Section 2. Each table is computed once from the previous one and no step number is ever listed; this is dynamic programming. ^[4] Listing would be hopeless: there are about $1.9\cdot10^{12}$ step numbers below $10^{40}$. By Section 3, two yes-or-no flags, whether $0$ and whether $9$ has occurred, could replace the set; the published programs keep the full set, which does not rely on Section 3.

6. Worked example: eleven and twelve digits

Two observations make the next lengths countable by hand. Each step changes the digit by $1$ and so changes its parity, whether it is even or odd; a walk of $k$ steps from the first digit $s$ to the last digit $e$ therefore has $k$ and $e-s$ both even or both odd. And a pandigital walk visits $0$ and $9$: if it reaches $0$ first, it needs at least $s$ steps down to $0$, $9$ steps up to $9$ and $9-e$ steps back to $e$, so at least $s+18-e$ steps; if it reaches $9$ first, at least $(9-s)+9+e$. Both minima have the parity of $e-s$, so spare steps come in pairs, and a walk without spare steps is fixed by $s$, $e$ and the end it reaches first.

For $11$ digits, $k=10$. If $0$ comes first, $s+18-e\le10$, that is $e-s\ge8$, and with $s\ge1$ only $s=1$, $e=9$ remains: $10123456789$. If $9$ comes first, $(9-s)+9+e\le10$ gives $s-e\ge8$, and an even $s-e$ leaves $s=8$, $e=0$ and $s=9$, $e=1$: $89876543210$ and $98765432101$. So $3$ step numbers with $11$ digits are pandigital.

For $12$ digits, $k=11$, so $e-s$ is odd. If $0$ comes first, $e-s\ge7$ in the same way, which leaves $s=1$, $e=8$ and $s=2$, $e=9$, without spare steps: $101234567898$ and $210123456789$. If $9$ comes first, $s-e\ge7$ leaves $789876543210$, $898765432101$ and $987654321012$ without spare steps, and $s=9$, $e=0$ with two: the walk runs down from $9$ to some $j$ from $0$ to $8$, steps up once to $j+1$ and runs down to $0$, which gives $9$ numbers, from $989876543210$ for $j=8$ to $987654321010$ for $j=0$. Altogether $2+3+9=14$, and $1+3+14=18$ pandigital step numbers have at most $12$ digits; the C++ program recomputes this total before its main run.

7. A second count by inclusion–exclusion

Section 3 also gives a count without sets. Let $P(L)$ be the number of pandigital step numbers with $L$ digits and, among the $T(L)$ step numbers with $L$ digits, let $A_0(L)$, $A_9(L)$ and $A_{09}(L)$ count those without the digit $0$, those without $9$, and those with neither. A step number is pandigital exactly when it contains $0$ and $9$. Subtracting from $T(L)$ the numbers without $0$ and those without $9$ removes the numbers with neither twice, so these are added back once; this is the inclusion–exclusion principle: ^[5]

$$\begin{aligned}P(L)={}&T(L)-A_0(L)\\&-A_9(L)+A_{09}(L).\end{aligned}$$

Each term counts walks on a line: $A_0(L)$ the walks of $L-1$ steps on the shorter line $1,\dots,9$, $A_9(L)$ those on $0,\dots,8$ starting at one of $1,\dots,8$, and $A_{09}(L)$ those on $1,\dots,8$. A table of ten numbers, the numbers of walks ending at each digit, counts them: it starts with $1$ at each allowed first digit and $0$ elsewhere, each step replaces the count of every digit by the sum of the old counts of its neighbours on that line, and after $L-1$ steps the counts are added up. For $10$, $11$ and $12$ digits this gives

$$\begin{aligned}2986-2600-2475+2090&=1,\\5721-4950-4700+3932&=3,\\10982-9400-8950+7382&=14,\end{aligned}$$

in agreement with Sections 2 and 6.

8. How large the counts become

Each entry of the table for $\ell$ digits is at most $T(\ell)\le9\cdot2^{\ell-1}$, and the answer is at most the number of all step numbers below $10^{40}$:

$$\sum_{L=1}^{40}T(L)\le9\,(2^{40}-1)\lt10^{13}.$$

This is far below $2^{63}\approx9.2\cdot10^{18}$, so signed $64$-bit integers hold every count exactly.

How the Code Works

The C++ program ^[6] starts in main with the Options defaults, $40$ digits and checkpoints on. parse_arguments accepts --skip-checkpoints and --max-digits= followed by decimal digits, which parse_int_after_prefix accumulates in an int without a range check, so a value too large for an int overflows, which is undefined behaviour; ^[7] a later --max-digits overrides an earlier one. Any other argument, or a final value below $1$, gives exit code $1$. Unless switched off, run_checkpoints compares solve(12) with brute_small(12), giving exit code $2$ if they differ; then main prints solve(options.max_digits).

solve builds the table dp of Section 5, a std::vector of max_digits + 1 layers, layer $0$ unused, each holding $1024$ std::array rows of ten long long counts. The entry dp[len][mask][d] is $F(\ell,M,d)$ for $\ell$ equal to len, where bit $i$ of mask, worth $2^i$, is set exactly when the digit $i$ belongs to $M$: the prefix $12$ has the mask $2+4=6$, appending $3$ sets the bit worth $8$ and gives $14$, while appending $1$ leaves $6$, because a bitwise OR sets the bit of the new digit and changes no other bit. ^[8] The nine entries dp[1][1 << first][first] start at $1$. Then, for len from $1$ to max_digits - 1, the program runs through all $1024$ masks and ten digits, skips zero entries, and adds each nonzero count ways to the entries of the digits $d-1$, if $d\gt0$, and $d+1$, if $d\lt9$. This pushes each count forward instead of collecting the sum of Section 5, adding every term of that sum exactly once; as only layer len + 1 is written, the loop order within a layer does not matter. Finally solve adds the entries dp[len][kMaskAll][d] over all lengths and last digits, kMaskAll being $1023$, the mask of the full set $D$.

brute_small counts the same numbers directly. Its recursive std::function dfs(len, last, mask) is called once for every step number with at most max_digits + 1 digits; a call with len beyond max_digits returns at once, and every other call adds $1$ when the mask is full and calls itself for the neighbours of last. For $12$ digits it makes $43\,992$ calls, $21\,053$ of which return at once, and both functions give the total $18$ of Section 6.

The Python program runs the same loops in solve on a nested list dp, and the Java program in main on a long[][][] array; both fix the length at $40$ and have no options or checks. C++'s long long has at least $64$ bits, Java's long exactly $64$, and Python's integers are unbounded, so by Section 8 no version overflows. With a $64$-bit long long, the C++ program is exact for every --max-digits up to $66$; from $67$ on the final sum exceeds $2^{63}-1$, again undefined behaviour, ^[7] and in the build used here --max-digits=67 printed a negative number.

Complexity and Verification

For $n$ digits the table holds $(n+1)\cdot2^{10}\cdot10$ counts, $419\,840$ numbers of $64$ bits or about $3.4$ MB in C++ for $n=40$, and the main loop visits $(n-1)\cdot10240=399\,360$ entries. Only $6947$ of them are nonzero, at most $219$ per layer by Section 3, and these make $13\,301$ additions. Time and memory therefore grow linearly in $n$. On a desktop computer a whole run takes about $3$ milliseconds in C++, checkpoints included, and a few hundredths of a second in Python and Java.

All three programs print the same number. For this article it was compared, without being displayed, with the sum of the inclusion–exclusion formula of Section 7 and with a dynamic programme that keeps only the two flags of Section 5; both agree with the published table for every length up to $40$. An enumeration of all $1\,143\,888$ step numbers with at most $18$ digits reproduces $T(L)$ and $P(L)$ for every $L\le18$, including the lists of Sections 2 and 6, and the C++ output for every --max-digits from $1$ to $66$ equals the exact count. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above; the interval property, the recurrence, the hand counts and the inclusion–exclusion formula are derived in this article.

Project Euler 178 — Step Numbers. The official statement defines step numbers, with the example 45656, and pandigital numbers, and asks how many pandigital step numbers less than 10⁴⁰ there are.
Wikipedia — Path graph. The vertices of a path graph can be listed in an order v₁, v₂, …, vₙ such that the edges are {vᵢ, vᵢ₊₁}; the two end vertices have degree 1 and all others degree 2.
OEIS A033075 — Positive numbers all of whose pairs of consecutive decimal digits differ by 1. The entry notes that they are also called 10-esthetic numbers and lists 9, 17, 32, 61, 116, 222, 424 as the numbers of terms with n digits; OEIS A090994 continues these counts, in agreement with T(L).
Wikipedia — Dynamic programming. Dynamic programming breaks a complicated problem into simpler sub-problems, solves each of them only once and stores the results in a table; it can count solutions without visiting them all.
Wikipedia — Inclusion–exclusion principle. For two finite sets, |A ∪ B| = |A| + |B| − |A ∩ B|; in the complementary form, the elements of a finite set S that lie in neither of two subsets A and B number |S| − |A| − |B| + |A ∩ B|.
C++ — Euler178.cpp. The linked immutable C++ revision contains parse_arguments, solve, brute_small and run_checkpoints. It is the implementation record for this article.
cppreference — Arithmetic operators. Overflow in signed integer arithmetic is undefined behaviour; one possible outcome is a wrap-around, typically in two's complement.
Wikipedia — Mask (computing). An OR with 1 turns a bit on and an OR with 0 leaves it unchanged, so the bits of one integer can hold a set of yes-or-no flags.

Problem 178 source code

C++

#include <array>
#include <cstdint>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    int max_digits = 40;
    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;
}

i64 solve(const int max_digits) {
    static constexpr int kMaskAll = (1 << 10) - 1;
    std::vector<std::vector<std::array<i64, 10>>> dp(
        static_cast<std::size_t>(max_digits + 1),
        std::vector<std::array<i64, 10>>(1 << 10));

    for (int first = 1; first <= 9; ++first) {
        dp[1][1 << first][static_cast<std::size_t>(first)] = 1;
    }

    for (int len = 1; len < max_digits; ++len) {
        for (int mask = 0; mask <= kMaskAll; ++mask) {
            for (int d = 0; d <= 9; ++d) {
                const i64 ways = dp[static_cast<std::size_t>(len)][static_cast<std::size_t>(mask)][
                    static_cast<std::size_t>(d)];
                if (ways == 0) {
                    continue;
                }
                if (d > 0) {
                    const int nmask = mask | (1 << (d - 1));
                    dp[static_cast<std::size_t>(len + 1)][static_cast<std::size_t>(nmask)][
                        static_cast<std::size_t>(d - 1)] += ways;
                }
                if (d < 9) {
                    const int nmask = mask | (1 << (d + 1));
                    dp[static_cast<std::size_t>(len + 1)][static_cast<std::size_t>(nmask)][
                        static_cast<std::size_t>(d + 1)] += ways;
                }
            }
        }
    }

    i64 answer = 0;
    for (int len = 1; len <= max_digits; ++len) {
        for (int d = 0; d <= 9; ++d) {
            answer += dp[static_cast<std::size_t>(len)][kMaskAll][static_cast<std::size_t>(d)];
        }
    }
    return answer;
}

i64 brute_small(const int max_digits) {
    i64 answer = 0;
    std::function<void(int, int, int)> dfs = [&](int len, int last, int mask) {
        if (len > max_digits) {
            return;
        }
        if (mask == ((1 << 10) - 1)) {
            ++answer;
        }
        if (last > 0) {
            dfs(len + 1, last - 1, mask | (1 << (last - 1)));
        }
        if (last < 9) {
            dfs(len + 1, last + 1, mask | (1 << (last + 1)));
        }
    };
    for (int first = 1; first <= 9; ++first) {
        dfs(1, first, 1 << first);
    }
    return answer;
}

bool run_checkpoints() {
    if (solve(12) != brute_small(12)) {
        std::cerr << "Checkpoint failed for max-digits=12" << '\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 << solve(options.max_digits) << '\n';
    return 0;
}

Python

# Problem 178: Step Numbers (numbers where consecutive digits differ by exactly 1
# and all digits 0-9 appear at least once)

def solve():
    max_digits = 40
    ALL = (1 << 10) - 1
    # dp[len][mask][last_digit] = count
    dp = [[[0]*10 for _ in range(1 << 10)] for _ in range(max_digits+1)]
    for d in range(1, 10):
        dp[1][1 << d][d] = 1
    for ln in range(1, max_digits):
        for mask in range(1 << 10):
            for d in range(10):
                w = dp[ln][mask][d]
                if w == 0: continue
                if d > 0:
                    dp[ln+1][mask | (1<<(d-1))][d-1] += w
                if d < 9:
                    dp[ln+1][mask | (1<<(d+1))][d+1] += w
    ans = 0
    for ln in range(1, max_digits+1):
        for d in range(10):
            ans += dp[ln][ALL][d]
    print(ans)

solve()

Java

public class Euler178 {
    public static void main(String[] args) {
        int maxD = 40, ALL = (1 << 10) - 1;
        long[][][] dp = new long[maxD + 1][1 << 10][10];
        for (int d = 1; d <= 9; d++)
            dp[1][1 << d][d] = 1;
        for (int ln = 1; ln < maxD; ln++)
            for (int mask = 0; mask < (1 << 10); mask++)
                for (int d = 0; d <= 9; d++) {
                    long w = dp[ln][mask][d];
                    if (w == 0)
                        continue;
                    if (d > 0)
                        dp[ln + 1][mask | (1 << (d - 1))][d - 1] += w;
                    if (d < 9)
                        dp[ln + 1][mask | (1 << (d + 1))][d + 1] += w;
                }
        long ans = 0;
        for (int ln = 1; ln <= maxD; ln++)
            for (int d = 0; d <= 9; d++)
                ans += dp[ln][ALL][d];
        System.out.println(ans);
    }
}