Given the following Python "reference implementation" of non-terminating FizzBuzz:
i=1 while True: if i%15 == 0: print("FizzBuzz") elif i%3 == 0: print("Fizz") elif i%5 == 0: print("Buzz") else: print(i) i += 1
We can represent its output as an infinite array of chars/bytes (assuming \n line terminators) that looks like the following:
['1', '\n', '2', '\n', 'F', 'i', 'z', 'z', '\n', '4', '\n', 'B', 'u', 'z', 'z', '\n', 'F', 'i', 'z', 'z', ...]
Your task is to write the shortest function or program that returns the character at the Nth index of this array.
Sounds easy? Your code should also work for extremely large values of N, for example 1e100.
It is possible to calculate the Nth byte of this output array in O(log(n)) time (or possibly better) - how is left as an exercise for the reader.
Your solution must run in O(poly(log(n))) time (or better). There is no hard execution time limit, but as a rough guideline you should be able to solve the
N=1e100 case almost instantaneously.
This is code-golf: the shortest code in bytes wins.
f(0) == '1' f(1) == '\n' f(2) == '2' f(10) == '\n' f(100) == '\n' f(1000) == 'z' f(100000) == 'F' f(1e10) == '5' f(1e100) == '0'
Some more, randomly generated testcases: https://gist.github.com/DavidBuchanan314/65eccad5032c427218eb9c269b55e869
Note: these test cases are correct to the best of my knowledge. If you have contradictory findings, I am open to discussion.