### Background

I was reading a [book](http://www.amazon.co.uk/Things-Make-Do-Fourth-Dimension/dp/1846147646/) recently, "Things to Make and Do in the Fourth Dimension" by comedian and mathematician Matt Parker, and in the first chapter of the book Matt talks about problems he likes to solve in his head to take his mind off the fact that he is in his dentist's chair, we've all been there!

The problem he talks about relates to polydivisible numbers, and I thought a kata should be written on the subject as it's quite interesting. (Well it's interesting to me, so there!)

### Polydivisib... huh what?

So what are they?

A polydivisible number is divisible in an unusual way. The first digit is cleanly divisible by `1`, the first two digits are cleanly divisible by `2`, the first three by `3` and so on.

The interesting thing about polydivisiblity is that it relates to the underlying number, but not the base it is written in, so if aliens came to Earth and used base `23` (`11` fingers on one hand and `12` on the other), no matter what squiggles they use to write numbers, they would find the same numbers polydivisible!

### Polydivisibilty Example:

Let's do a worked example to clear up any questions ...

Starting wih the number `1,232` in base `10` then:

```
 1232
 1    /1 = 1    Yay!
 12   /2 = 6    Yay!
 123  /3 = 41   Yay!
 1232 /4 = 308  Yay!
```

Thus `1,232` is a polydivisible number in base `4` and above.

However starting wih the number `123,220` and using base `10` then:

```
 123220
 1      /1 = 1            Yay!
 12     /2 = 6            Yay!
 123    /3 = 41           Yay!
 1232   /4 = 308          Yay!
 12322  /5 = 2464.4       Oh no, that's not a round number!
 123220 /6 = 220536.333r  Oh no, that's not a round number!
```

Thus `123,220` is not a polydivisible base 10 number, but what about in another base?

Again starting wih the number `123,220` and using base `6` then:

```
 base 6   base 10
 1      = 1       -> 1     /1 = 1     Yay!
 12     = 8       -> 8     /2 = 4     Yay!
 123    = 51      -> 51    /3 = 17    Yay!
 1232   = 308     -> 308   /4 = 77    Yay!
 12322  = 1850    -> 1850  /5 = 370   Yay!
 123220 = 11100   -> 11100 /6 = 1850  Yay!
```

Thus `123,220` is a polydivisible base `6` number (and a polydivisible base `10` number when converted to `11100` in base `10`).

### Kata

In this kata you must implement two methods: `is_polydivisible(n, b)` and `get_polydivisible(n, b)`.

The first `is_polydivisible(n, b)` will return `True` if `n` is polydivisible in base `b` or `False` if not.

The second `get_polydivisible(n, b)` will return the `n`th polydivisible number using base `b`, the first polydivisible number is of course always `0`.

You can assume that all inputs are valid.

```if:haskell
All necessary arithmetic can be done in `Int` range.
```

### Kata Examples:

```python
    is_polydivisible("1232", 10)   # => True
    is_polydivisible("123220", 10) # => False
    is_polydivisible("123220", 6)  # => True
    get_polydivisible(22, 10)      # => "32"
    get_polydivisible(22, 16)      # => "1A"
    get_polydivisible(42, 16)      # => "42"
```

#### A Note on Bases

The maximum base used is base `62`, and uses characters in the following order `[0-9][A-Z][a-z]` to denote its digits, base `n` will use the first `n` characters of this sequence.
```if-not:haskell
A constant CHARS has been declared with this sequence for you.
```

Difficulty: interview

Starter code:

def is_polydivisible(s, b):
	

Solutions:
l = {j:i for i,j in enumerate('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz')}
l_ = dict(enumerate('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'))

is_polydivisible = lambda n, base:next((0 for i in range(1, len(n) + 1) if get_base(n[:i], base) % i),1)
get_base = lambda n, base:sum(int(l[j]) * (base ** i) for i, j in enumerate(n[::-1]))
def get_polydivisible(n, base):
    c = i = 0; r = ''
    while c < n:
        t = to_base(i, base)
        if is_polydivisible(t, base) : c += 1 ;  r = t
        i += 1
    return ''.join(r) or '0'

def to_base(n, base):
      li = []
      while n:
          n, b = divmod(n, base)
          li.append(l_[b])
      return li[::-1]

from itertools import count

digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def convert_digits(s):
    # converts each digit in base b in string s to its corresponding value in base 10
    # @return list of integers from 0 to b-1
    return [int(digits.index(d)) for d in s]

def convert_to_base_10(s,b):
    # converts an integer in base b to base 10
    # @input string representing integer and integer b representing base
    # @return string representing integer in base 10
    if b == 10:
        return s
    coeffs = convert_digits(s)[::-1]
    return str(sum([coeffs[i]*b**i for i in range(len(s))]))

def convert_from_base_10(s,b):
    #converts an integer from base 10 to base b
    # @input string representing integer and integer b representing base
    # @return string representing integer in base b
    max_exp = 0
    n = int(s)
    coeffs = []
    while b**(max_exp+1) <= n:
        max_exp += 1
    for k in range(max_exp+1):
        coeffs.append(digits[n%b])
        n = int((n-n%b)/b)
    return "".join(coeffs[::-1])

def is_polydivisible(s,b):
    # checks for polydivisibility in base b
    base_b = [s[:k] for k in range(1,len(s)+1)]
    #print("base_b = " + str(base_b))
    base10 = list(map(lambda s: convert_to_base_10(s,b), base_b))
    #print("base10 = " + str(base10))
    divisible = [int(base10[k])%(k+1) == 0 for k in range(1,len(s))]
    return not (False in divisible)

def get_polydivisible(n, b):
    # @return the nth polydivisible number in base b
    poly_count = 0
    for k in count(start=0, step=1):
        if is_polydivisible(convert_from_base_10(str(k),b), b):
            temp = str(k)
            poly_count += 1
            if poly_count == n:
                return convert_from_base_10(temp,b)

CHARS="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def from10(n, b):
    if b == 10: return n
    new = ''
    while n: 
        new += str(CHARS[n%b])
        n //= b
    return new[::-1]

def to10(n, b):
    num = 0
    for i, d in enumerate(str(n)[::-1]):
        num += int(CHARS.index(d))*(b**i)
    return num

def is_polydivisible(s, b):
    for i in range(1, len(s)+1):
        if to10(s[:i], b) % i != 0: return False
    return True


def get_polydivisible(n, b):
    if n == 1: return '0'
    i = 0 
    poly = []
    while len(poly) < n:
        fr = str(from10(i, b))
        if is_polydivisible(str(fr), b): 
            poly.append(fr)
            i += 1
        else: i += 1
    return poly[-1]

b62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def atoi (n, b):
    res = 0
    n = str(n)
    for i,c in enumerate(n):
        res += b62.index(c) * b**(len(n)-i-1)
    return res
    
def itoa (n, b):
    res = ""
    while n > 0:
        res = b62[n % b] + res
        n //= b
    return res or "0"

def is_polydivisible(s, b):
    for i in range(len(s), 0, -1):
        n = atoi(s[:i], b)
        if n % i != 0:
            return False
    return True

def get_polydivisible(n, b):
    res = ""
    c = 0
    for i in range(n):
        while 1:
            a = itoa(c, b)
            c += 1
            if is_polydivisible(a, b):
                res = a
                break
    return res

is_polydivisible, get_polydivisible = (lambda digits: ((lambda ds: lambda s, b: (lambda f: (lambda x: x(x))(lambda y: f(lambda *xs: y(y)(*xs))))(lambda f: lambda l, n, xs: n % l == 0 and (not xs or f(l+1, n*b+xs.pop(), xs)))(1, ds[s[0]], [ds[i] for i in reversed(s[1:])]))({i:n for n,i in enumerate(digits)}), (lambda n, b: '0' if n == 1 else (lambda f: (lambda x: x(x))(lambda y: f(lambda *xs: y(y)(*xs))))(lambda f: lambda n, l, ds, xs: (xs[n][0] if n < len(xs) else f(n-len(xs), l+1, ds, [(s+d, x*b+i) for s,x in xs for i,d in enumerate(ds) if (x*b+i)%l==0])) if xs else None)(n - 2, 2, digits[:b], list(zip(digits, range(b)))[1:]))))('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz')

CHARS="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def base(number, base):
    return sum([num * base**coeff for coeff, num in enumerate(number[::-1])])

def bias_checker(n, b, slicer=0):
    if n[0] == b:
        n[0]=0
        n.insert(0,1)
    elif n[-1+ slicer] == b:
        n[-1 + slicer] = 0
        n[-2 + slicer] += 1
        bias_checker(n, b, slicer-1)
    return

def get_polydivisible(n, b):
    num = [0]
    count = 0
    polydiv_num = 0
    while count < n:
        for x in range(1, len(num)+1):
            if base(num[:x], b) % x != 0:
                num[-1] += 1
                bias_checker(num, b)                
                break
        else:
            count += 1
            polydiv_num = num
            num[-1] += 1
            bias_checker(num, b)
    num[-1] -= 1
    return "".join([CHARS[x] for x in num]) 

def is_polydivisible(s, b):
    num = [CHARS.find(x) for x in s]
    for x in range(1,len(num)+1):
        if base(num[:x],b) % x != 0:
            return False
    return True

CHARS="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def todecimal(s,b):
    l=len(s)
    res=0
    for i in range(l):
        c=s[i]
        val=CHARS.find(c)
        res=res+val*b**(l-i-1)
    return res

def tobaseb(n,b):
    res=''
    restant=n
    while restant>0:
        res=CHARS[restant%b]+res
        restant=restant//b
    return res

def is_polydivisible(s, b):
    yes=True
    for i in range(len(s)):
        if b!=10:
            bout=str(todecimal(s[:i+1],b))
        else:
            bout=s[:i+1]
        if int(bout)%(i+1)!=0:
            yes=False
            break
    return yes

def get_polydivisible(n, b):
    if n==1:
        return '0'
    c=0
    i=0
    while c<n:
        if b!=10:
            ib=tobaseb(i,b)
        else:
            ib=str(i)
        if is_polydivisible(ib,b):
            c=c+1
        i=i+1
    return ib

CHARS="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def to_dec(s,b):
    n = 0
    for i,v in enumerate(s[::-1]):
        n += CHARS.index(v)*b**i
    return n

def to_base(n,b):
    r = ''
    while n >= b:
        n,x = divmod(n,b)
        r += CHARS[:b][x]
    r += CHARS[:b][n]
    return r[::-1]
         
def is_polydivisible(s,b):
    return all(not to_dec(s[:i],b)%i for i in range(1,len(s)+1))

def get_polydivisible(x,b):
    c = 0
    n = 0
    while c<x:
        try:
            if is_polydivisible(to_base(n,b),b):
                c += 1
        except:
            pass
        n += 1
    return to_base(n-1,b) or '0'

CHARS="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def is_polydivisible(s, b):
    divide=1
    while divide<=len(s):
        temp=divide
        index=0
        num=0
        while temp>0:                
            num+=CHARS.index(s[index])*(b**(temp-1))
            temp-=1
            index+=1
        if num%divide!=0:
            return False
        divide+=1
        num=0
    return True
def get_polydivisible(n, b):
    count=0
    count2=0
    temp=1
    s=""
    while True:
        if count2>=b**temp:
            temp+=1
        record=count2
        power=temp 
        while len(s)<temp:                    
            some=record//b**(power-1)
            s+=CHARS[some]
            record-=some*(b**(power-1))
            power-=1
        count2+=1
        if is_polydivisible(s, b):
            count+=1
        if count==n:
            return s
        s=""

CHARS="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def is_polydivisible(s, b):
    divide=1
    if b==10:        
        while divide<=len(s):
            num=int(s[0:divide])
            if num%divide!=0:
                return False
            divide+=1
        return True
    else:
        while divide<=len(s):
            temp=divide
            index=0
            num=0
            while temp>0:                
                num+=CHARS.index(s[index])*(b**(temp-1))
                temp-=1
                index+=1
            if num%divide!=0:
                return False
            divide+=1
            num=0
        return True
def get_polydivisible(n, b):
    count=0
    count2=0
    temp=1
    s=""
    while True:
        if count2>=b**temp:
            temp+=1
        record=count2
        power=temp 
        while len(s)<temp:                    
            some=record//b**(power-1)
            s+=CHARS[some]
            record-=some*(b**(power-1))
            power-=1
        count2+=1
        if is_polydivisible(s, b):
            count+=1
        if count==n:
            return s
        s=""