Problem 442: Eleven-free Integers

Project Euler Problem 442 Solution

EulerSolve provides an optimized solution for Project Euler Problem 442, Eleven-free Integers, with C++, Python, Java, and a step-by-step mathematical explanation.

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

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

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

Problem 442 source code

C++

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

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

struct Options {
    u64 n = 1000000000000000000ULL;
    bool run_checkpoints = true;
};

struct Node {
    std::array<int, 10> next{};
    int fail = 0;
    bool out = false;
    Node() {
        next.fill(-1);
    }
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        value = static_cast<u64>(std::stoull(tail));
    } catch (...) {
        return false;
    }
    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_u64_after_prefix(arg, "--n=", options.n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.n >= 1ULL;
}

std::string mul_by_11(const std::string& s) {
    std::string out;
    out.resize(s.size());
    int carry = 0;
    for (int i = static_cast<int>(s.size()) - 1; i >= 0; --i) {
        const int v = 11 * (s[static_cast<std::size_t>(i)] - '0') + carry;
        out[static_cast<std::size_t>(i)] = static_cast<char>('0' + (v % 10));
        carry = v / 10;
    }
    while (carry > 0) {
        out.insert(out.begin(), static_cast<char>('0' + (carry % 10)));
        carry /= 10;
    }
    std::size_t pos = 0;
    while (pos + 1 < out.size() && out[pos] == '0') {
        ++pos;
    }
    if (pos > 0) {
        out.erase(0, pos);
    }
    return out;
}

std::vector<std::string> generate_forbidden(int max_len) {
    std::vector<std::string> patterns;
    std::string cur = "11";  // powers 11^k, k>=1
    while (static_cast<int>(cur.size()) <= max_len) {
        patterns.push_back(cur);
        cur = mul_by_11(cur);
    }
    return patterns;
}

std::vector<Node> build_aho(const std::vector<std::string>& patterns) {
    std::vector<Node> nodes(1);

    for (const std::string& p : patterns) {
        int state = 0;
        for (const char ch : p) {
            const int d = ch - '0';
            int nx = nodes[static_cast<std::size_t>(state)].next[static_cast<std::size_t>(d)];
            if (nx == -1) {
                nx = static_cast<int>(nodes.size());
                nodes[static_cast<std::size_t>(state)].next[static_cast<std::size_t>(d)] = nx;
                nodes.push_back(Node{});
            }
            state = nx;
        }
        nodes[static_cast<std::size_t>(state)].out = true;
    }

    std::queue<int> q;
    for (int d = 0; d <= 9; ++d) {
        int& nx = nodes[0].next[static_cast<std::size_t>(d)];
        if (nx == -1) {
            nx = 0;
        } else {
            nodes[static_cast<std::size_t>(nx)].fail = 0;
            q.push(nx);
        }
    }

    while (!q.empty()) {
        const int v = q.front();
        q.pop();

        const int f = nodes[static_cast<std::size_t>(v)].fail;
        if (nodes[static_cast<std::size_t>(f)].out) {
            nodes[static_cast<std::size_t>(v)].out = true;
        }

        for (int d = 0; d <= 9; ++d) {
            int& nx = nodes[static_cast<std::size_t>(v)].next[static_cast<std::size_t>(d)];
            if (nx == -1) {
                nx = nodes[static_cast<std::size_t>(f)].next[static_cast<std::size_t>(d)];
            } else {
                nodes[static_cast<std::size_t>(nx)].fail =
                    nodes[static_cast<std::size_t>(f)].next[static_cast<std::size_t>(d)];
                q.push(nx);
            }
        }
    }

    return nodes;
}

u128 cap_add(u128 a, u128 b, u128 cap) {
    const u128 s = a + b;
    if (s >= cap || s < a) {
        return cap;
    }
    return s;
}

std::string nth_eleven_free(u64 n_target) {
    const int max_digits = 64;
    const std::vector<std::string> patterns = generate_forbidden(max_digits);
    const std::vector<Node> automaton = build_aho(patterns);
    const int states = static_cast<int>(automaton.size());

    const u128 cap = static_cast<u128>(n_target) + 1ULL;

    std::vector<std::vector<u128>> ways(
        static_cast<std::size_t>(max_digits + 1),
        std::vector<u128>(static_cast<std::size_t>(states), 0));

    for (int s = 0; s < states; ++s) {
        ways[0][static_cast<std::size_t>(s)] = 1;
    }

    for (int rem = 1; rem <= max_digits; ++rem) {
        for (int s = 0; s < states; ++s) {
            if (automaton[static_cast<std::size_t>(s)].out) {
                ways[static_cast<std::size_t>(rem)][static_cast<std::size_t>(s)] = 0;
                continue;
            }
            u128 sum = 0;
            for (int d = 0; d <= 9; ++d) {
                const int ns = automaton[static_cast<std::size_t>(s)].next[static_cast<std::size_t>(d)];
                if (automaton[static_cast<std::size_t>(ns)].out) {
                    continue;
                }
                sum = cap_add(sum, ways[static_cast<std::size_t>(rem - 1)][static_cast<std::size_t>(ns)], cap);
            }
            ways[static_cast<std::size_t>(rem)][static_cast<std::size_t>(s)] = sum;
        }
    }

    u128 remaining = static_cast<u128>(n_target);
    int len = 0;
    for (int L = 1; L <= max_digits; ++L) {
        u128 cnt = 0;
        for (int d = 1; d <= 9; ++d) {
            const int ns = automaton[0].next[static_cast<std::size_t>(d)];
            if (automaton[static_cast<std::size_t>(ns)].out) {
                continue;
            }
            cnt = cap_add(cnt, ways[static_cast<std::size_t>(L - 1)][static_cast<std::size_t>(ns)], cap);
        }
        if (remaining > cnt) {
            remaining -= cnt;
        } else {
            len = L;
            break;
        }
    }

    if (len == 0) {
        return {};
    }

    std::string answer;
    answer.reserve(static_cast<std::size_t>(len));
    int state = 0;

    for (int pos = 0; pos < len; ++pos) {
        const int start_digit = (pos == 0) ? 1 : 0;
        for (int d = start_digit; d <= 9; ++d) {
            const int ns = automaton[static_cast<std::size_t>(state)].next[static_cast<std::size_t>(d)];
            if (automaton[static_cast<std::size_t>(ns)].out) {
                continue;
            }
            const u128 cnt =
                ways[static_cast<std::size_t>(len - pos - 1)][static_cast<std::size_t>(ns)];
            if (remaining > cnt) {
                remaining -= cnt;
            } else {
                answer.push_back(static_cast<char>('0' + d));
                state = ns;
                break;
            }
        }
    }

    return answer;
}

bool run_checkpoints() {
    if (nth_eleven_free(3) != "3") {
        std::cerr << "Checkpoint failed: E(3)\n";
        return false;
    }
    if (nth_eleven_free(200) != "213") {
        std::cerr << "Checkpoint failed: E(200)\n";
        return false;
    }
    if (nth_eleven_free(500000) != "531563") {
        std::cerr << "Checkpoint failed: E(500000)\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 << nth_eleven_free(options.n) << '\n';
    return 0;
}

Python

# Native Python 442
def solve():
    n_target = 1000000000000000000

    def mul_by_11(s):
        out = []
        carry = 0
        for ch in reversed(s):
            v = 11 * int(ch) + carry
            out.append(str(v % 10))
            carry = v // 10
        while carry > 0:
            out.append(str(carry % 10))
            carry //= 10
        out.reverse()
        # lstrip '0' but leave one if all '0'
        res = "".join(out).lstrip('0')
        return res if res else "0"

    max_digits = 64
    patterns = []
    cur = "11"
    while len(cur) <= max_digits:
        patterns.append(cur)
        cur = mul_by_11(cur)

    # Build Aho-Corasick
    class Node:
        def __init__(self):
            self.next = [-1] * 10
            self.fail = 0
            self.out = False

    nodes = [Node()]
    for p in patterns:
        state = 0
        for ch in p:
            d = int(ch)
            nx = nodes[state].next[d]
            if nx == -1:
                nx = len(nodes)
                nodes[state].next[d] = nx
                nodes.append(Node())
            state = nx
        nodes[state].out = True

    from collections import deque
    q = deque()
    for d in range(10):
        nx = nodes[0].next[d]
        if nx == -1:
            nodes[0].next[d] = 0
        else:
            nodes[nx].fail = 0
            q.append(nx)

    while q:
        v = q.popleft()
        f = nodes[v].fail
        if nodes[f].out:
            nodes[v].out = True
        for d in range(10):
            nx = nodes[v].next[d]
            if nx == -1:
                nodes[v].next[d] = nodes[f].next[d]
            else:
                nodes[nx].fail = nodes[f].next[d]
                q.append(nx)

    states = len(nodes)
    cap = n_target + 1

    ways = [[0] * states for _ in range(max_digits + 1)]
    for s in range(states):
        ways[0][s] = 1

    for rem in range(1, max_digits + 1):
        for s in range(states):
            if nodes[s].out:
                continue
            summ = 0
            for d in range(10):
                ns = nodes[s].next[d]
                if not nodes[ns].out:
                    summ += ways[rem - 1][ns]
            ways[rem][s] = min(summ, cap)

    remaining = n_target
    length = 0
    for L in range(1, max_digits + 1):
        cnt = 0
        for d in range(1, 10):
            ns = nodes[0].next[d]
            if not nodes[ns].out:
                cnt += ways[L - 1][ns]
        if remaining > cnt:
            remaining -= cnt
        else:
            length = L
            break

    if length == 0:
        return ""

    ans = []
    state = 0
    for pos in range(length):
        start_digit = 1 if pos == 0 else 0
        for d in range(start_digit, 10):
            ns = nodes[state].next[d]
            if nodes[ns].out:
                continue
            cnt = ways[length - pos - 1][ns]
            if remaining > cnt:
                remaining -= cnt
            else:
                ans.append(str(d))
                state = ns
                break

    return "".join(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Euler442 {
    private static final long N_TARGET = 1000000000000000000L;

    private static String mulBy11(String s) {
        StringBuilder out = new StringBuilder();
        int carry = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int v = 11 * (s.charAt(i) - '0') + carry;
            out.append(v % 10);
            carry = v / 10;
        }
        while (carry > 0) {
            out.append(carry % 10);
            carry /= 10;
        }
        out.reverse();
        int pos = 0;
        while (pos < out.length() - 1 && out.charAt(pos) == '0') {
            pos++;
        }
        return out.substring(pos);
    }

    private static class Node {
        int[] next = new int[10];
        int fail = 0;
        boolean out = false;

        Node() {
            for (int i = 0; i < 10; i++)
                next[i] = -1;
        }
    }

    private static long capAdd(long a, long b, long cap) {
        long s = a + b;
        if (s < 0 || s >= cap)
            return cap;
        return s;
    }

    public static String solve() {
        int maxDigits = 64;
        List<String> patterns = new ArrayList<>();
        String cur = "11";
        while (cur.length() <= maxDigits) {
            patterns.add(cur);
            cur = mulBy11(cur);
        }

        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node());

        for (String p : patterns) {
            int state = 0;
            for (int i = 0; i < p.length(); i++) {
                int d = p.charAt(i) - '0';
                int nx = nodes.get(state).next[d];
                if (nx == -1) {
                    nx = nodes.size();
                    nodes.get(state).next[d] = nx;
                    nodes.add(new Node());
                }
                state = nx;
            }
            nodes.get(state).out = true;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int d = 0; d <= 9; d++) {
            int nx = nodes.get(0).next[d];
            if (nx == -1) {
                nodes.get(0).next[d] = 0;
            } else {
                nodes.get(nx).fail = 0;
                q.add(nx);
            }
        }

        while (!q.isEmpty()) {
            int v = q.poll();
            int f = nodes.get(v).fail;
            if (nodes.get(f).out) {
                nodes.get(v).out = true;
            }
            for (int d = 0; d <= 9; d++) {
                int nx = nodes.get(v).next[d];
                if (nx == -1) {
                    nodes.get(v).next[d] = nodes.get(f).next[d];
                } else {
                    nodes.get(nx).fail = nodes.get(f).next[d];
                    q.add(nx);
                }
            }
        }

        int states = nodes.size();
        long cap = N_TARGET + 1;

        long[][] ways = new long[maxDigits + 1][states];
        for (int s = 0; s < states; s++) {
            ways[0][s] = 1;
        }

        for (int rem = 1; rem <= maxDigits; rem++) {
            for (int s = 0; s < states; s++) {
                if (nodes.get(s).out)
                    continue;
                long sum = 0;
                for (int d = 0; d <= 9; d++) {
                    int ns = nodes.get(s).next[d];
                    if (!nodes.get(ns).out) {
                        sum = capAdd(sum, ways[rem - 1][ns], cap);
                    }
                }
                ways[rem][s] = sum;
            }
        }

        long remaining = N_TARGET;
        int len = 0;
        for (int L = 1; L <= maxDigits; L++) {
            long cnt = 0;
            for (int d = 1; d <= 9; d++) {
                int ns = nodes.get(0).next[d];
                if (!nodes.get(ns).out) {
                    cnt = capAdd(cnt, ways[L - 1][ns], cap);
                }
            }
            if (remaining > cnt) {
                remaining -= cnt;
            } else {
                len = L;
                break;
            }
        }

        if (len == 0)
            return "";

        StringBuilder ans = new StringBuilder();
        int state = 0;
        for (int pos = 0; pos < len; pos++) {
            int startDigit = (pos == 0) ? 1 : 0;
            for (int d = startDigit; d <= 9; d++) {
                int ns = nodes.get(state).next[d];
                if (nodes.get(ns).out)
                    continue;
                long cnt = ways[len - pos - 1][ns];
                if (remaining > cnt) {
                    remaining -= cnt;
                } else {
                    ans.append(d);
                    state = ns;
                    break;
                }
            }
        }

        return ans.toString();
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}