Solution

Answer: 126461847755

We seek the number of pandigital step numbers below $10^{40}$.

A step number is a number in which adjacent digits differ by exactly $1$.

Examples:

$45656$ is a step number because

$$|4-5|=|5-6|=|6-5|=|5-6|=1.$$

Leading zeros are not allowed in the number itself.

A number is pandigital if every digit $0,1,\dots,9$ appears at least once.

We must count all pandigital step numbers with at most $40$ digits.

Mathematical Analysis

The defining property of a step number is entirely local:

from digit $d$, the next digit can only be $d-1$ or $d+1$.

This naturally suggests dynamic programming.

The additional pandigital condition means we must track which digits have appeared so far.

1. State Representation

Suppose we are building a step number digit-by-digit.

At any point we need to know:

the current last digit,
which digits have already appeared.

We encode the set of used digits with a 10-bit mask:

$$\text{mask} \in [0,2^{10}-1].$$

Bit $k$ is $1$ iff digit $k$ has appeared.

For example:

mask $= 0000000011_2$ means digits $0,1$ appeared,
mask $=1111111111_2 = 1023$ means all digits appeared.

Define

$$dp[\ell][d][m]$$

as the number of step numbers:

of length $\ell$,
ending in digit $d$,
having used digit-set $m$.

2. Initial Conditions

A valid number cannot begin with zero.

So for length $1$:

$$dp[1][d][1\ll d]=1 \quad\text{for } d=1,\dots,9.$$

3. Transition

If the current last digit is $d$, then next digit can be:

$d-1$ if $d>0$,
$d+1$ if $d<9$.

Suppose we extend to digit $nd$. Then:

$$\text{newmask}=m\cup{nd} = m ,|, (1\ll nd).$$

Hence:

$$dp[\ell+1][nd][newmask] ;+=; dp[\ell][d][m].$$

4. Counting Pandigital Numbers

A number is pandigital iff all digits appeared:

$$m = 2^{10}-1 = 1023.$$

Thus for each length $\ell$,

$$\text{count}(\ell) = \sum_{d=0}^{9} dp[\ell][d][1023].$$

We need all lengths $1$ through $40$.

Complexity

There are:

$40$ lengths,
$10$ possible ending digits,
$2^{10}=1024$ masks.

So total states:

$$40 \times 10 \times 1024 \approx 4\times 10^5,$$

which is tiny.

Python Implementation

from collections import defaultdict

FULL = (1 << 10) - 1   # 1023, all digits used

# dp[digit][mask] = count
dp = defaultdict(int)

# Initialize 1-digit numbers (no leading zero)
for d in range(1, 10):
    dp[(d, 1 << d)] = 1

answer = 0

# Build lengths from 1 up to 40
for length in range(1, 41):

    # Count pandigital numbers of this length
    for (digit, mask), cnt in dp.items():
        if mask == FULL:
            answer += cnt

    # Build next layer
    new_dp = defaultdict(int)

    for (digit, mask), cnt in dp.items():

        # Move to digit-1
        if digit > 0:
            nd = digit - 1
            new_mask = mask | (1 << nd)
            new_dp[(nd, new_mask)] += cnt

        # Move to digit+1
        if digit < 9:
            nd = digit + 1
            new_mask = mask | (1 << nd)
            new_dp[(nd, new_mask)] += cnt

    dp = new_dp

print(answer)

Code Walkthrough

Initialization

FULL = (1 << 10) - 1

Creates the mask

$$1111111111_2 = 1023,$$

meaning all digits $0$–$9$ have appeared.

dp[(d, 1 << d)] = 1

A 1-digit number consisting only of digit $d$:

ends in $d$,
has used only digit $d$.

We start only with $1$–$9$ because leading zero is forbidden.

Main Loop

for length in range(1, 41):

Processes all numbers of length length.

Counting Pandigital States

if mask == FULL:
    answer += cnt

Any state whose mask contains all digits contributes to the final answer.

Transition

if digit > 0:

We may append digit-1.

if digit < 9:

We may append digit+1.

These are exactly the step-number rules.

Small Example Check

Consider step numbers of length $2$.

Starting from:

$1\to 0,2$,
$2\to 1,3$,
etc.

This generates:

$$10,12,21,23,32,34,\dots,98.$$

Exactly the correct set of 2-digit step numbers.

Pandigitality obviously cannot occur until length $10$, which our DP naturally enforces because the mask cannot become full earlier.

Final Verification

The result should:

be positive,
be much smaller than all step numbers below $10^{40}$,
first appear only from length $10$ onward.

This DP is exhaustive and exact:

every valid step-number path is counted once,
no invalid transitions exist,
digit usage is tracked perfectly by the bitmask.

Running the program yields:

$$126461847755$$

Answer: 126461847755

Project Euler Problem 178