Efficient Bytewise FizzBuzz Given the following Python &quot;reference implementation&quot; of non-terminating FizzBuzz:
i=1
while True:
    if i%15 == 0:
        print(&quot;FizzBuzz&quot;)
    elif i%3 == 0:
        print(&quot;Fizz&quot;)
    elif i%5 == 0:
        print(&quot;Buzz&quot;)
    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.
Test cases:
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.
JavaScript (Node.js), 145 bytes
Saved 2 bytes thanks to @user202729
Expects a BigInt. Outputs # instead of \n for readability.
f=(n,k=0n,p=10n**k,x=55n+8n*k,q=p*3n/5n*x||30n)=&gt;n&lt;q?(g=p=&gt;j--&amp;&amp;([[&quot;Fizz&quot;][p%3n]]+[[&quot;Buzz&quot;][p%5n]]||p)+'#'+g(++p))(p+n/x*(j=15n))[n%x]:f(n-q,-~k)

Try it online!
How?
Method
We use a recursive function that quickly computes the number of characters required to build all blocks of 15 terms using numbers of \$1\$, \$2\$, ..., \$N\$ digits. This takes \$\approx \log(n)\$ iterations, where \$n\$ is the input.
The only block that is explicitly generated is the last one, which contains the character we're looking for.
Formulae
Below is the template of a block of 15 terms of the sequence, where # is the separator and @ is a placeholder for a full number. (Note that the leading term modulo \$15\$ can be anything between \$0\$ and \$14\$. The length of the block doesn't depend on that.)
        &lt;--------- 55 characters and 8 full numbers ----------&gt;
        FizzBuzz#@#@#Fizz#@#Buzz#Fizz#@#@#Fizz#Buzz#@#Fizz#@#@#
        ^        ^ ^ ^    ^ ^    ^    ^ ^ ^    ^    ^ ^    ^ ^
mod 15: 0        1 2 3    4 5    6    7 8 9    10  11 12  13 14

All terms in such a block are meant to have the same number of digits \$k+1\$. For \$k&gt;0\$, the length of the block is \$55+8k\$ characters. For \$k=0\$, we can only build a partial block of 9 terms whose length is \$30\$ characters:
&lt;------ 30 characters -------&gt;
1#2#Fizz#4#Buzz#Fizz#7#8#Fizz#

The number of terms with \$k+1\$ digits is \$9\times 10^k\$.
The number of blocks with \$k+1\$ digits is:
$$\left\lceil10^k\times\dfrac{9}{15}\right\rceil=\left\lceil10^k\times\dfrac{3}{5}\right\rceil$$
(where the ceiling is only needed for \$k=0\$)
And the number of characters is:
$$\cases{
30&amp;k=0\\
10^k\times\dfrac{3}{5}\times (55+8k)&amp;k&gt;0
}$$
Commented
f = (                      // f is a recursive function taking:
  n,                       //   n = input
  k = 0n,                  //   k = exponent
  p = 10n ** k,            //   p = 10 ** k
  x = 55n + 8n * k,        //   x = length of a block of 15 terms, using numbers of
                           //       k + 1 digits
  q = p * 3n / 5n * x      //   q = number of characters added when all numbers of
      || 30n               //       k + 1 digits are used (p = 1 is an edge case)
) =&gt;                       //
n &lt; q ?                    // if n is less than q:
  ( g = p =&gt;               //   g is a recursive function that builds the block of 15
                           //   terms in which lies the character we're looking for
    j-- &amp;&amp;                 //     abort if j = 0 (decrement it afterwards)
    (                      //     otherwise:
      [[&quot;Fizz&quot;][p % 3n]] + //       append 'Fizz' if p is a multiple of 3
      [[&quot;Buzz&quot;][p % 5n]]   //       append 'Buzz' if p is a multiple of 5
      || p                 //       append p if it's neither a multiple of 3 or 5
    ) + '#' +              //       append the separator
    g(++p)                 //       append the result of a recursive call to g
  )(p + n / x * (j = 15n)) //   initial call to g: we set j to 15 and add to p the
                           //   number of terms that can be generated with n
                           //   characters, using only full blocks of 15 terms
  [n % x]                  //   extract the character at n modulo x
:                          // else:
  f(n - q, -~k)            //   recursive call to f with n - q and k + 1