Detailed mathematical approach

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. If \(f_1=f_2=1\) and \(f_k=f_{k-2}+f_{k-1}\), then

$L_k=100f_k.$

This matters because the algorithm never needs the words themselves. It only needs enough length values to know which block contains the target position. Since Fibonacci growth is exponential in \(k\), the largest required index is already covered by \(F_{74}\), so only a few dozen length values are needed.

The descent rule for one digit

Suppose we want the \(t\)-th digit of \(F_k\) with \(k\ge 3\). Because

$F_k=F_{k-2}F_{k-1},$

the first \(L_{k-2}\) positions of \(F_k\) come from \(F_{k-2}\), and the remaining \(L_{k-1}\) positions come from \(F_{k-1}\). Therefore the desired digit satisfies

$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$

This is the whole mathematics of the problem. One comparison with \(L_{k-2}\) tells us whether the target digit sits in the left block or the right block, and in the right-block case the local position is obtained by subtracting the entire left-block length.

Invariant and termination

Start from \(k=k(t)\), the smallest index with \(L_k\ge t\). At every stage, the state \((k,t)\) means: “the answer is the \(t\)-th digit of \(F_k\).” The descent rule preserves this statement exactly while making \(k\) smaller.

If the position lies in the left block, we replace \((k,t)\) by \((k-2,t)\). If it lies in the right block, we replace \((k,t)\) by \((k-1,t-L_{k-2})\). Either way, the word index drops, so after finitely many steps we must land at \(k=1\) or \(k=2\). At that point the answer is read directly from the seed string \(A\) or \(B\).

No branching tree is explored. For each query there is exactly one valid path downward through the concatenation structure.

Worked example: the statement checkpoint \(D_{A,B}(35)=9\)

Using the shorter seeds from the problem statement,

$A=1415926535,\qquad B=8979323846,$

the lengths are \(10,10,20,30,50,\dots\). The first Fibonacci word long enough to contain position \(35\) is \(F_5\), because \(L_4=30<35\le 50=L_5\).

Now apply the descent rule:

$ (5,35)\to(4,15)\to(3,5)\to(1,5). $

The reasoning is

$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10.$

So the required digit is the 5th digit of \(A\), namely \(9\). This example shows exactly how an apparently large position collapses to a direct lookup in a base word.

The final sum needs only eighteen queries

For the actual problem, define

$p_n=(127+19n)7^n\qquad (0\le n\le 17).$

Each \(p_n\) is handled independently: find \(D_{A,B}(p_n)\) by descent, then place that digit at decimal weight \(10^n\). The final answer is therefore assembled as

$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17}).$

The hard-looking global problem is thus just eighteen small position queries plus a decimal accumulation.

How the Code Works

Building the length table

The C++, Python, and Java implementations store the two seed strings and generate the length sequence \(L_k\) iteratively. For each query they extend that table until the last length is at least the requested position. Because the largest query is reached by \(F_{74}\), this table remains tiny.

Descending to a base string

Once the relevant \(k\) is known, the implementation loops while \(k>2\). At each iteration it compares the current position with \(L_{k-2}\). A position in the left block keeps the same local index and jumps to \(F_{k-2}\); a position in the right block subtracts \(L_{k-2}\) and jumps to \(F_{k-1}\). When the loop reaches \(F_1\) or \(F_2\), the code reads the corresponding digit directly from \(A\) or \(B\).

The only indexing subtlety is that the mathematics is 1-indexed, while programming strings are 0-indexed. So the final character access uses position \(t-1\) inside the chosen seed.

Assembling the decimal value

After each digit extraction, the implementation adds it to a running total with weight \(10^n\). The three language versions follow the same sequence of eighteen queries and the same recurrence logic; they differ only in the numeric container used for the final accumulator.

Complexity Analysis

If \(k(t)\) is the smallest index with \(L_{k(t)}\ge t\), then a single query performs one descent step per level until it reaches a seed. Its running time is therefore \(O(k(t))\). Since \(L_k=100f_k\) and Fibonacci numbers satisfy \(f_k=\Theta(\varphi^k)\), this is \(O(\log t)\).

For Problem 230 there are only 18 queries, and even the largest one starts at \(k=74\). So the full computation is only a few hundred simple integer operations. Memory usage is \(O(k_{\max})\) for the length table, which here means only a few dozen 64-bit values.

Footnotes and References

1. Project Euler Problem 230: https://projecteuler.net/problem=230
2. Fibonacci word: Wikipedia - Fibonacci word
3. Fibonacci number: Wikipedia - Fibonacci number
4. Concatenation: Wikipedia - Concatenation
5. Recurrence relation: Wikipedia - Recurrence relation