Problem 305: Reflexive Position

Project Euler Problem 305 Solution

EulerSolve provides an optimized solution for Project Euler Problem 305, Reflexive Position, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Consider the infinite concatenation $$C=12345678910111213\dots$$ For a given $n$, let $P=\text{str}(n)$. Define $f(n)$ as the starting position of the $n$-th occurrence of $P$ inside $C$. The Project Euler sum is taken over $n=3^k$. Mathematical Approach 1) Why this is a string-search problem on one continuous stream The pattern $P$ can appear: 1. entirely inside one integer, 2. across the boundary between consecutive integers, 3. overlapping with itself. So we must search in the continuous digit stream $123456789101112\dots$, not number by number. Resetting the match state at integer boundaries would miss valid occurrences. 2) KMP automaton for $P=\text{str}(n)$ The code builds a Knuth-Morris-Pratt automaton for the decimal pattern $P$. A state $q\in\{0,\dots,L\}$, where $L=|P|$, means: “the last processed digits currently match the first $q$ digits of $P$”. For every state $q$ and digit $d\in\{0,\dots,9\}$, the automaton stores: $$q'=\delta(q,d),$$ and an output bit $$o(q,d)\in\{0,1\},$$ which tells whether reading digit $d$ completes one new occurrence of $P$. Because the KMP fallback is applied after a full match, overlapping occurrences are counted correctly. 3) Operator view of a digit block For any finite digit string $w$, define an operator $T_w$....

Detailed mathematical approach

Problem Summary

Write the positive integers one after another in base $10$ and read the result as a single infinite digit string

$$S=12345678910111213\ldots$$

Positions are counted from $1$. For a positive integer $n$ let $P$ be its decimal digit string and $L$ the length of $P$. Every integer occurs in $S$ infinitely often, and $f(n)$ is the starting position of the $n$-th occurrence of $P$. The statement gives $f(1)=1$, $f(5)=81$, $f(12)=271$ and $f(7780)=111111365$, and asks for ^[1]

$$\sum_{k=1}^{13}f\bigl(3^{k}\bigr),$$

with the thirteen patterns $3$, $9$, $27$, $81$, $243$, $729$, $2187$, $6561$, $19683$, $59049$, $177147$, $531441$, $1594323$.

The whole solution in one sentence: instead of writing out digits we summarise what a whole block of consecutive integers does to a pattern-matching machine, glue such summaries together to count the occurrences finishing among the first $N$ integers, and halve a search interval until we reach the integer in which the wanted occurrence finishes.

Mathematical Approach

Three obstacles must be cleared: for the largest pattern the occurrence lies beyond position $10^{13}$, so that prefix of $S$ cannot be materialised; occurrences straddle the seams between integers, so $S$ is one stream; and $f$ is erratic, $f(20)=2651$ against $f(21)=541$, so it cannot be searched directly. One monotone counting function and an algebra of digit blocks cure all three.

1. Positions, occurrences and why $f$ exists

An occurrence of $P$ is a position $p$ with $S_{p}S_{p+1}\cdots S_{p+L-1}=P$; occurrences are listed by increasing $p$, and overlapping ones each count. Since $n\cdot 10^{m}$ begins with the digits of $n$ for every $m\ge 0$, $P$ occurs infinitely often and $f$ is defined. ^[1]

One example needs no machinery. The digits $1,\ldots,9$ fill positions $1$ to $9$ and the two-digit integers follow, two each, so $45$ occupies positions $80$ and $81$. The first five occurrences of $P=5$ are the last digits of $5,15,25,35,45$ — no earlier integer carries a $5$ in a higher place — so the fifth is the last digit of $45$ and $f(5)=81$, as the statement says. The sixth is the leading digit of $50$.

2. Occurrences cross the seams

Take $n=12$, so $P=12$. The first occurrence is at position $1$: the digit $1$ is the whole integer $1$, the digit $2$ the whole integer $2$. A second seam is the pair $21,22$, filling positions $32$ to $35$ with $2,1,2,2$: the $1$ of $21$ followed by the $2$ of $22$ is an occurrence starting at position $33$. A direct scan gives the first twelve starting positions of $P=12$ as

$$1,\ 14,\ 33,\ 227,\ 250,\ 253,\ 256,$$

$$259,\ 262,\ 265,\ 268,\ 271,$$

so $f(12)=271$, again as the statement says. Two of the twelve lie on a seam, so any method restarting the match at each integer boundary would report a wrong value.

3. One monotone counting function

Let $C_N$ be the string $123\cdots N$, the concatenation of the integers $1$ to $N$, and let $A(N)$ count the occurrences of $P$ whose last digit lies in $C_N$, including those begun in an earlier integer. Appending integers never destroys an occurrence, so $A$ is nondecreasing, and $A(N)\to\infty$ by Section 1. Therefore

$$M=\min\{N: A(N)\ge n\}$$

is well defined, and it is the integer inside which the $n$-th occurrence ends. All occurrences have length $L$, so ordering by last digit is ordering by first digit, and the problem's $n$-th occurrence is the $n$-th counted by $A$. Monotonicity lets a binary search find $M$ in its leftmost-match form, in about $\log_{2}M$ evaluations. ^[7] All now rests on evaluating $A(N)$ quickly for $N$ up to roughly $10^{13}$.

4. An automaton that counts occurrences

Scanning a stream for one pattern is the classical task of the Knuth–Morris–Pratt algorithm. ^[3] Let the state $q$ be the length of the longest suffix of what was read that is also a proper prefix of $P$, so $q\in\{0,\ldots,L-1\}$. Reading a digit $d$ gives a state $\delta(q,d)$ and an output bit $o(q,d)$ that is $1$ exactly when that digit completes an occurrence. Both tables come from the failure function $\pi$, where $\pi(i)$ is the longest proper border of the prefix of length $i+1$: a proper prefix that is also a suffix.

For $P=12$ the tables are tiny: $\delta(q,1)=1$ for every $q$, $\delta(q,d)=0$ otherwise, and the only nonzero output is $o(1,2)=1$. For $P=11$, $o(1,1)=1$ and $\delta(1,1)=1$, since after a match the automaton falls back to the border $1$ rather than $0$; scanning $111$ therefore reports two occurrences — the overlapping convention of Section 1.

The convention could matter, so check that it does not here. Two occurrences at positions $i\lt j\lt i+L$ force a proper border of length $i+L-j\ge 1$, so a pattern with longest proper border $0$ admits no overlapping pair. All thirteen patterns have border $0$, $1594323$ included, so the requested sum is the same either way. In general the convention matters: $f(11)=235$ with overlaps, $244$ without.

5. The scanning operator of a digit block

For a digit string $w$ define a map $T_{w}$ sending each starting state $q$ to the pair

$$T_{w}(q)=\bigl(e_{w}(q),\,c_{w}(q)\bigr),$$

where $e_{w}(q)$ is the state after scanning $w$ from $q$ and $c_{w}(q)$ the number of occurrences completed in that scan. These two arrays, indexed by $q$, are what the programs store as end_state and add_count. Keeping a whole array rather than one number is the key move: $T_{w}$ answers for every context at once, so a block can be processed before we know what precedes it.

Operators combine. Split $w=uv$: scanning $uv$ from $q$ means scanning $u$, arriving in $e_{u}(q)$, then scanning $v$ from there. Every occurrence is completed by exactly one digit, in $u$ or in $v$, so the counts add:

$$e_{uv}(q)=e_{v}\bigl(e_{u}(q)\bigr),$$

$$c_{uv}(q)=c_{u}(q)+c_{v}\bigl(e_{u}(q)\bigr).$$

An occurrence straddling the cut is still counted once, in $v$, where its last digit lies; nothing is lost at a seam. Regrouping three blocks changes neither the final state nor the number of matches, so the rule is associative, and the empty string is an identity. A set with an associative rule and an identity is a monoid; digit strings form one under concatenation, and $w\mapsto T_{w}$ turns concatenation into the rule above, making it a homomorphism. ^[6] Once a block's operator is known, its digits are never read again.

Why the array matters: for $P=12$ the block $20\,21\cdots 29$ has $c(0)=1$ but $c(1)=2$, because entering in state $1$, with a $1$ just before it, makes the leading $2$ of $20$ complete an extra occurrence. In $S$ it is entered in state $0$, after the $9$ of $19$ — but it cannot know that in advance.

6. A digit dynamic programme for $C_N$

Let $p$ be a digit string with a nonzero first digit and $r\ge 0$, and let $\mathrm{fb}(p,r)$ be the operator of the integers formed by appending to $p$ every suffix of exactly $r$ digits, in increasing order; suffix leading zeroes are kept, so there are $10^{r}$ of them. Then

$$\begin{aligned}\mathrm{fb}(p,0)&=T_{p},\\ \mathrm{fb}(p,r)&=\prod_{d=0}^{9}\mathrm{fb}(pd,\,r-1),\end{aligned}$$

the product combining in increasing order of $d$, which is increasing numeric order. The top of the range needs a one-sided version: for $0\le u\lt 10^{r}$ let $\mathrm{pb}(p,r,u)$ be the same block restricted to suffixes of value at most $u$. With $u=a\cdot 10^{r-1}+u'$, $0\le u'\lt 10^{r-1}$, and an empty product read as the identity,

$$\begin{aligned}\mathrm{pb}(p,r,u)=&\Bigl(\prod_{d=0}^{a-1}\mathrm{fb}(pd,r-1)\Bigr)\\ &\cdot\,\mathrm{pb}(pa,r-1,u'),\end{aligned}$$

with $\mathrm{pb}(p,0,0)=T_{p}$. Now let $N$ have $D$ digits and leading digit $a_{1}$. The integers $1$ to $N$ split into those with fewer than $D$ digits, those with $D$ digits and a smaller leading digit, and the rest:

$$T_{C_N}=\prod_{d=1}^{D-1}\ \prod_{a=1}^{9}\mathrm{fb}(a,d-1)$$

$$\begin{aligned}\cdot\ &\prod_{a=1}^{a_{1}-1}\mathrm{fb}(a,D-1)\\ &\cdot\ \mathrm{pb}\bigl(a_{1},D-1,u\bigr),\end{aligned}$$

where $u$ is $N$ without its leading digit. Reading the result at state $0$ gives $A(N)=c_{C_N}(0)$, because $S$ begins with $C_N$ and the automaton starts in state $0$.

Taken literally, $\mathrm{fb}(p,r)$ branches ten ways to depth $r$: $10^{r}$ leaves, exactly the digits we refused to write out. The saving is that $\mathrm{fb}$ is cached on $\bigl(T_{p},r\bigr)$ rather than on the string $p$, and that key loses nothing. Suppose $T_{p}=T_{q}$; appending any digit $d$ gives $T_{pd}=T_{qd}$ by the rule of Section 5, so induction on $r$ from $r=0$ makes corresponding child blocks equal and hence $\mathrm{fb}(p,r)=\mathrm{fb}(q,r)$, end states and counts alike. Such coincidences are common: with $P=12$ the prefixes $3$ and $4$ both send every state to $0$ and complete nothing, so $T_{3}=T_{4}$. Operators are also interned, stored once and named by an index, so comparing them means comparing small integers. For $P=1594323$ the run produces only $1012$ distinct operators and $570$ cached blocks.

7. Worked example: $A(30)$ for $P=12$

Here $N=30$ has $D=2$ digits and leading digit $3$, so Section 6 decomposes

$$\begin{aligned}C_{30}=\ &\underbrace{1\cdots 9}_{\mathrm{fb}(a,0),\,a\le 9}\ \underbrace{10\cdots 19}_{\mathrm{fb}(1,1)}\\ &\underbrace{20\cdots 29}_{\mathrm{fb}(2,1)}\ \underbrace{30}_{\mathrm{pb}(3,1,0)}.\end{aligned}$$

The four operators give $c(0)=1,1,1,0$; each block ends in a $9$ or a $0$ and so leaves state $0$, and the counts add to $A(30)=3$. Those three are the seam $1\mid 2$ at $1$, the integer $12$ at $14$ and the seam $21\mid 22$ at $33$; a direct count in $123456789101112\ldots 2930$ also finds three.

8. From $M$ to the position

Two ingredients finish the job. First, where an integer starts: the integers with exactly $d$ digits number $9\cdot 10^{d-1}$ and give $d$ digits each, so for $N$ with $D$ digits the length of $C_N$ is

$$\begin{aligned}\mathrm{dig}(N)=\ &\sum_{d=1}^{D-1}9\cdot 10^{d-1}d\\ &+\bigl(N-10^{D-1}+1\bigr)D,\end{aligned}$$

the last term counting the $D$-digit integers from $10^{D-1}$ to $N$. With $C_{0}$ empty, so $A(0)=\mathrm{dig}(0)=0$, every $N\ge 1$ occupies positions $\mathrm{dig}(N-1)+1$ to $\mathrm{dig}(N)$.

Second, the occurrence inside $M$. Let $b=A(M-1)$ and $q_{0}$ the state after $C_{M-1}$, both read at index $0$ of the same operator; we want occurrence number $n-b$ among those completed inside $M$. Run the automaton from $q_{0}$ over the digits of $M$ and suppose the wanted output bit falls on the digit at index $i$, counted from $0$. That digit sits at position $\mathrm{dig}(M-1)+i+1$, and as every occurrence is $L$ digits long,

$$f(n)=\mathrm{dig}(M-1)+i+2-L.$$

This stays correct when the occurrence begins in an earlier integer: the subtraction walks back across the seam, as it must for the $12$ at position $1$, which ends inside the integer $2$.

9. Worked example: $f(12)=271$

For $n=12$ and $P=12$ the dynamic programme gives $A(126)=11$ and $A(127)=12$, so $M=127$, and $\mathrm{dig}(126)=9+180+81=270$ puts $127$ at positions $271,272,273$. We need occurrence number $12-11=1$ inside it. The integer $126$ ends in a $6$, leaving the automaton in state $q_{0}=0$; scanning $127$, the digit $1$ moves to state $1$ with no output and the digit $2$, at index $i=1$, outputs a match. Hence $f(12)=270+1+2-2=271$; the same route gives $f(5)=81$ from $M=45$ and $\mathrm{dig}(44)=79$.

10. How far the search reaches

The string $S$ is the digit expansion of Champernowne's constant, proved normal in base $10$ by Champernowne in 1933: every block of $L$ digits has asymptotic density $10^{-L}$. ^[4] ^[5] For a fixed pattern that suggests the scale $n\cdot 10^{L}$ for its $n$-th occurrence; here the pattern grows with $n$, so $f(n)\approx n\cdot 10^{L}$ is a heuristic for which normality gives no error bound, and the search uses doubling instead. The scale is right: for $k=1,\ldots,5$ the ratio $f(3^{k})/(3^{k}10^{L})$ is $1.23$, $1.88$, $0.82$, $0.58$, $0.66$, and for $k=13$, with $n=1594323$ and $L=7$, the search ends inside a $13$-digit integer.

How the Code Works

All three programs centre on PatternEngine, built from the decimal string of one pattern; the driver (solve_sum_k in C++, solve in Python and Java) creates a fresh engine for each of $3,9,\ldots,3^{13}$, since every cached operator belongs to one automaton, and sums the returned positions.

build_automaton, buildAutomaton in Java, implements Section 4: it fills pi by the standard border recursion, then the transition tables, named next_/out_ in C++, next_state/out in Python and nextState/out in Java. A transition reaching length $L$ sets the output bit and falls back to pi[L-1], which makes overlapping occurrences count. All three allocate $L+1$ rows, but row $L$ is unreachable from state $0$, so the states stay $0,\ldots,L-1$.

C++ keeps an operator in an Op struct of end_state and add_count arrays, Java in an Op class with endState and addCount; Python has no such type and stores a pair of lists, using their tuple copies as the interning key. intern_op returns an operator's index or registers it in ops and op_to_id, and build_digit_operators registers id_identity and the ten digit_op_id[d]. On a cache miss compose_ids fills both result arrays in one loop over $L+1$ entries by the rule of Section 5, and on a hit returns the stored index. append_digit is the one-digit case with its own cache; full_block and partial_block implement $\mathrm{fb}$ and $\mathrm{pb}$, with full_block_cache keyed on the prefix operator's index and the number of free digits.

range_operator assembles $T_{C_N}$ in the three-part order of Section 6, occ_and_state reads $\bigl(A(N),q\bigr)$ from entry $0$, and digits_before is $\mathrm{dig}$. nth_occurrence_position runs Sections 3 and 8: it doubles hi until $A(\mathtt{hi})\ge n$, narrows to the leftmost such $N$, reads $b$ and $q_{0}$ from occ_and_state(number - 1), then walks the digits of number until the output bits reach $n-b$ and returns end_pos - L + 1.

C++ hashes whole Op values with a hand-written OpHash into an unordered_map, whose average constant-time lookup makes interning cheap; ^[8] Java uses Arrays.equals and HashMap, Python plain dictionaries. Python has arbitrary-precision integers, C++ unsigned $64$-bit counts and positions, Java signed long. A count query at $N=2^{41}$ already reaches the required count for all thirteen patterns, and $13\,\mathrm{dig}(2^{41})\lt 10^{15}$, so every value and their sum fit easily; the one-byte state is safe only because $L\le 7$. C++ guards the doubling of hi against overflow and Java does not, and both fixed-width ports fill their power-of-ten tables past the representable range — $10^{20}$ wraps in C++, $10^{19}$ already in Java — but never read those entries.

Only the C++ version carries self-tests and options: --k-max=, --single= and --skip-checkpoints, parsed by parse_arguments into Options. run_checkpoints reproduces the four statement values, then compares the engine with brute_nth_position_small for $n=1,\ldots,30$; that brute force appends one integer at a time to an explicit string and rescans only from offset old_size${}-(L-1)$, the earliest start a new digit can belong to.

Complexity and Verification

Let $L$ be the pattern length and $D$ the number of digits of $M$. The failure function costs $O(L)$, but building the transition tables costs $O(10L^{2})$ in the worst case, since every state-and-digit pair walks its own chain of failure links — a pattern of equal digits attains that, taking $253$ link steps for $1111111$ against $64$ for $1594323$. A composition that misses the cache fills and hashes both arrays, costing $O(L)$; a hit returns an index in expected constant time. Let $F$ count the full-block entries created in one search: each is expanded once with at most ten children, one evaluation of $A$ issues $O(D)$ further requests, and doubling plus binary search makes $O(D)$ evaluations, so the search costs

$$O\bigl(10L^{2}+10L(F+D^{2})\bigr).$$

There is no clean bound on $F$, which depends on how many digit prefixes share an operator, so it is measured: for $L=7$ the run makes $84$ calls to range_operator and $16467$ to compose_ids, $1818$ of them misses, interning $1012$ operators and storing $F=570$ blocks — well under $10^{6}$ array operations, but a measurement for these patterns, not a bound for arbitrary ones.

Memory holds the operator table, the interning map and all three caches, so with $U$ interned operators and $F$, $H$, $J$ full-block, composition and append entries it is $O(UL+F+H+J+D)$ words. For the largest pattern those are $1012$, $570$, $1818$ and $790$, and the arrays in the C++ ops_ table alone hold $72864$ payload bytes; copied keys, caches and allocator overhead add more, Java and Python objects more again, so this is no whole-process figure. All these counts are machine-independent, whereas elapsed time also depends on compiler, runtime and process startup.

The following was verified here. An independent brute force — two million digits of $S$ built explicitly and scanned for $P$ with overlapping matches — agrees with the engine for $n=1,\ldots,30$ and reproduces all four checkpoints $f(1)=1$, $f(5)=81$, $f(12)=271$, $f(7780)=111111365$. The $A(30)=3$ of Section 7 and the twelve positions of Section 2 match direct counts in that string, and $f(1),\ldots,f(20)$ agree term by term with OEIS A181362, which is this sequence. ^[2] The last failure-function entry $\pi(L-1)$ is zero for all thirteen patterns, so none has a nonempty border and the overlap convention cannot affect the requested sum; earlier entries need not vanish, and $P=6561$ has $\pi=(0,0,1,0)$. The three programs print the same total, which checks the ports against one another, while the brute force, the scans and the OEIS comparison are the independent evidence. ^[9]

Footnotes and References

The references supply the background facts used above; the counting function $A$, the operator algebra, the decomposition of $C_N$, the formula for $\mathrm{dig}(N)$, the border argument and all measured counts are derived here.

Project Euler 305 — Reflexive Position. The official statement makes S the concatenation of the consecutive positive integers in base 10, notes that any number shows up infinitely often, defines f(n) as the starting position of the nth occurrence of n in S, lists f(1) = 1, f(5) = 81, f(12) = 271, f(7780) = 111111365, and asks for the sum of f(3^k) over 1 ≤ k ≤ 13.
OEIS A181362 — starting position of the n-th occurrence of n. Defined exactly as f above, with first terms 1, 15, 37, 59, 81, 103, 125, 147, 169, 214, 235, 271, 307, 533, 836, 1139, 1442, 1745, 2048, 2651, the values compared against here.
Wikipedia — Knuth–Morris–Pratt algorithm. The partial match table, also called the failure function, records for each prefix the length of the longest proper initial segment that is also a suffix; it is built in O(k) and the scan is O(n), so matching costs O(n + k). After a full match the search resumes from that table entry instead of restarting — which is how overlapping occurrences are found.
Wikipedia — Champernowne constant. C₁₀ = 0.1234567891011121314151617181920… concatenates the base-10 representations of the positive integers. It is named after D. G. Champernowne, who published it as an undergraduate in 1933 and proved it normal in base 10; its fractional digits are the string S.
Wikipedia — Normal number. A number is normal in base b when all strings of n digits have density b^(−n): the occurrences of a fixed block w among the first n digits, divided by n, tend to b^(−|w|). This is a limit for each fixed block, with no error term.
Wikipedia — Monoid. A monoid is a set with an associative binary operation and an identity element, and strings over a fixed alphabet form the free monoid under concatenation. The operators of Section 5 carry a state and a count together, so their monoid and its rule are derived there, not taken from this source.
Wikipedia — Binary search. The search runs in logarithmic time, with O(log n) comparisons and at most ⌊log₂ n + 1⌋ iterations. The article gives the leftmost-element procedure, which moves the right endpoint whenever the tested value is at least the target — the variant used to locate M.
cppreference — std::unordered_map. Search, insertion and removal have average constant-time complexity, and equivalent keys must receive equal hash values — the contract OpHash and Op::operator== must satisfy for interning to be correct.
C++ — Euler305.cpp. The linked immutable revision contains PatternEngine with build_automaton, compose_ids, full_block, partial_block, range_operator and nth_occurrence_position, plus brute_nth_position_small and run_checkpoints. It is the implementation record for this article.

Problem 305 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int k_max = 13;
    bool run_checkpoints = true;
    u64 single_n = 0;
};

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_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;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<u64>(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, "--k-max=", options.k_max)) {
            continue;
        }
        if (parse_u64_after_prefix(arg, "--single=", options.single_n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.k_max >= 1;
}

struct Op {
    std::vector<std::uint8_t> end_state;
    std::vector<u64> add_count;

    bool operator==(const Op& other) const {
        return end_state == other.end_state && add_count == other.add_count;
    }
};

struct OpHash {
    std::size_t operator()(const Op& op) const {
        std::size_t h = 1469598103934665603ULL;
        for (std::uint8_t v : op.end_state) {
            h ^= static_cast<std::size_t>(v) + 0x9e3779b97f4a7c15ULL + (h << 6U) + (h >> 2U);
        }
        for (u64 v : op.add_count) {
            h ^= static_cast<std::size_t>(v ^ (v >> 32U)) + 0x9e3779b97f4a7c15ULL + (h << 6U) + (h >> 2U);
        }
        return h;
    }
};

class PatternEngine {
public:
    explicit PatternEngine(const std::string& pattern)
        : pattern_(pattern), L_(static_cast<int>(pattern.size())) {
        build_automaton();
        build_digit_operators();
        build_pow10(20);
    }

    u64 nth_occurrence_position(const u64 target_occurrence) {
        u64 hi = 1;
        while (occ_and_state(hi).first < target_occurrence) {
            if (hi > std::numeric_limits<u64>::max() / 2ULL) {
                hi = std::numeric_limits<u64>::max();
                break;
            }
            hi *= 2ULL;
        }

        u64 lo = 1;
        while (lo < hi) {
            const u64 mid = lo + (hi - lo) / 2ULL;
            if (occ_and_state(mid).first >= target_occurrence) {
                hi = mid;
            } else {
                lo = mid + 1ULL;
            }
        }

        const u64 number = lo;
        const auto [before_count, before_state] = occ_and_state(number - 1ULL);
        const u64 need_inside = target_occurrence - before_count;

        u64 prefix_digits = digits_before(number - 1ULL);
        u64 found_inside = 0;
        int state = before_state;

        const std::string num = std::to_string(number);
        for (std::size_t i = 0; i < num.size(); ++i) {
            const int d = num[i] - '0';
            if (out_[state][d] != 0) {
                ++found_inside;
                if (found_inside == need_inside) {
                    const u64 end_pos = prefix_digits + static_cast<u64>(i + 1);
                    return end_pos - static_cast<u64>(L_) + 1ULL;
                }
            }
            state = next_[state][d];
        }

        return 0;
    }

private:
    std::string pattern_;
    int L_ = 0;

    std::vector<std::vector<int>> next_;
    std::vector<std::vector<std::uint8_t>> out_;

    std::vector<Op> ops_;
    std::unordered_map<Op, int, OpHash> op_to_id_;

    int id_identity_ = -1;
    std::array<int, 10> digit_op_id_{};

    std::unordered_map<u64, int> compose_cache_;
    std::unordered_map<u64, int> append_cache_;
    std::unordered_map<u64, int> full_block_cache_;

    std::vector<u64> pow10_;

    static u64 make_key(const int a, const int b) {
        return (static_cast<u64>(a) << 32U) | static_cast<std::uint32_t>(b);
    }

    int intern_op(const Op& op) {
        const auto it = op_to_id_.find(op);
        if (it != op_to_id_.end()) {
            return it->second;
        }
        const int id = static_cast<int>(ops_.size());
        ops_.push_back(op);
        op_to_id_.emplace(ops_[static_cast<std::size_t>(id)], id);
        return id;
    }

    void build_automaton() {
        std::vector<int> pi(static_cast<std::size_t>(L_), 0);
        for (int i = 1; i < L_; ++i) {
            int j = pi[static_cast<std::size_t>(i - 1)];
            while (j > 0 && pattern_[static_cast<std::size_t>(i)] != pattern_[static_cast<std::size_t>(j)]) {
                j = pi[static_cast<std::size_t>(j - 1)];
            }
            if (pattern_[static_cast<std::size_t>(i)] == pattern_[static_cast<std::size_t>(j)]) {
                ++j;
            }
            pi[static_cast<std::size_t>(i)] = j;
        }

        next_.assign(static_cast<std::size_t>(L_ + 1), std::vector<int>(10, 0));
        out_.assign(static_cast<std::size_t>(L_ + 1), std::vector<std::uint8_t>(10, 0));

        for (int st = 0; st <= L_; ++st) {
            for (int d = 0; d <= 9; ++d) {
                const char c = static_cast<char>('0' + d);
                int j = st;
                while (j > 0 && (j == L_ || pattern_[static_cast<std::size_t>(j)] != c)) {
                    j = pi[static_cast<std::size_t>(j - 1)];
                }
                if (j < L_ && pattern_[static_cast<std::size_t>(j)] == c) {
                    ++j;
                }

                if (j == L_) {
                    out_[static_cast<std::size_t>(st)][static_cast<std::size_t>(d)] = 1;
                    j = pi[static_cast<std::size_t>(L_ - 1)];
                }
                next_[static_cast<std::size_t>(st)][static_cast<std::size_t>(d)] = j;
            }
        }
    }

    void build_digit_operators() {
        Op identity;
        identity.end_state.resize(static_cast<std::size_t>(L_ + 1));
        identity.add_count.assign(static_cast<std::size_t>(L_ + 1), 0);
        for (int s = 0; s <= L_; ++s) {
            identity.end_state[static_cast<std::size_t>(s)] = static_cast<std::uint8_t>(s);
        }
        id_identity_ = intern_op(identity);

        for (int d = 0; d <= 9; ++d) {
            Op op;
            op.end_state.resize(static_cast<std::size_t>(L_ + 1));
            op.add_count.resize(static_cast<std::size_t>(L_ + 1));
            for (int s = 0; s <= L_; ++s) {
                op.end_state[static_cast<std::size_t>(s)] =
                    static_cast<std::uint8_t>(next_[static_cast<std::size_t>(s)][static_cast<std::size_t>(d)]);
                op.add_count[static_cast<std::size_t>(s)] =
                    static_cast<u64>(out_[static_cast<std::size_t>(s)][static_cast<std::size_t>(d)]);
            }
            digit_op_id_[static_cast<std::size_t>(d)] = intern_op(op);
        }
    }

    void build_pow10(const int max_power) {
        pow10_.assign(static_cast<std::size_t>(max_power + 1), 1ULL);
        for (int i = 1; i <= max_power; ++i) {
            pow10_[static_cast<std::size_t>(i)] = pow10_[static_cast<std::size_t>(i - 1)] * 10ULL;
        }
    }

    int compose_ids(const int id_a, const int id_b) {
        const u64 key = make_key(id_a, id_b);
        const auto it = compose_cache_.find(key);
        if (it != compose_cache_.end()) {
            return it->second;
        }

        const Op& A = ops_[static_cast<std::size_t>(id_a)];
        const Op& B = ops_[static_cast<std::size_t>(id_b)];

        Op C;
        C.end_state.resize(static_cast<std::size_t>(L_ + 1));
        C.add_count.resize(static_cast<std::size_t>(L_ + 1));

        for (int s = 0; s <= L_; ++s) {
            const int mid = A.end_state[static_cast<std::size_t>(s)];
            C.end_state[static_cast<std::size_t>(s)] = B.end_state[static_cast<std::size_t>(mid)];
            C.add_count[static_cast<std::size_t>(s)] =
                A.add_count[static_cast<std::size_t>(s)] + B.add_count[static_cast<std::size_t>(mid)];
        }

        const int id = intern_op(C);
        compose_cache_.emplace(key, id);
        return id;
    }

    int append_digit(const int op_id, const int d) {
        const u64 key = make_key(op_id, d);
        const auto it = append_cache_.find(key);
        if (it != append_cache_.end()) {
            return it->second;
        }
        const int id = compose_ids(op_id, digit_op_id_[static_cast<std::size_t>(d)]);
        append_cache_.emplace(key, id);
        return id;
    }

    int full_block(const int prefix_op, const int rem_digits) {
        const u64 key = make_key(prefix_op, rem_digits);
        const auto it = full_block_cache_.find(key);
        if (it != full_block_cache_.end()) {
            return it->second;
        }

        int id;
        if (rem_digits == 0) {
            id = prefix_op;
        } else {
            int result = id_identity_;
            for (int d = 0; d <= 9; ++d) {
                const int child = full_block(append_digit(prefix_op, d), rem_digits - 1);
                result = compose_ids(result, child);
            }
            id = result;
        }

        full_block_cache_.emplace(key, id);
        return id;
    }

    int partial_block(const int prefix_op, const int rem_digits, const u64 upper_suffix) {
        if (rem_digits == 0) {
            return prefix_op;
        }

        const u64 base = pow10_[static_cast<std::size_t>(rem_digits - 1)];
        const int first = static_cast<int>(upper_suffix / base);
        const u64 rest = upper_suffix % base;

        int result = id_identity_;
        for (int d = 0; d < first; ++d) {
            const int child = full_block(append_digit(prefix_op, d), rem_digits - 1);
            result = compose_ids(result, child);
        }

        const int last = partial_block(append_digit(prefix_op, first), rem_digits - 1, rest);
        result = compose_ids(result, last);
        return result;
    }

    int range_operator(const u64 N) {
        if (N == 0) {
            return id_identity_;
        }

        const std::string s = std::to_string(N);
        const int D = static_cast<int>(s.size());

        int result = id_identity_;

        for (int d = 1; d < D; ++d) {
            const int rem = d - 1;
            for (int a = 1; a <= 9; ++a) {
                const int block = full_block(digit_op_id_[static_cast<std::size_t>(a)], rem);
                result = compose_ids(result, block);
            }
        }

        const int first = s[0] - '0';
        const int rem = D - 1;

        for (int a = 1; a < first; ++a) {
            const int block = full_block(digit_op_id_[static_cast<std::size_t>(a)], rem);
            result = compose_ids(result, block);
        }

        if (rem == 0) {
            result = compose_ids(result, digit_op_id_[static_cast<std::size_t>(first)]);
        } else {
            u64 suffix = 0;
            for (int i = 1; i < D; ++i) {
                suffix = suffix * 10ULL + static_cast<u64>(s[static_cast<std::size_t>(i)] - '0');
            }
            const int part = partial_block(digit_op_id_[static_cast<std::size_t>(first)], rem, suffix);
            result = compose_ids(result, part);
        }

        return result;
    }

    std::pair<u64, int> occ_and_state(const u64 N) {
        const int op_id = range_operator(N);
        const Op& op = ops_[static_cast<std::size_t>(op_id)];
        return {op.add_count[0], static_cast<int>(op.end_state[0])};
    }

    u64 digits_before(const u64 N) const {
        if (N == 0) {
            return 0;
        }

        const std::string s = std::to_string(N);
        const int D = static_cast<int>(s.size());

        u64 total = 0;
        for (int d = 1; d < D; ++d) {
            total += 9ULL * pow10_[static_cast<std::size_t>(d - 1)] * static_cast<u64>(d);
        }

        total += (N - pow10_[static_cast<std::size_t>(D - 1)] + 1ULL) * static_cast<u64>(D);
        return total;
    }
};

u64 brute_nth_position_small(const int n) {
    const std::string token = std::to_string(n);
    const int L = static_cast<int>(token.size());

    std::string stream;
    stream.reserve(10000);
    std::vector<u64> starts;
    starts.reserve(static_cast<std::size_t>(n));

    u64 checked_until = 0;

    for (int x = 1; static_cast<int>(starts.size()) < n; ++x) {
        const std::string s = std::to_string(x);
        const u64 old_size = static_cast<u64>(stream.size());
        stream += s;

        const u64 begin = (old_size >= static_cast<u64>(L - 1)) ? (old_size - static_cast<u64>(L - 1)) : 0ULL;
        for (u64 i = begin; i + static_cast<u64>(L) <= static_cast<u64>(stream.size()); ++i) {
            bool match = true;
            for (int j = 0; j < L; ++j) {
                if (stream[static_cast<std::size_t>(i + static_cast<u64>(j))] != token[static_cast<std::size_t>(j)]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                if (starts.empty() || starts.back() != i + 1ULL) {
                    starts.push_back(i + 1ULL);
                }
            }
        }
        checked_until = old_size;
        (void)checked_until;
    }

    return starts[static_cast<std::size_t>(n - 1)];
}

bool run_checkpoints() {
    struct Sample {
        u64 n;
        u64 expected;
    };

    const std::vector<Sample> samples = {
        {1ULL, 1ULL},
        {5ULL, 81ULL},
        {12ULL, 271ULL},
        {7780ULL, 111111365ULL},
    };

    for (const auto& s : samples) {
        PatternEngine engine(std::to_string(s.n));
        const u64 got = engine.nth_occurrence_position(s.n);
        if (got != s.expected) {
            std::cerr << "Sample checkpoint failed for n=" << s.n << ": got " << got
                      << ", expected " << s.expected << '\n';
            return false;
        }
    }

    for (int n = 1; n <= 30; ++n) {
        PatternEngine engine(std::to_string(n));
        const u64 fast = engine.nth_occurrence_position(static_cast<u64>(n));
        const u64 brute = brute_nth_position_small(n);
        if (fast != brute) {
            std::cerr << "Brute checkpoint failed for n=" << n << ": fast=" << fast
                      << ", brute=" << brute << '\n';
            return false;
        }
    }

    return true;
}

u64 solve_sum_k(const int k_max) {
    u64 sum = 0;
    u64 n = 1;
    for (int k = 1; k <= k_max; ++k) {
        n *= 3ULL;
        PatternEngine engine(std::to_string(n));
        sum += engine.nth_occurrence_position(n);
    }
    return sum;
}

}  // 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;
    }

    if (options.single_n > 0) {
        PatternEngine engine(std::to_string(options.single_n));
        std::cout << engine.nth_occurrence_position(options.single_n) << '\n';
        return 0;
    }

    std::cout << solve_sum_k(options.k_max) << '\n';
    return 0;
}

Python

import sys

class PatternEngine:
    def __init__(self, pattern):
        self.pattern = pattern
        self.L = len(pattern)
        self.next_state = [[0] * 10 for _ in range(self.L + 1)]
        self.out = [[0] * 10 for _ in range(self.L + 1)]
        self.build_automaton()
        
        self.ops = []
        self.op_to_id = {}
        
        self.id_identity = -1
        self.digit_op_id = [0] * 10
        self.build_digit_operators()
        
        self.compose_cache = {}
        self.append_cache = {}
        self.full_block_cache = {}
        
        self.pow10 = [1] * 21
        for i in range(1, 21):
            self.pow10[i] = self.pow10[i - 1] * 10

    def build_automaton(self):
        pi = [0] * self.L
        for i in range(1, self.L):
            j = pi[i - 1]
            while j > 0 and self.pattern[i] != self.pattern[j]:
                j = pi[j - 1]
            if self.pattern[i] == self.pattern[j]:
                j += 1
            pi[i] = j
            
        for st in range(self.L + 1):
            for d in range(10):
                c = str(d)
                j = st
                while j > 0 and (j == self.L or self.pattern[j] != c):
                    j = pi[j - 1]
                if j < self.L and self.pattern[j] == c:
                    j += 1
                if j == self.L:
                    self.out[st][d] = 1
                    j = pi[self.L - 1]
                self.next_state[st][d] = j

    def intern_op(self, end_state, add_count):
        key = (tuple(end_state), tuple(add_count))
        if key in self.op_to_id:
            return self.op_to_id[key]
        op_id = len(self.ops)
        self.ops.append((end_state, add_count))
        self.op_to_id[key] = op_id
        return op_id

    def build_digit_operators(self):
        end_state = list(range(self.L + 1))
        add_count = [0] * (self.L + 1)
        self.id_identity = self.intern_op(end_state, add_count)
        
        for d in range(10):
            es = [0] * (self.L + 1)
            ac = [0] * (self.L + 1)
            for s in range(self.L + 1):
                es[s] = self.next_state[s][d]
                ac[s] = self.out[s][d]
            self.digit_op_id[d] = self.intern_op(es, ac)

    def compose_ids(self, id_a, id_b):
        key = (id_a, id_b)
        if key in self.compose_cache:
            return self.compose_cache[key]
            
        A_es, A_ac = self.ops[id_a]
        B_es, B_ac = self.ops[id_b]
        
        C_es = [0] * (self.L + 1)
        C_ac = [0] * (self.L + 1)
        for s in range(self.L + 1):
            mid = A_es[s]
            C_es[s] = B_es[mid]
            C_ac[s] = A_ac[s] + B_ac[mid]
            
        res = self.intern_op(C_es, C_ac)
        self.compose_cache[key] = res
        return res

    def append_digit(self, op_id, d):
        key = (op_id, d)
        if key in self.append_cache:
            return self.append_cache[key]
        res = self.compose_ids(op_id, self.digit_op_id[d])
        self.append_cache[key] = res
        return res

    def full_block(self, prefix_op, rem_digits):
        key = (prefix_op, rem_digits)
        if key in self.full_block_cache:
            return self.full_block_cache[key]
            
        if rem_digits == 0:
            res = prefix_op
        else:
            res = self.id_identity
            for d in range(10):
                child = self.full_block(self.append_digit(prefix_op, d), rem_digits - 1)
                res = self.compose_ids(res, child)
                
        self.full_block_cache[key] = res
        return res

    def partial_block(self, prefix_op, rem_digits, upper_suffix):
        if rem_digits == 0:
            return prefix_op
            
        base = self.pow10[rem_digits - 1]
        first = int(upper_suffix // base)
        rest = int(upper_suffix % base)
        
        res = self.id_identity
        for d in range(first):
            child = self.full_block(self.append_digit(prefix_op, d), rem_digits - 1)
            res = self.compose_ids(res, child)
            
        last = self.partial_block(self.append_digit(prefix_op, first), rem_digits - 1, rest)
        res = self.compose_ids(res, last)
        return res

    def range_operator(self, N):
        if N == 0:
            return self.id_identity
            
        s = str(N)
        D = len(s)
        res = self.id_identity
        
        for d in range(1, D):
            rem = d - 1
            for a in range(1, 10):
                block = self.full_block(self.digit_op_id[a], rem)
                res = self.compose_ids(res, block)
                
        first = int(s[0])
        rem = D - 1
        for a in range(1, first):
            block = self.full_block(self.digit_op_id[a], rem)
            res = self.compose_ids(res, block)
            
        if rem == 0:
            res = self.compose_ids(res, self.digit_op_id[first])
        else:
            suffix = int(s[1:])
            part = self.partial_block(self.digit_op_id[first], rem, suffix)
            res = self.compose_ids(res, part)
            
        return res

    def occ_and_state(self, N):
        op_id = self.range_operator(N)
        es, ac = self.ops[op_id]
        return ac[0], es[0]

    def digits_before(self, N):
        if N == 0:
            return 0
            
        s = str(N)
        D = len(s)
        total = 0
        for d in range(1, D):
            total += 9 * self.pow10[d - 1] * d
            
        total += (N - self.pow10[D - 1] + 1) * D
        return total

    def nth_occurrence_position(self, target_occurrence):
        hi = 1
        while self.occ_and_state(hi)[0] < target_occurrence:
            hi *= 2
            
        lo = 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self.occ_and_state(mid)[0] >= target_occurrence:
                hi = mid
            else:
                lo = mid + 1
                
        number = lo
        before_count, before_state = self.occ_and_state(number - 1)
        need_inside = target_occurrence - before_count
        
        prefix_digits = self.digits_before(number - 1)
        found_inside = 0
        state = before_state
        
        num_str = str(number)
        for i, ch in enumerate(num_str):
            d = int(ch)
            if self.out[state][d]:
                found_inside += 1
                if found_inside == need_inside:
                    end_pos = prefix_digits + i + 1
                    return end_pos - self.L + 1
            state = self.next_state[state][d]
            
        return 0

def solve(k_max=13):
    total = 0
    n = 1
    for k in range(1, k_max + 1):
        n *= 3
        engine = PatternEngine(str(n))
        total += engine.nth_occurrence_position(n)
        
    return str(total)

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

Java

import java.util.*;

public class Euler305 {

    static class Op {
        byte[] endState;
        long[] addCount;

        Op(byte[] endState, long[] addCount) {
            this.endState = endState;
            this.addCount = addCount;
        }

        @Override
        public boolean equals(Object obj) {
            Op other = (Op) obj;
            return Arrays.equals(endState, other.endState) && Arrays.equals(addCount, other.addCount);
        }

        @Override
        public int hashCode() {
            int h = 1;
            for (byte b : endState)
                h = 31 * h + b;
            for (long c : addCount)
                h = 31 * h + (int) (c ^ (c >>> 32));
            return h;
        }
    }

    static class PatternEngine {
        String pattern;
        int L;

        int[][] nextState;
        byte[][] out;

        List<Op> ops = new ArrayList<>();
        Map<Op, Integer> opToId = new HashMap<>();

        int idIdentity = -1;
        int[] digitOpId = new int[10];

        Map<Long, Integer> composeCache = new HashMap<>();
        Map<Long, Integer> appendCache = new HashMap<>();
        Map<Long, Integer> fullBlockCache = new HashMap<>();

        long[] pow10 = new long[21];

        PatternEngine(String pattern) {
            this.pattern = pattern;
            this.L = pattern.length();
            nextState = new int[L + 1][10];
            out = new byte[L + 1][10];

            buildAutomaton();
            buildDigitOperators();

            pow10[0] = 1;
            for (int i = 1; i <= 20; ++i) {
                pow10[i] = pow10[i - 1] * 10L;
            }
        }

        long makeKey(int a, int b) {
            return (((long) a) << 32) | (b & 0xFFFFFFFFL);
        }

        int internOp(Op op) {
            Integer id = opToId.get(op);
            if (id != null)
                return id;
            int newId = ops.size();
            ops.add(op);
            opToId.put(op, newId);
            return newId;
        }

        void buildAutomaton() {
            int[] pi = new int[L];
            for (int i = 1; i < L; ++i) {
                int j = pi[i - 1];
                while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                    j = pi[j - 1];
                }
                if (pattern.charAt(i) == pattern.charAt(j)) {
                    j++;
                }
                pi[i] = j;
            }

            for (int st = 0; st <= L; ++st) {
                for (int d = 0; d < 10; ++d) {
                    char c = (char) ('0' + d);
                    int j = st;
                    while (j > 0 && (j == L || pattern.charAt(j) != c)) {
                        j = pi[j - 1];
                    }
                    if (j < L && pattern.charAt(j) == c) {
                        j++;
                    }
                    if (j == L) {
                        out[st][d] = 1;
                        j = pi[L - 1];
                    }
                    nextState[st][d] = j;
                }
            }
        }

        void buildDigitOperators() {
            byte[] es = new byte[L + 1];
            long[] ac = new long[L + 1];
            for (int s = 0; s <= L; ++s)
                es[s] = (byte) s;
            idIdentity = internOp(new Op(es, ac));

            for (int d = 0; d < 10; ++d) {
                byte[] esd = new byte[L + 1];
                long[] acd = new long[L + 1];
                for (int s = 0; s <= L; ++s) {
                    esd[s] = (byte) nextState[s][d];
                    acd[s] = out[s][d];
                }
                digitOpId[d] = internOp(new Op(esd, acd));
            }
        }

        int composeIds(int idA, int idB) {
            long key = makeKey(idA, idB);
            Integer cached = composeCache.get(key);
            if (cached != null)
                return cached;

            Op A = ops.get(idA);
            Op B = ops.get(idB);

            byte[] CEs = new byte[L + 1];
            long[] CAc = new long[L + 1];

            for (int s = 0; s <= L; ++s) {
                int mid = A.endState[s];
                CEs[s] = B.endState[mid];
                CAc[s] = A.addCount[s] + B.addCount[mid];
            }

            int id = internOp(new Op(CEs, CAc));
            composeCache.put(key, id);
            return id;
        }

        int appendDigit(int opId, int d) {
            long key = makeKey(opId, d);
            Integer cached = appendCache.get(key);
            if (cached != null)
                return cached;
            int id = composeIds(opId, digitOpId[d]);
            appendCache.put(key, id);
            return id;
        }

        int fullBlock(int prefixOp, int remDigits) {
            long key = makeKey(prefixOp, remDigits);
            Integer cached = fullBlockCache.get(key);
            if (cached != null)
                return cached;

            int id;
            if (remDigits == 0) {
                id = prefixOp;
            } else {
                int res = idIdentity;
                for (int d = 0; d < 10; ++d) {
                    int child = fullBlock(appendDigit(prefixOp, d), remDigits - 1);
                    res = composeIds(res, child);
                }
                id = res;
            }
            fullBlockCache.put(key, id);
            return id;
        }

        int partialBlock(int prefixOp, int remDigits, long upperSuffix) {
            if (remDigits == 0)
                return prefixOp;

            long base = pow10[remDigits - 1];
            int first = (int) (upperSuffix / base);
            long rest = upperSuffix % base;

            int res = idIdentity;
            for (int d = 0; d < first; ++d) {
                int child = fullBlock(appendDigit(prefixOp, d), remDigits - 1);
                res = composeIds(res, child);
            }

            int last = partialBlock(appendDigit(prefixOp, first), remDigits - 1, rest);
            res = composeIds(res, last);
            return res;
        }

        int rangeOperator(long N) {
            if (N == 0)
                return idIdentity;

            String s = String.valueOf(N);
            int D = s.length();
            int res = idIdentity;

            for (int d = 1; d < D; ++d) {
                int rem = d - 1;
                for (int a = 1; a < 10; ++a) {
                    int block = fullBlock(digitOpId[a], rem);
                    res = composeIds(res, block);
                }
            }

            int first = s.charAt(0) - '0';
            int rem = D - 1;
            for (int a = 1; a < first; ++a) {
                int block = fullBlock(digitOpId[a], rem);
                res = composeIds(res, block);
            }

            if (rem == 0) {
                res = composeIds(res, digitOpId[first]);
            } else {
                long suffix = Long.parseLong(s.substring(1));
                int part = partialBlock(digitOpId[first], rem, suffix);
                res = composeIds(res, part);
            }

            return res;
        }

        long[] occAndState(long N) {
            int opId = rangeOperator(N);
            Op op = ops.get(opId);
            return new long[] { op.addCount[0], op.endState[0] };
        }

        long digitsBefore(long N) {
            if (N == 0)
                return 0;

            String s = String.valueOf(N);
            int D = s.length();

            long total = 0;
            for (int d = 1; d < D; ++d) {
                total += 9L * pow10[d - 1] * d;
            }

            total += (N - pow10[D - 1] + 1) * D;
            return total;
        }

        long nthOccurrencePosition(long targetOccurrence) {
            long hi = 1;
            while (occAndState(hi)[0] < targetOccurrence) {
                hi *= 2;
            }

            long lo = 1;
            while (lo < hi) {
                long mid = lo + (hi - lo) / 2;
                if (occAndState(mid)[0] >= targetOccurrence) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }

            long number = lo;
            long[] before = occAndState(number - 1);
            long beforeCount = before[0];
            int beforeState = (int) before[1];

            long needInside = targetOccurrence - beforeCount;
            long prefixDigits = digitsBefore(number - 1);

            long foundInside = 0;
            int state = beforeState;
            String numStr = String.valueOf(number);

            for (int i = 0; i < numStr.length(); ++i) {
                int d = numStr.charAt(i) - '0';
                if (out[state][d] != 0) {
                    foundInside++;
                    if (foundInside == needInside) {
                        long endPos = prefixDigits + i + 1;
                        return endPos - L + 1;
                    }
                }
                state = nextState[state][d];
            }

            return 0;
        }
    }

    public static String solve() {
        int kMax = 13;
        long sum = 0;
        long n = 1;
        for (int k = 1; k <= kMax; ++k) {
            n *= 3;
            PatternEngine engine = new PatternEngine(String.valueOf(n));
            sum += engine.nthOccurrencePosition(n);
        }
        return String.valueOf(sum);
    }

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