Efficient Bytewise FizzBuzz

Question

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.

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.

Answer 1

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)=>n<q?(g=p=>j--&&([["Fizz"][p%3n]]+[["Buzz"][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.)

        <--------- 55 characters and 8 full numbers ---------->
        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>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:

<------ 30 characters ------->
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&k=0\\ 10^k\times\dfrac{3}{5}\times (55+8k)&k>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)
) =>                       //
n < q ?                    // if n is less than q:
  ( g = p =>               //   g is a recursive function that builds the block of 15
                           //   terms in which lies the character we're looking for
    j-- &&                 //     abort if j = 0 (decrement it afterwards)
    (                      //     otherwise:
      [["Fizz"][p % 3n]] + //       append 'Fizz' if p is a multiple of 3
      [["Buzz"][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

Answer 2

Python 2, 216 212 209 189 183 182 bytes

f=lambda i,j=90:j*"."and f(i,j-1)+("Fizz"*(j%3<1)+"Buzz"*(j%5==1)or str(10*i+j-1))+"\n"
n,i,l=input()-30,1,len
while n/i/l(f(i)):n-=l(f(i))*i;i*=10
s=f(i+n/l(f(i))*9);print s[n%l(s)]

Try it online! Compares n against a number increasing by more than tenfold every iteration, so I assume this should take log time. Edit: Saved 4 bytes thanks to @Danis. Saved 3 6 bytes thanks to @JonathanAllan. Saved 1 byte thanks to @ovs.

Answer 3

Ruby, 170 ... 139 138 bytes

f=->n,d=0,c=55,a=30,b=6,t=1{n<a ?((b%10-5..10).map{|x|:FizzBuzzz[x**4%-15,x==0?8:4]||d+(n/c)*15+x}*$/)[n%c]:f[n-a,d+t*15,c+=8,b*c,b*10,b]}

Try it online!

How:

f=->n,d=0,c=55,a=30,b=6,t=1

Initialize some parameters: d is the last number of the previous block, c is the size in bytes of the 15-number sequence in the current block, a is the length of the current block, b is the number of sequences in the next block, and t is the number of sequences in the current block.

    {n<a ?

First check: is the byte in the current block?

    ((b%10-5..10)

Build a FizzBuzz sequence, starting from 1 for the first iteration, and from -5 after that. We could stop at 9, but going to 10 adds the final newline (the last "Buzz" is ignored) at the cost of 1 byte.

    :FizzBuzzz[x**4%-15,x==0?8:4]||d+(n/c)*15+x

Courtesy of Lynn: shortest Ruby FizzBuzz generator ever. The Fizzes and Buzzes are in fixed position, we have to find the beginning of the sequence, which is the (n/c)th sequence of the current block. The starting number is d plus 15 times the position of the sequence in the block.

    }*$/)[n%c]:

Join using newlines, get the nth character of the block, and since this is the (n/c)th slice, this is the (n%c)th byte of this slice.

f[n-a,d+t*15,c+=8,b*c,b*10,b]}

If the byte is not in the current block, move to the next:

• decrease n by the length of the current block
• increase d by 15 times the number of sequences in the current block
• increase the length in byte of a sequence by 8
• calculate the number of bytes in the next block
• multiply the number of sequences in a block by 10
• still lose to Javascript by 1 byte???
• reduce by 1 byte every day (and thanks Dingus for -1 byte)