10
\$\begingroup\$

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
\$\endgroup\$
5
  • 4
    \$\begingroup\$ Is it a part of this challenge to watch the 10-min video and find out what that nice property is? :-) \$\endgroup\$
    – Luis Mendo
    Jan 31, 2016 at 19:29
  • \$\begingroup\$ Not necessarily...you could look at a few of those numbers and figure out the property for yourself. I would definitely encourage this method. Hence the spoiler alert. \$\endgroup\$
    – quintopia
    Jan 31, 2016 at 20:13
  • \$\begingroup\$ IMO, it'd probably be better to standardize the n,k,b variables such that testing them, your input is identical. \$\endgroup\$
    – Kyle Kanos
    Feb 1, 2016 at 1:38
  • \$\begingroup\$ I found a bug in my code. It cost me 10 bytes to fix it :-( \$\endgroup\$
    – Neil
    Feb 9, 2016 at 8:52
  • \$\begingroup\$ You still win by default. \$\endgroup\$
    – quintopia
    Feb 9, 2016 at 16:53

3 Answers 3

7
+200
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ ah so you're the one that upvoted the question out of nowhere \$\endgroup\$
    – quintopia
    Jan 14, 2021 at 5:42
4
\$\begingroup\$

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.

(bk-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 bk-1 is 0.00...01 remainder 0.00...01 [k-1 zeros]. This obviously continues to give (bk-1)-1 as being 0.00...0100...0100... [k-1 zeros each time] in b-ary notation.

To form (bk-1)-2 it merely suffices to divide (bk-1)-1 itself by bk-1. Again we consider k digits each time. The first k digits are just 00..01 which obviously don't divide by bk-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 bk+1 by bk-1 giving 1 remainder 2. Considering the next k digits we divide 2bk+1 by bk-1 giving 2 remainder 3. At each step we have mbk+1 = m(bk-1)+m+1. This continues until we reach (bk-3)bk+1 which divides by bk-1 giving bk-3 remainder bk-2. At this point (bk-2)bk+1 is equal to (bk-1-1)(bk-1+1)+1 which can be written as (bk-1)2-12+1 or simply (bk-1)2, which therefore divides exactly by bk-1.

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

My solution divides n-1 by k and then reduces modulo bk-1 to find the appropriate k-digit number. If n is an exact multiple of k(bk-1) it adds 1 to the number because the last k-digit number is bk-1 itself. Having found the number it then adds bk, 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.

\$\endgroup\$
3
  • \$\begingroup\$ what do i need to do to test this? \$\endgroup\$
    – quintopia
    Feb 1, 2016 at 0:19
  • \$\begingroup\$ @quintopia Does meta.codegolf.stackexchange.com/a/8252/17602 help? \$\endgroup\$
    – Neil
    Feb 1, 2016 at 9:45
  • \$\begingroup\$ Okay, it tests fine. I wish more languages had an equivalent to that toString! \$\endgroup\$
    – quintopia
    Feb 2, 2016 at 14:49
0
\$\begingroup\$

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...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.