Very interesting problem. It was a fun one to work on during this snowy day.
The trick was to figure out whether the digit was part of an A or a B. Once we have that information, it is simple to be able to find the digit.
I started by writing out the values of these “Fibonacci words” and noticed that other than the first two letters, the remaining letters were always the same. From here the trick was to figure out which row first houses the letter, then modulo off the first half of the word until the location is either a 1 or a 2.
For example, if we are looking for the 18th letter in the Fibonacci word, we notice that the first row that has more than 18 letters is the 8th row:
1: A
2: B
3: AB
4: BAB
5: ABBAB
6: BABABBAB
7: ABBABBABABBAB
8: BABABBABABBABBABABBAB
Next, we chop off everything from the previous row (the 7th) leaving just
BABABBAB. The highlighted letter is now the 5th letter in this Fibonacci
word.
1: A
2: B
3: AB
4: BAB
5: ABBAB
Repeating the process one more time, we find that the highlighted letter is the second letter of the third row. We can now easily deduce that it is the letter B.
A = '1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
B = '8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196'
def memoize(fn):
_cache = {}
def wrap(n):
if n in _cache:
return _cache[n]
ret = fn(n)
_cache[n] = ret
return ret
return wrap
@memoize
def fib(n):
if n < 2:
return 1
f1 = f2 = i = 1
while i < n:
i += 1
f1, f2 = f2, f1 + f2
return f2
def findletter(n):
f, i = n, 0
while f > 2:
i = 0
while fib(i) < f:
i += 1
f %= fib(i-1)
if f == 1:
if (i + 1) % 2 == 0:
return 'B'
return 'A'
if (i + 1) % 2 == 1:
return 'B'
return 'A'
def solve(n):
letters = {'A': A, 'B': B}
lena = len(A)
def d(n):
d, m = divmod(n, lena)
l = findletter(d+(m>0))
return int(letters[l][(n-1)%lena])
total, ten, seven = 0, 1, 1
for i in range(n + 1):
num = (127 + 19*i) * seven
total += d(num) * ten
ten *= 10
seven *= 7
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest, problem
from problem import solve
_test_solve = (
(0, 3),
(1, 93),
(2, 393),
(3, 9393),
(4, 19393),
(5, 519393),
(6, 4519393),
(7, 64519393),
(8, 364519393),
(9, 2364519393),
(10, 12364519393),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
problem.A = '1415926535'
problem.B = '8979323846'
assert expect == solve(n)