Project Euler Problem 230

Statement

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

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

Example:

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

The first few terms of FA,B are:
1415926535
8979323846
14159265358979323846
897932384614159265358979323846
14159265358979323846897932384614159265358979323846
Then DA,B(35) is the 35th 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 Fibn * 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 nth iteration of FA,B = FA,B(n-2) + FA,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 nth iteration at its corresponding index in (n-1)th iteration. There are two cases:

  • index > length(FA,B(n-2)) -> in this case it is really easy we just subtract the length of FA,B(n-2) to the index.
  • index <= length(FA,B(n-2)) -> in this case we need to take note that FA,B(n-2) is included in FA,B(n-1) so what we need to do is determine the location of FA,B(n-2) in FA,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(FA,B(n -1)) -length( FA,B(n-2)).

When we reached that we are in A + B situation we collect the nth 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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License