Statement

For any two strings of digits, A and B, we define F_A,B to be the sequence (A,B,AB,BAB,ABBAB,…) in which each term is the concatenation of the previous two.

Further, we define D_A,B(n) to be the nth digit in the first term of F_A,B that contains at least n digits.

Example:

Let A=1415926535, B=8979323846. We wish to find D_A,B(35), say.

The first few terms of F_A,B are:
1415926535
8979323846
14159265358979323846
897932384614159265358979323846
14159265358979323846897932384614159265358979323846
Then D_A,B(35) is the 35^th digit in the fifth term, which is 9.

Now we use for A the first 100 digits of π behind the decimal point:

14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679

and for B the next hundred digits:

82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196 .

Find $\sum _{n = 0,1,...,17} 10^{n} \times D_{A,B}((127+19n)7^{n})$.

Solution

To accomplish this task it is important to notice how the string is built to understand its properties. At first what is easily seen is that the length of the string at iteration n is equal to Fib_n * length of one of the strings.

Knowing that it is easy to determine the iteration in which the string is going to be long enough. Now it's time to determine the digit at the indicated position in that string, in order to do that I will disassemble methodically the string until I have the equivalent location of the digit in the 3rd iteration(A + B). In order to do that how the string is built is fundamental:

To form the n^th iteration of F_A,B = F_A,B(n-2) + F_A,B(n-1). We know the length of the three of them because of the relation with the Fib sequence mentioned previously, knowing that we can translate the index at the n^th iteration at its corresponding index in (n-1)^th iteration. There are two cases:

• index > length(F_A,B(n-2)) -> in this case it is really easy we just subtract the length of F_A,B(n-2) to the index.
• index <= length(F_A,B(n-2)) -> in this case we need to take note that F_A,B(n-2) is included in F_A,B(n-1) so what we need to do is determine the location of F_A,B(n-2) in F_A,B(n-1) which will be in its last part, so we "align" the index to that and that's it. The new index = index + length(F_A,B(n -1)) -length( F_A,B(n-2)).

When we reached that we are in A + B situation we collect the n^th digit.

calc_offset = lambda x: (127+19*x)*(7**x)
 
def solve(n, a, b):
    len_str = len(a)
    ab = a + b
    i1 = 1
    i2 = 2
    while i2 * len_str < n:
        t = i2
        i2 += i1
        i1 = t
    while i2 > 2:
        t = i1
        i1 = i2 - i1
        i2 = t
        if n <= i1 * len_str:
            n += i2 * len_str
        n -= i1 * len_str
    return ab[n-1]
 
a = '1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
b = '8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196'
 
if __name__ == '__main__':
    result = []
    for i in range(18):
        result.insert(0, solve(calc_offset(i), a, b))
    print("The result is:", ''.join(result))

The Python file is available for download here.