Project Euler Problem 230


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.


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

The first few terms of FA,B are:
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:


and for B the next hundred digits:

48111745028410270193852110555964462294895493038196 .

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


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