Detailed mathematical approach

Problem Summary

A positive integer is called 11-free if its decimal representation does not contain the decimal expansion of any power \(11^k\) with \(k \ge 1\) as a contiguous substring. The forbidden patterns therefore begin with

$11,\quad 121,\quad 1331,\quad 14641,\quad 161051,\quad \dots$

The single digit \(1\) is allowed, because the definition excludes \(11^0\). If \(E(n)\) denotes the \(n\)-th 11-free positive integer in increasing order, the checkpoints \(E(3)=3\), \(E(200)=213\), and \(E(500000)=531563\) confirm the interpretation. The goal is to compute \(E(10^{18})\), so scanning integers one by one is not realistic.

Mathematical Approach

Step 1: Keep only the forbidden powers that can actually appear

If the final answer has at most \(D\) digits, then only powers of 11 whose decimal length is at most \(D\) can appear as substrings. Write

$\mathcal{P}_D=\{\operatorname{dec}(11^k): k \ge 1,\ |\operatorname{dec}(11^k)| \le D\}.$

The implementation generates these strings directly in decimal form by repeated multiplication by 11, performed on digit strings rather than with a big-integer library. The C++, Python, and Java implementations all use the safe bound \(D=64\), which is much larger than the actual answer length and therefore guarantees that no relevant forbidden pattern is missed.

Step 2: Encode all forbidden substrings with one automaton

When we build a number digit by digit, we do not need to remember the whole prefix. We only need the longest suffix of the current prefix that is also a prefix of some forbidden pattern. That information is exactly what an Aho-Corasick automaton stores.

Let \(s_0\) be the root state, and let \(T(s,d)\) be the state reached after appending digit \(d \in \{0,\dots,9\}\). A state is called terminal if some member of \(\mathcal{P}_D\) has already been matched as a substring. Once a terminal state is reached, the number is invalid forever, so every continuation from that state must be discarded.

Step 3: Count valid suffixes by dynamic programming

For every safe automaton state \(s\) and every remaining length \(r\), define \(A(r,s)\) as the number of length-\(r\) digit strings that can be appended without ever entering a terminal state. The empty suffix gives the base case

$A(0,s)=1.$

For \(r \ge 1\), every next digit either leads to another safe state or to a forbidden one, so the recurrence is

$A(r,s)=\sum_{d=0}^{9} A(r-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ is safe}}.$

This is a standard digit-DP over automaton states. Leading zeros are handled outside the recurrence, so zeros are allowed inside the suffix. The implementations also cap every count at \(n+1\): once a count is already larger than the target rank, exact values above that threshold are irrelevant for later comparisons.

Step 4: Count valid numbers of each length

Let \(C_L\) be the number of valid \(L\)-digit positive integers. Since the first digit cannot be zero,

$C_L=\sum_{d=1}^{9} A(L-1,T(s_0,d)) \cdot \mathbf{1}_{T(s_0,d)\text{ is safe}}.$

Now process lengths \(L=1,2,3,\dots\) in order. If the current rank \(n\) is larger than \(C_L\), then all valid \(L\)-digit numbers lie before the desired answer, so we subtract \(C_L\) and continue. The first length for which the remaining rank does not exceed \(C_L\) is the length of \(E(n)\).

Step 5: Reconstruct the answer lexicographically

After the length \(L\) is known, the number is built from left to right. Suppose we are at position \(i\), currently in state \(s\), with remaining rank \(r\). For a candidate digit \(d\), the number of valid completions is

$B_d=A(L-i-1,T(s,d)) \cdot \mathbf{1}_{T(s,d)\text{ is safe}}.$

If \(r > B_d\), then every valid number starting with that candidate comes before the target, so we replace \(r\) by \(r-B_d\) and try the next digit. Otherwise we fix that digit and move to the next position. For the first position the candidates are \(1,\dots,9\); afterwards they are \(0,\dots,9\).

This works because all shorter lengths were removed first, and among numbers with the same number of digits, lexicographic order is the same as numerical order.

Why the checkpoints fit

The checkpoint \(E(200)=213\) is a good sanity check for the substring rule. The number \(211\) is excluded because it contains the forbidden substring \(11\), while \(212\) and \(213\) remain admissible. The same automaton-and-DP framework explains all three published checkpoints without any special cases.

How the Code Works

The C++, Python, and Java implementations follow the same plan. They first generate all relevant decimal powers of 11 up to the fixed digit bound. They then build the Aho-Corasick automaton, including failure transitions and terminal propagation, so that every digit extension can be checked in constant time. Next they precompute the table \(A(r,s)\) for every remaining length and every safe state. Finally, they use that table twice: once to determine how many digits the target number has, and once more to reconstruct the exact digits of the answer in increasing order.

A practical implementation detail matters here: the counts are stored with saturation at \(n+1\). This preserves every branch decision of the unranking algorithm while preventing overflow in the fixed-width languages.

Complexity Analysis

Let \(D\) be the chosen digit bound, let \(P=|\mathcal{P}_D|\) be the number of generated forbidden powers, and let \(S\) be the number of automaton states. Generating the patterns costs \(O(PD)\) digit operations. Building the automaton costs \(O(S)\) up to the constant alphabet factor 10.

The dominant phase is the dynamic programming table:

$O(D \cdot S \cdot 10)$

time and

$O(D \cdot S)$

memory. The final reconstruction adds only \(O(D \cdot 10)\) time. This is negligible compared with any brute-force search for the \(10^{18}\)-th valid integer.

References

1. Problem page: https://projecteuler.net/problem=442
2. Aho-Corasick algorithm: Wikipedia — Aho-Corasick algorithm
3. Trie data structure: Wikipedia — Trie
4. Finite-state machine: Wikipedia — Finite-state machine
5. Dynamic programming: Wikipedia — Dynamic programming