Problem 230: Fibonacci Words

Mathematical Foundation

Theorem 1 (Length Recurrence). The lengths $L(n) = |F(n)|$ satisfy $L(1) = L(2) = 100$ and $L(n) = L(n-1) + L(n-2)$ for $n \geq 3$.

Proof. $F(n) = F(n-2) \cdot F(n-1)$ is the concatenation of $F(n-2)$ and $F(n-1)$, so $|F(n)| = |F(n-2)| + |F(n-1)|$. $\square$

Theorem 2 (Exponential Growth). $L(n) = \Theta(\phi^n)$ where $\phi = (1 + \sqrt{5})/2$ is the golden ratio. Specifically,

Proof. The recurrence $L(n) = L(n-1) + L(n-2)$ with $L(1) = L(2) = 100$ has characteristic equation $x^2 = x + 1$ with roots $\phi$ and $-1/\phi$. The closed form follows from solving the initial conditions. Asymptotically, the $(-1/\phi)^n$ terms vanish, giving $L(n) = \Theta(\phi^n)$. $\square$

Lemma 1 (Sufficient Depth). The largest position queried is $k_{17} = (127 + 19 \cdot 17) \cdot 7^{17} = 450 \cdot 7^{17} \approx 1.05 \times 10^{17}$. We need $L(n) \geq k_{17}$, which is satisfied for $n \approx 85$.

Proof. $L(n) \approx 100 \cdot \phi^{n-2} / (\phi + 1)$. Solving $L(n) \geq 10^{17}$ gives $n \geq \lceil 2 + \log_\phi(10^{17} \cdot (\phi+1)/100) \rceil \approx 85$. $\square$

Theorem 3 (Recursive Digit Lookup). To find the $k$-th digit of $F(n)$ where $n$ is the smallest index with $L(n) \geq k$:

• If $n = 1$: return $A[k]$.
• If $n = 2$: return $B[k]$.
• If $k \leq L(n-2)$: the digit is in $F(n-2)$; recurse with $(n-2, k)$.
• If $k > L(n-2)$: the digit is in $F(n-1)$; recurse with $(n-1, k - L(n-2))$.

Proof. Since $F(n) = F(n-2) \cdot F(n-1)$, the first $L(n-2)$ characters are from $F(n-2)$ and the remaining $L(n-1)$ characters are from $F(n-1)$. The recursion correctly decomposes the position. Termination is guaranteed since at each step we reduce $n$ by at least 1 (and $k$ stays bounded by $L(n)$, which decreases exponentially). $\square$

Lemma 2 (Lookup Complexity). Each digit lookup performs $O(n) = O(\log_\phi k)$ recursive steps.

Proof. At each step, $n$ decreases by 1 or 2. Since we start at $n \approx \log_\phi k$ and reach $n \in \{1, 2\}$, the number of steps is $O(\log_\phi k)$. $\square$

Editorial

F(1) = A (100 digits of pi), F(2) = B (next 100 digits of pi) F(n) = F(n-2) . F(n-1) (concatenation, older part first) Sequence: A, B, AB, BAB, ABBAB, … Find sum of D((127+19n)*7^n) * 10^n for n = 0 to 17, where D(k) is the k-th digit of the infinite Fibonacci word. We precompute Fibonacci lengths. We then find smallest n with L[n] >= k. Finally, recurse.

Pseudocode

Precompute Fibonacci lengths
Find smallest n with L[n] >= k
Recurse
else

Complexity Analysis

• Time: $O(18 \cdot \log_\phi k_{\max}) = O(18 \times 85) = O(1530)$. Essentially instantaneous.
• Space: $O(\log_\phi k_{\max}) = O(85)$ for the precomputed lengths.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Problem 230: Fibonacci Words
    // F(1) = A (100 digits of pi), F(2) = B (next 100 digits of pi)
    // F(n) = F(n-2) . F(n-1) (concatenation, older first)
    // Find sum of D((127+19n)*7^n) * 10^n for n=0..17

    string A = "1415926535897932384626433832795028841971"
               "6939937510582097494459230781640628620899"
               "86280348253421170679";
    string B = "8214808651328230664709384460955058223172"
               "5359408128481117450284102701938521105559"
               "64462294895493038196";

    // Use __int128 for large positions
    typedef __int128 lll;
    const int MAXN = 200;
    lll L[MAXN + 1];
    L[1] = L[2] = 100;
    lll cap = (lll)1e25;
    for (int i = 3; i <= MAXN; i++) {
        L[i] = L[i-1] + L[i-2];
        if (L[i] > cap) {
            for (int j = i + 1; j <= MAXN; j++) L[j] = cap;
            break;
        }
    }

    // Compute 7^n using __int128
    auto power7 = [](int n) -> lll {
        lll result = 1;
        for (int i = 0; i < n; i++) result *= 7;
        return result;
    };

    // Find the k-th digit (1-indexed) of the Fibonacci word
    // F(n) = F(n-2) . F(n-1): first L[n-2] chars from F(n-2), rest from F(n-1)
    auto find_digit = [&](lll k) -> int {
        int n = 1;
        while (L[n] < k) n++;
        while (n > 2) {
            if (k <= L[n-2]) {
                n -= 2;
            } else {
                k -= L[n-2];
                n -= 1;
            }
        }
        if (n == 1) return A[(int)(k - 1)] - '0';
        else return B[(int)(k - 1)] - '0';
    };

    // Compute the answer
    long long answer = 0;
    long long pow10 = 1;
    for (int n = 0; n <= 17; n++) {
        lll k = (lll)(127 + 19 * n) * power7(n);
        int digit = find_digit(k);
        answer += pow10 * digit;
        pow10 *= 10;
    }

    printf("%lld\n", answer);
    return 0;
}

"""
Problem 230: Fibonacci Words

F(1) = A (100 digits of pi), F(2) = B (next 100 digits of pi)
F(n) = F(n-2) . F(n-1) (concatenation, older part first)
Sequence: A, B, AB, BAB, ABBAB, ...

Find sum of D((127+19n)*7^n) * 10^n for n = 0 to 17,
where D(k) is the k-th digit of the infinite Fibonacci word.
"""

def solve():
    A = ("1415926535897932384626433832795028841971"
         "6939937510582097494459230781640628620899"
         "86280348253421170679")
    B = ("8214808651328230664709384460955058223172"
         "5359408128481117450284102701938521105559"
         "64462294895493038196")

    # Precompute Fibonacci lengths
    MAX_N = 200
    L = [0] * (MAX_N + 1)
    L[1] = L[2] = 100
    for i in range(3, MAX_N + 1):
        L[i] = L[i-1] + L[i-2]
        if L[i] > 10**30:
            for j in range(i+1, MAX_N + 1):
                L[j] = 10**30
            break

    def find_digit(k):
        """Find the k-th digit (1-indexed) of the infinite Fibonacci word."""
        n = 1
        while L[n] < k:
            n += 1
        # F(n) = F(n-2) . F(n-1)
        while n > 2:
            if k <= L[n-2]:
                n -= 2
            else:
                k -= L[n-2]
                n -= 1
        if n == 1:
            return int(A[k - 1])
        else:
            return int(B[k - 1])

    # Compute the answer
    answer = 0
    for n in range(18):
        k = (127 + 19 * n) * (7 ** n)
        digit = find_digit(k)
        answer += digit * (10 ** n)

    print(answer)

solve()