### 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: MEDIUM_HARD
Tags: Number theory

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):
	return [int(digits.index(d)) for d in s]

def convert_to_base_10(s, b):
	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):
	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):
	base_b = [s[:k] for k in range(1, len(s) + 1)]
	base10 = list(map(lambda s: convert_to_base_10(s, b), base_b))
	divisible = [int(base10[k]) % (k + 1) == 0 for k in range(1, len(s))]
	return not False in divisible

def get_polydivisible(n, 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 = ''