Problem 230: Fibonacci Words

Mathematical Development

Let

Because $F(n)$ is the concatenation of $F(n-2)$ and $F(n-1)$,

So the lengths follow the Fibonacci recurrence and grow exponentially. This means we can reach any queried position by precomputing only a short table of lengths.

Now suppose $n$ is the smallest index with $L(n)\ge k$. Since

the first $L(n-2)$ digits come from $F(n-2)$ and the remaining digits come from $F(n-1)$. Therefore

This reduces the query to a smaller Fibonacci word without ever constructing the actual string.

Editorial

The strings themselves are a red herring. By the time the index reaches $(127+19n)7^n$ for $n=17$, the relevant Fibonacci word is astronomically long, so building it explicitly is impossible. But the only thing the concatenation rule preserves is length, and length is exactly the information needed to walk a position backwards through the recursion.

So the program does two tiny pieces of precomputation. First it builds the length table until the entries are safely larger than every requested index. Then, for each query position, it repeatedly asks whether the digit lies in the left block $F(n-2)$ or the right block $F(n-1)$. Every step replaces one huge word by a smaller one and eventually lands in either $A$ or $B$, where the digit is read directly.

Pseudocode

Store the two 100-digit base strings A and B.

Precompute the Fibonacci-style length table L(n)
until it is larger than every queried position.

To answer one query k:
    find the first n with L(n) >= k
    while n > 2:
        if k <= L(n - 2):
            move to F(n - 2)
            n = n - 2
        otherwise:
            subtract L(n - 2) from k
            move to F(n - 1)
            n = n - 1
    read the kth digit from A or B

Evaluate the 18 queries and accumulate digit * 10^n.

Complexity Analysis

• Time: $O(\log k)$ per digit lookup, so the whole sum is tiny.
• Space: $O(\log k)$ for the length table.

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

    const int MAXN = 200;
    unsigned long long L[MAXN + 1];
    L[1] = L[2] = 100;
    const unsigned long long cap = 1000000000000000000ULL;
    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;
        }
    }

    auto power7 = [](int n) -> unsigned long long {
        unsigned long long 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 = [&](unsigned long long 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++) {
        unsigned long long k = (unsigned long long)(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)


if __name__ == "__main__":
    solve()