Find the nth base-b digit of (b^k-1)^-2

Question

Task

Your task is simple. Write a program or function which takes three positive integer arguments \$n\$, \$k\$, and \$b\$ in any order, such that \$2 ≤ b ≤ 36\$, and returns or outputs the nth (1-indexed) base-\$b\$ digit after the decimal point of the rational number (\$b^k-1)^{-2}\$.

The output must be correct for \$n\$ and \$b^k\$ up to the largest integer value your language of choice can natively represent. This will most likely mean that you cannot depend on built-in floating point representations to exactly represent the base-\$b\$ expansion of the number.

Fortunately, this class of numbers has a rather nice property [Spoiler Alert!]: https://www.youtube.com/watch?v=daro6K6mym8

Rules

• Base conversion built-ins are permitted.
• Built-in spigot functions capable of indexing digits of exactly represented real numbers are forbidden.
• The digits for base \$b\$ are the first \$b\$ symbols in the string 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ or alternately 0123456789abcdefghijklmnopqrstuvwxyz. Your choice.

Winning

This is code golf. Shortest solution in bytes wins.

Test Cases

(You need not be able to correctly handle all of these if \$n\$ or \$b^k\$ overflows your integer datatype.)

Input (n,k,b)               Output
9846658,3,31                5
789234652,4,10              4
4294967295,17,2             1
4294967254,72,15            B
137894695266,3,30           H
184467440737095595,6,26     L
184467440737095514,999,36   T

Answer 1

APL (Dyalog Extended), 31 bytes

(⎕D,⎕A)⊃⍨⊃⎕⌽¯1⌽,⍉⎕(⊣⊤⍳⍤*~*-2⍨)⎕

Try it online!

A full program that takes numbers from stdin in the order of k, b, n. n being 1-based cost me 3 bytes ¯1⌽.

How it works

The main mathematical trick is well explained in Neil's answer. The gist is that the repeating part of the base-b representation consists of length-k base-b digits of 0..b^k-1, except b^k-2.

This answer implements it very literally: list all repeating base-b digits, cyclically fetch nth digit from it, and convert it to 0-9A-Z. Cyclic indexing uses ngn's trick.

⎕(...)⎕     ⍝ Take k (the right) and b (the left) from stdin
  ⍳⍤*~*-2⍨  ⍝ Create a list of 0..b^k-1, and remove the number b^k-2
  ⊣⊤        ⍝ Convert these numbers into base-b digits into columns
,⍉          ⍝ Transpose and flatten to get the repeating base-b digits
⊃⎕⌽¯1⌽      ⍝ Take n from stdin and get the nth digit cyclically
(⎕D,⎕A)⊃⍨   ⍝ Convert the number to the corresponding char in 0-9A-Z

Answer 2

ES7, 59 bytes

(n,k,b)=>(1+!(n/k%(d=b**k-1))+d+--n/k%d).toString(b)[n%k+1]

ES6-compatible version for people who don't have Firefox Nightly:

(n,k,b)=>(1+!(n/k%(d=Math.pow(b,k)-1))+d+--n/k%d).toString(b)[n%k+1]

Explanation (possibly the same as in the video; I haven't watched it):

I start with the simple case of (b-1)^-1 in b-ary notation. Obviously b-1 does not divide 1, so we add an extra zero after the b-ary point. 1.0 divided by b-1 is 0.1 remainder 0.1. This continues in the obvious manner to give (b-1)^-1 as being 0.111... in b-ary notation.

(b^k-1)^-1 is not much harder; the only difference is that we have to add k extra zeros before we can divide. We then have 1.00...00 [k zeros] divided by b^k-1 is 0.00...01 remainder 0.00...01 [k-1 zeros]. This obviously continues to give (b^k-1)^-1 as being 0.00...0100...0100... [k-1 zeros each time] in b-ary notation.

To form (b^k-1)^-2 it merely suffices to divide (b^k-1)^-1 itself by b^k-1. Again we consider k digits each time. The first k digits are just 00..01 which obviously don't divide by b^k-1, so the first k digits of the result are 00..00. The next k digits are of course also 00..01 so we divide b^k+1 by b^k-1 giving 1 remainder 2. Considering the next k digits we divide 2b^k+1 by b^k-1 giving 2 remainder 3. At each step we have mb^k+1 = m(b^k-1)+m+1. This continues until we reach (b^k-3)b^k+1 which divides by b^k-1 giving b^k-3 remainder b^k-2. At this point (b^k-2)b^k+1 is equal to (b^k-1-1)(b^k-1+1)+1 which can be written as (b^k-1)²-1²+1 or simply (b^k-1)², which therefore divides exactly by b^k-1.

We therefore have managed to divide the first k(b^k-1) digits of (b^k-1)^-1 by b^k-1 exactly, and the sequence therefore repeats at this point. In effect, (b^k-1)^-2 is formed by concatenating all the (zero-padded) k-digit numbers from 0 to b^k-3, plus b^k-1 itself, and then repeating.

My solution divides n-1 by k and then reduces modulo b^k-1 to find the appropriate k-digit number. If n is an exact multiple of k(b^k-1) it adds 1 to the number because the last k-digit number is b^k-1 itself. Having found the number it then adds b^k, which has the effect of forcing the base conversion to generate any required leading zeros. The appropriate digit of the converted number is then returned.

Answer 3

Python 2, 110 bytes

n,k,b=input()
n=~-n%(k*b**k-k)
print"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[(n/k+(n/k+2==b**k))/b**(k-1-n%k)%b]

Maybe answering it myself (poorly) will bring this EASY question some more attention. Usually easy questions get more answers...