7
\$\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 (bk - 1)-2.

The output must be correct for n and bk 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 bk 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\$
  • 3
    \$\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 '16 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 '16 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 '16 at 1:38
  • \$\begingroup\$ I found a bug in my code. It cost me 10 bytes to fix it :-( \$\endgroup\$ – Neil Feb 9 '16 at 8:52
  • \$\begingroup\$ You still win by default. \$\endgroup\$ – quintopia Feb 9 '16 at 16:53
1
\$\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\$
  • \$\begingroup\$ what do i need to do to test this? \$\endgroup\$ – quintopia Feb 1 '16 at 0:19
  • \$\begingroup\$ @quintopia Does meta.codegolf.stackexchange.com/a/8252/17602 help? \$\endgroup\$ – Neil Feb 1 '16 at 9:45
  • \$\begingroup\$ Okay, it tests fine. I wish more languages had an equivalent to that toString! \$\endgroup\$ – quintopia Feb 2 '16 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, privacy policy and cookie policy

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