Problem 230: Fibonacci Words

Project Euler Problem 230 Solution

EulerSolve provides an optimized solution for Project Euler Problem 230, Fibonacci Words, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We start with two fixed 100-digit strings $A$ and $B$. From them we define Fibonacci words by $$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3),$$ where juxtaposition means concatenation. The words grow extremely quickly, so the task is not to build them explicitly, but to recover individual digits at carefully chosen positions. For a positive integer $t$, let $L_k=|F_k|$ and let $k(t)$ be the smallest index such that $L_{k(t)}\ge t$. The queried digit $D_{A,B}(t)$ is the $t$-th digit of that first Fibonacci word long enough to contain position $t$. The required answer is $$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big).$$ The largest queried position is $450\cdot 7^{17}=104683731294243150$, so any method that tries to construct the word itself is hopeless. The solution works entirely with lengths and index transformations. Mathematical Approach The key observation is that a position inside a concatenated word can be traced back to exactly one position in a smaller word. Repeating that idea turns a gigantic string problem into a short descent through a Fibonacci-style length table. The length sequence is Fibonacci as well If $L_k=|F_k|$, then concatenation immediately gives $$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3).$$ So the lengths follow the same recurrence as Fibonacci numbers....

Detailed mathematical approach

Problem Summary

For two strings of digits $A$ and $B$, the sequence $F_{A,B}$ starts with $A$ and $B$, and every further term is the concatenation of the two terms before it, the older one first: $A,B,AB,BAB,ABBAB,\dots$ The value $D_{A,B}(n)$ is the $n$-th digit of the first term that has at least $n$ digits. In the example of the statement, $A=1415926535$ and $B=8979323846$ are the first ten and the next ten digits of $\pi$ after the decimal point; the fifth term is the first one with at least $35$ digits, and its $35$th digit gives $D_{A,B}(35)=9$. For the actual task, $A$ consists of the first $100$ digits of $\pi$ after the decimal point and $B$ of the next $100$, and we must compute ^[1]

$$\begin{aligned}S&=\sum_{n=0}^{17}10^n\,D_{A,B}(p_n),\\p_n&=(127+19n)\cdot7^n.\end{aligned}$$

Each $D_{A,B}(p_n)$ is a single digit, so the weight $10^n$ puts it in the $n$-th decimal place of $S$, counting the units digit as place $0$: $S$ is simply the eighteen digits for $n=17,16,\dots,0$ written side by side. From now on we write $D(n)$ for $D_{A,B}(n)$.

The whole solution in one sentence: every term after the first two is a shorter term followed by another shorter term, so a position in a gigantic term can be traced back one term at a time, using nothing but the lengths of the terms, which are $100$ times the Fibonacci numbers, until it lands in $A$ or $B$, where the digit is read off.

Mathematical Approach

The largest position is $p_{17}=104683731294243150$, about $1.05\times10^{17}$. It lies in a term with about $1.3\times10^{17}$ digits, some $130$ petabytes at one byte per digit, far too much to store, so the programs never build any term. We study the structure on the small example of the statement, where every claim can be checked by hand, and then work with the lengths of the terms alone.

1. Small terms

Write $F_1=A$, $F_2=B$ and $F_k=F_{k-2}F_{k-1}$ for $k\ge3$, where two words written side by side are concatenated. With the ten-digit seeds of the example:

$F_3=AB=14159265358979323846$ has $20$ digits;
$F_4=BAB$ has $30$ digits and begins with $F_2=8979323846$;
$F_5=ABBAB$ has $50$ digits and begins with $F_3$.

Two patterns appear: each length is the sum of the two lengths before it, and each term begins with the term two places earlier. The next terms have $80$, $130$, $210$ and $340$ digits.

2. The lengths are Fibonacci numbers

Let $L_k$ be the number of digits of $F_k$. The length of a concatenation is the sum of the lengths of its parts, so $L_k=L_{k-2}+L_{k-1}$ for $k\ge3$. This is the rule of the Fibonacci numbers, which we write in lower case, $f_0=0$, $f_1=1$ and $f_k=f_{k-1}+f_{k-2}$, to keep $F_k$ for the words. ^[3] If both seeds have $\ell$ digits, then $L_1=\ell f_1$ and $L_2=\ell f_2$, and since both sides obey the same rule, induction on $k$ gives $L_k=\ell f_k$ for every $k\ge1$. The example has $L_k=10f_k$, and the real problem has $L_k=100f_k$, that is, $100,100,200,300,500,800,\dots$

Binet's formula expresses $f_k$ through the golden ratio $\varphi=(1+\sqrt5)/2\approx1.618$ and shows that $f_k$ is the integer nearest to $\varphi^k/\sqrt5$. ^[3] The lengths therefore grow by a factor of about $1.618$ per term, and fewer than $80$ terms take them past $10^{17}$.

3. The first term that is long enough

Let $k(n)$ be the index of the first term with at least $n$ digits, so that $D(n)$ is the $n$-th digit of $F_{k(n)}$. Here $L_1=L_2=100$, and from $k=3$ on $L_k=L_{k-1}+L_{k-2}\gt L_{k-1}$. Hence $k(n)=1$ for $n\le100$, while for $n\gt100$ it is the unique $k\ge3$ with $L_{k-1}\lt n\le L_k$. By Section 2, $k(n)$ is close to $\log_\varphi(\sqrt5\,n/100)$. For $n=p_{17}$ this estimate is $73.5$, and indeed $L_{73}\approx8.07\times10^{16}$ is smaller than $p_{17}$ while $L_{74}\approx1.30\times10^{17}$ is not, so $k(p_{17})=74$.

4. Why the first term matters

Since $F_{k+2}=F_kF_{k+1}$, every term is a prefix, an initial segment, of the term two places later, and therefore of all later terms of the same parity: the $n$-th digit is the same in $F_{k(n)}$, $F_{k(n)+2}$, $F_{k(n)+4}$ and so on. The terms of odd index begin with $A$, however, and those of even index with $B$, so neighbouring terms can disagree. In the example, the first term with at least $12$ digits is $F_3=AB$, and $D(12)=9$ is the second digit of $B$; the $12$th digit of $F_4=BAB$ is $4$, the second digit of $A$. In the same way $D(n)$ is a digit of $A$ for $n\le100$, although $B$ is just as long.

5. The descent rule

Write $d(k,t)$ for the $t$-th digit of $F_k$, where $1\le t\le L_k$. The key claim is that for $k\ge3$

$$d(k,t)=\begin{cases}d(k-2,\,t),&t\le L_{k-2},\\d(k-1,\,t-L_{k-2}),&t\gt L_{k-2}.\end{cases}$$

Proof: $F_k=F_{k-2}F_{k-1}$ consists of the $L_{k-2}$ digits of $F_{k-2}$ followed by the $L_{k-1}$ digits of $F_{k-1}$. Position $t\le L_{k-2}$ therefore holds digit $t$ of $F_{k-2}$, and position $t\gt L_{k-2}$ holds digit $t-L_{k-2}$ of $F_{k-1}$, a valid position because $1\le t-L_{k-2}\le L_k-L_{k-2}=L_{k-1}$. We call the first case a left step and the second a right step.

6. The walk ends quickly

Start with $(k,t)=(k(n),n)$. The claim that $D(n)=d(k,t)$ with $1\le t\le L_k$ holds at the start, and by Section 5 every step keeps it true while lowering $k$ by $1$ or $2$. As soon as $k\le2$ the walk stops, and $D(n)$ is digit $t$ of $A$ if $k=1$ and of $B$ if $k=2$. At each step exactly one case applies, so there is a single path and nothing to search. If $k(n)=1$ there is no step at all. Otherwise $k(n)\ge3$, steps are taken only from $k\ge3$ and each lowers $k$ by at least $1$, so there are at most $k(n)-2$ of them, at most $72$ for $p_{17}$. With $k=k(n)\ge3$, the first step is always a right step, because $n\gt L_{k-1}\ge L_{k-2}$; when $k\ge4$ the second one is too, because $n-L_{k-2}\gt L_{k-1}-L_{k-2}=L_{k-3}$.

7. Worked example: the checkpoint of the statement

With the example seeds, $L_4=30\lt35\le50=L_5$, so $k(35)=5$, and the walk is:

$(5,35)$: $35\gt L_3=20$, a right step to $(4,15)$;
$(4,15)$: $15\gt L_2=10$, a right step to $(3,5)$;
$(3,5)$: $5\le L_1=10$, a left step to $(1,5)$.

The fifth digit of $A=1415926535$ is $9$, the value $D(35)=9$ of the statement.

8. Worked example: a longer walk

For $n=250$, $L_8=210\lt250\le340=L_9$ gives $k(250)=9$, and comparing $t$ with $L_{k-2}$ at each step produces

$$\begin{aligned}(9,250)&\to(8,120)\to(7,40)\\&\to(5,40)\to(4,20)\\&\to(3,10)\to(1,10).\end{aligned}$$

The right steps come from $250\gt130$, $120\gt80$, $40\gt20$ and $20\gt10$, the left steps from $40\le50$ and $10\le10$. So $D(250)$ is the tenth digit of $A$, which is $5$, and building the $340$ digits of $F_9$ confirms that its $250$th digit is $5$. This walk takes $6$ of the at most $k(250)-2=7$ steps.

9. Whole copies of the seeds

Replace $A$ by the letter $\mathtt a$ and $B$ by the letter $\mathtt b$. The words $W_1=\mathtt a$, $W_2=\mathtt b$ and $W_k=W_{k-2}W_{k-1}$ record which seed is copied where: $F_k$ is $W_k$ with every $\mathtt a$ replaced by $A$ and every $\mathtt b$ by $B$, as in $W_5=\mathtt{abbab}$ and $F_5=ABBAB$. The induction of Section 2 shows that $W_k$ has $f_{k-2}$ letters $\mathtt a$ and $f_{k-1}$ letters $\mathtt b$ for $k\ge2$. As both seeds have $100$ digits, the copies fill the blocks of positions $1$ to $100$, $101$ to $200$, and so on, and every right step subtracts $L_{k-2}=100f_{k-2}$, a multiple of $100$. The walk thus never changes $t$ modulo $100$ and ends at the offset $r=((n-1)\bmod 100)+1$ of $n$ inside its block, where $a\bmod 100$ is the remainder of $a$ on division by $100$: position $100$ has offset $100$ and position $101$ has offset $1$. All the walk decides is whether this block holds $A$ or $B$. In the example, with blocks of ten, the walks for $35$ and $250$ end at the offsets $5$ and $10$.

10. A closed formula from the Fibonacci word

The classical Fibonacci word concatenates in the other order: $S_0=\mathtt0$, $S_1=\mathtt{01}$ and $S_j=S_{j-1}S_{j-2}$. The word $S_j$ has $f_{j+2}$ letters and is a prefix of the infinite Fibonacci word $\mathtt{0100101001001}\dots$, whose $m$-th letter, counted from $1$, is ^[2]

$$s(m)=2+\lfloor m\varphi\rfloor-\lfloor (m+1)\varphi\rfloor.$$

Here $\lfloor x\rfloor$ is the largest integer not above $x$; for instance $\lfloor\varphi\rfloor=1$ and $\lfloor2\varphi\rfloor=3$ give $s(1)=0$, the first letter. Reading a word backwards reverses the order of its parts, so the mirror images $\overline{S_j}$ obey $\overline{S_j}=\overline{S_{j-2}}\,\overline{S_{j-1}}$, our rule. They start with $\overline{S_0}=\mathtt0$ and $\overline{S_1}=\mathtt{10}$, which are $W_2=\mathtt b$ and $W_3=\mathtt{ab}$ with $\mathtt a$ written as $\mathtt1$ and $\mathtt b$ as $\mathtt0$, so by induction $W_k$ is the mirror image of $S_{k-2}$ for every $k\ge2$. Hence block $j$ of $F_k$, counted from the left, holds $A$ if $s(f_k+1-j)=1$ and $B$ if $s(f_k+1-j)=0$. For $n\gt100$ this gives $D(n)$ without a walk: take $k=k(n)$, the block $j=\lceil n/100\rceil$, where $\lceil x\rceil$ is the smallest integer not below $x$, and the digit at offset $r$ of its seed. For $n=35$ in the example, with blocks of ten, $k=5$, $j=4$, $s(2)=2+3-4=1$ and $r=5$ give $A$ and the digit $9$ once more.

The floors must be exact. For $n\gt100$ we have $n\gt L_{k-1}$, so $j\gt f_{k-1}$ and $m=f_k+1-j\le f_{k-2}$; for the eighteen positions $m$ stays below $2.6\times10^{14}$. Even much smaller $m$ can defeat a double, because $\varphi$ times a Fibonacci number lies extremely close to an integer: $f_{i+1}-\varphi f_i=\psi^i$ with $\psi=(1-\sqrt5)/2$. ^[3] For $m=f_{40}=102334155$ the exact floor of $m\varphi$ is $165580140$, but the double-precision product rounds to $165580141$. Since $m\sqrt5$ is irrational, $m\varphi=(m+m\sqrt5)/2$ lies strictly between $(m+q)/2$ and $(m+q+1)/2$ with $q=\lfloor\sqrt{5m^2}\rfloor$. No integer lies strictly between these two neighbouring multiples of $\tfrac12$, so

$$\lfloor m\varphi\rfloor=\Bigl\lfloor\frac{m+\lfloor\sqrt{5m^2}\rfloor}{2}\Bigr\rfloor,$$

which needs only an integer square root. The published programs use the walk, not this formula; it serves as an independent check below.

11. The eighteen positions

The positions begin with $p_0=127$, $p_1=1022$ and $p_2=8085$, and each is between $7.30$ and $8.05$ times the one before, a little more than $\varphi^4\approx6.85$. Accordingly the index $k(p_n)$ grows by $4$ or $5$ from one position to the next, up to $k(p_{17})=74$. All positions exceed $100$, so $F_1$ is never the first term long enough. Every length and position involved is at most $L_{74}\approx1.3\times10^{17}$, far below $2^{63}\approx9.2\times10^{18}$, so 64-bit integers hold them all. The sum itself satisfies $S\le9\,(1+10+\dots+10^{17})=10^{18}-1$, which fits in a signed 64-bit integer as well.

How the Code Works

The C++ program ^[8] keeps the seeds in the constants A100 and B100. Its main first calls parse_arguments, which accepts only --skip-checkpoints and ends the program with exit code $1$ on any other argument. Unless that option is given, run_checkpoints then requires digit_at to return $9$ for the example seeds of the statement at $n=35$, and ends the program with exit code $2$ otherwise. Finally main prints the result of solve.

solve runs over $n=0,\dots,17$. It forms the position index as $127+19n$ multiplied $n$ times by $7$, in the 64-bit unsigned type u64, calls digit_at(A100, B100, index) and adds the digit times pow10, which holds $10^n$, to answer. Both of these use unsigned __int128, a GCC extension that Clang accepts too, ^[5] although by Section 11 a 64-bit type would do. The standard output stream has no operator for this type, so to_string_u128 produces the decimal digits by repeated division by $10$.

digit_at(A, B, n) carries out Sections 3 to 6. It starts the vector len as $\{0,|A|,|B|\}$, where the extra $0$ at index $0$ makes len[k] equal to $L_k$, and appends len[m - 1] + len[m] while the last entry is smaller than n. Then k is the index of the last entry, and the loop while (k > 2) makes the steps of Section 5: if n <= len[k - 2] it lowers k by $2$, otherwise it subtracts len[k - 2] from n and lowers k by $1$. Positions count from $1$ but strings from $0$, so the function returns the character A[n - 1] or B[n - 1] minus '0'.

Because the table starts with both seed lengths, k starts at the first index $k\ge2$ with $L_k\ge n$, not $k\ge1$. For $n\le100$, or $n\le10$ with the example seeds, the function therefore returns the $n$-th digit of $B$ where Section 3 asks for the $n$-th digit of $A$; with the example seeds it returns $8$ for $n=1$ instead of $D(1)=1$. This never matters here: every $p_n$ exceeds $100$ (Section 11), and for $n\gt100$ the first index $k\ge2$ with $L_k\ge n$ is exactly $k(n)$.

The Python file has the same functions digit_at and solve, with integers of unlimited precision, ^[6] and the Java file has digitAt and solve; neither has command-line options or the checkpoint. Java keeps the lengths in a List<Long> and the positions in long, whose range up to $2^{63}-1$ covers Section 11, and it accumulates the sum in a BigInteger. ^[7]

Complexity and Verification

For a position $n\gt100$, as all eighteen are, a query builds a table of $k(n)+1$ entries and makes at most $k(n)-2$ steps, each one comparison and at most one subtraction. As $k(n)$ grows like $\log_\varphi n$ (Section 3), a query makes $O(\log n)$ operations on integers that fit in 64 bits here and stores $O(\log n)$ of them, so it takes $O(\log n)$ time and memory. The programs rebuild the table for each of the $18$ positions; altogether they append $659$ entries, make $499$ steps and multiply by $7$ a total of $153$ times. On our machine all three finish within a few hundredths of a second, mostly start-up time.

The C++ program checks $D(35)=9$ from the statement on every run unless --skip-checkpoints is given. For this article we also ran the following checks, which are not part of the published programs:

The seeds in all three files are the digits $1$ to $200$ of $\pi$ after the decimal point, recomputed exactly with Machin's formula, ^[4] and the example seeds are its digits $1$ to $20$.
We built the terms explicitly, up to $F_{30}$ with $83\,204\,000$ digits for the real seeds and up to $F_{32}$ with $21\,783\,090$ digits for the example seeds. The published C++ function agrees with the definition at every position from $101$ to $83\,204\,000$, and from $11$ to $21\,783\,090$ for the example. At the smaller positions it returns the digit of $B$, as described above, which differs from the correct digit of $A$ at $84$ of the $100$ positions and at $9$ of the $10$. The Python and Java functions behave in exactly the same way at every position up to $L_{24}=4\,636\,800$ for the real seeds and $L_{28}=3\,178\,110$ for the example seeds.
The closed formula of Section 10 agrees with the explicit terms at every position up to $83\,204\,000$ for the real seeds and $21\,783\,090$ for the example seeds, and with the three published functions at $20\,000$ random positions up to $10^{18}$ and at the eighteen positions $p_n$, for both pairs of seeds.
The three programs print the same number, with the C++ compiled by GCC and by Clang.

Footnotes and References

The references below supply the background facts used above; the walks, the closed formula for these words, the counts and the checks were worked out for this article.

Project Euler 230 — Fibonacci Words. The official statement defines the sequence A, B, AB, BAB, ABBAB, … in which each term is the concatenation of the previous two, and D(n), the n-th digit of the first term with at least n digits. It gives D(35) = 9 for ten-digit example seeds and asks for the sum of 10ⁿ · D((127 + 19n) · 7ⁿ) over n = 0, …, 17, with A made of the first 100 digits of π after the decimal point and B of the next 100.
Wikipedia — Fibonacci word. The article defines S₀ = 0, S₁ = 01 and Sₙ = Sₙ₋₁Sₙ₋₂, states that Sₙ has Fₙ₊₂ letters and that the infinite Fibonacci word has every Sₙ as a prefix, and gives its n-th digit as 2 + ⌊nφ⌋ − ⌊(n + 1)φ⌋, the formula used in Section 10.
Wikipedia — Fibonacci sequence. The recurrence with F₀ = 0 and F₁ = 1, Binet's formula in terms of the golden ratio φ and its conjugate ψ = (1 − √5)/2, and its consequence that Fₙ is the integer nearest to φⁿ/√5, so that the numbers grow exponentially and the index of a given size can be found with a logarithm to base φ, as in Sections 2 and 3. The identity ψⁿ = Fₙψ + Fₙ₋₁ from the section on powers of φ and ψ gives Fₙ₊₁ − φFₙ = ψⁿ, used in Section 10.
OEIS A000796 — Decimal expansion of Pi. The digits 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, …, with a table of 20000 terms. For the check of the seeds the digits were recomputed with Machin's formula π/4 = 4 arctan(1/5) − arctan(1/239).
GCC manual — 128-bit Integers. GCC provides __int128 and unsigned __int128 on targets with an integer mode wide enough for 128 bits; the C++ program accumulates the sum in the unsigned type.
Python — Numeric types. The documentation states that Python integers have unlimited precision, so the Python program needs no special type for the positions or the sum.
The Java Language Specification, Java SE 17 — §4.2.1. The type long holds the integers from −2⁶³ to 2⁶³ − 1. The class BigInteger provides immutable arbitrary-precision integers, which the Java program uses for the sum.
C++ — Euler230.cpp. The linked immutable C++ revision contains parse_arguments, digit_at, solve, run_checkpoints and to_string_u128. It is the implementation record for this article.

Problem 230 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    bool run_checkpoints = true;
};

const std::string A100 =
    "14159265358979323846264338327950288419716939937510"
    "58209749445923078164062862089986280348253421170679";
const std::string B100 =
    "82148086513282306647093844609550582231725359408128"
    "48111745028410270193852110555964462294895493038196";

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

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

int digit_at(const std::string& A, const std::string& B, u64 n) {
    std::vector<u64> len = {0ULL, static_cast<u64>(A.size()), static_cast<u64>(B.size())};
    while (len.back() < n) {
        const int m = static_cast<int>(len.size()) - 1;
        len.push_back(len[static_cast<std::size_t>(m - 1)] + len[static_cast<std::size_t>(m)]);
    }

    int k = static_cast<int>(len.size()) - 1;
    while (k > 2) {
        if (n <= len[static_cast<std::size_t>(k - 2)]) {
            k -= 2;
        } else {
            n -= len[static_cast<std::size_t>(k - 2)];
            k -= 1;
        }
    }

    return (k == 1) ? (A[static_cast<std::size_t>(n - 1)] - '0')
                    : (B[static_cast<std::size_t>(n - 1)] - '0');
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

u128 solve() {
    u128 answer = 0;
    u128 pow10 = 1;

    for (int n = 0; n <= 17; ++n) {
        u64 index = static_cast<u64>(127 + 19 * n);
        for (int i = 0; i < n; ++i) {
            index *= 7ULL;
        }
        const int digit = digit_at(A100, B100, index);
        answer += pow10 * static_cast<u128>(digit);
        pow10 *= 10U;
    }

    return answer;
}

bool run_checkpoints() {
    const std::string A = "1415926535";
    const std::string B = "8979323846";
    if (digit_at(A, B, 35ULL) != 9) {
        std::cerr << "Checkpoint failed for statement example" << '\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 << to_string_u128(solve()) << '\n';
    return 0;
}

Python

A100 = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
B100 = "8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"

def digit_at(A, B, n):
    lens = [0, len(A), len(B)]
    while lens[-1] < n:
        lens.append(lens[-2] + lens[-1])
        
    k = len(lens) - 1
    while k > 2:
        if n <= lens[k - 2]:
            k -= 2
        else:
            n -= lens[k - 2]
            k -= 1
            
    if k == 1:
        return int(A[n - 1])
    else:
        return int(B[n - 1])

def solve():
    answer = 0
    pow10 = 1
    
    for n in range(18):
        index = 127 + 19 * n
        for _ in range(n):
            index *= 7
            
        digit = digit_at(A100, B100, index)
        answer += pow10 * digit
        pow10 *= 10
        
    return str(answer)

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

Java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Euler230 {
    static final String A100 = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
    static final String B100 = "8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196";

    static int digitAt(String a, String b, long n) {
        List<Long> len = new ArrayList<>();
        len.add(0L);
        len.add((long) a.length());
        len.add((long) b.length());

        while (len.get(len.size() - 1) < n) {
            int m = len.size() - 1;
            len.add(len.get(m - 1) + len.get(m));
        }

        int k = len.size() - 1;
        while (k > 2) {
            if (n <= len.get(k - 2)) {
                k -= 2;
            } else {
                n -= len.get(k - 2);
                k -= 1;
            }
        }

        if (k == 1) {
            return a.charAt((int) (n - 1)) - '0';
        } else {
            return b.charAt((int) (n - 1)) - '0';
        }
    }

    public static String solve() {
        BigInteger answer = BigInteger.ZERO;
        BigInteger pow10 = BigInteger.ONE;

        for (int n = 0; n <= 17; ++n) {
            long index = 127 + 19L * n;
            for (int i = 0; i < n; ++i) {
                index *= 7L;
            }
            int digit = digitAt(A100, B100, index);
            answer = answer.add(pow10.multiply(BigInteger.valueOf(digit)));
            pow10 = pow10.multiply(BigInteger.TEN);
        }

        return answer.toString();
    }

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