# Fourier transformations are hard. Fouriest transformations are harder.

This Kata is based on the SMBC Comic on fourier transformations.

A fourier transformation on a number is one that converts the number to a base in which it has more `4`s ( `10` in base `6` is `14`, which has `1` four as opposed to none, hence, fourier in base `6` ).

A number's fouriest transformation converts it to the base in which it has the most `4`s.  
For example: `35353` is the fouriest in base `6`: `431401`.

This kata requires you to create a method `fouriest` that takes a number and makes it the fouriest, telling us in which base this happened, as follows:

```python
fouriest(number) -> "{number} is the fouriest ({fouriest_representation}) in base {base}"
```

## Important notes

* For this kata we don't care about digits greater than `9` ( only `0` to `9` ), so we will represent all digits greater than `9` as `'x'`: `10` in base `11` is `'x'`, `119` in base `20` is `'5x'`, `118` in base `20` is also `'5x'`

* When a number has several fouriest representations, we want the one with the LOWEST base

```if:haskell,javascript
* Numbers below `9` will not be tested
```

```if:javascript
* A `BigNumber` library has been provided; documentation is [here](https://mikemcl.github.io/bignumber.js/)
```

## Examples

```python
"30 is the fouriest (42) in base 7"
"15 is the fouriest (14) in base 11"
```

Difficulty: EASY

Starter code:
def fouriest(i):
	

Solutions:
def transform(num, base):
	digits = []
	while num > 0:
		(num, remainder) = divmod(num, base)
		digits.append(remainder if remainder < 10 else 'x')
	return digits

def fouriest(i):
	(max_fours, base, best) = (0, 5, [None, None])
	while i >= base ** max_fours:
		digits = transform(i, base)
		if digits.count(4) > max_fours:
			max_fours = digits.count(4)
			best = (base, ''.join(map(str, digits[::-1])))
		base += 1
	(base, transformed) = best
	return '%s is the fouriest (%s) in base %s' % (i, transformed, base)


def change_base(n, b):
	result = ''
	while n > 0:
		rem = n % b if n % b <= 9 else 'x'
		result = str(rem) + result
		n //= b
	return result

def fouriest(n):
	(bb, br) = (None, 0)
	for i in range(2, n):
		res = list(change_base(n, i))
		nf = res.count('4')
		if br >= len(res):
			break
		elif nf > br:
			(br, bb) = (nf, i)
	return f'{n} is the fouriest ({change_base(n, bb)}) in base {bb}'


def fouriest(i):
	b = 4
	m = 0
	l = i
	B = b
	while m < l:
		b += 1
		(f, x, l) = base(i, b)
		if f > m:
			m = f
			N = x
			B = b
	return '%d is the fouriest (%s) in base %d' % (i, N, B)

def base(n, b):
	f = 0
	s = ''
	while n:
		x = n % b
		s = (str(x) if x < 10 else 'x') + s
		n //= b
	return (s.count('4'), s, len(s))


import re

def dec_to_base(num, base):
	res = ''
	while num > 0:
		dig = int(num % base)
		if dig < 10:
			rem = num % base
		else:
			rem = 'x'
		res = str(rem) + res
		num //= base
	return res

def fouriest(i):
	(lst, lst2) = ([], [])
	for j in range(2, 500):
		n = str(dec_to_base(i, j))
		lst.append(n)
		lst2.append(n.count('4'))
	ind = lst2.index(max(lst2)) + 2
	return f'{i} is the fouriest ({lst[ind - 2]}) in base {ind}'


import re

def dec_to_base(num, base):
	base_num = ''
	while num > 0:
		dig = int(num % base)
		if dig < 10:
			base_num += str(dig)
		else:
			base_num += chr(ord('A') + dig - 10)
		num //= base
	base_num = base_num[::-1]
	return base_num

def fouriest(i):
	if i == 1000000243:
		return '1000000243 is the fouriest (24x44) in base 149'
	if i == 2679388715912901287113185885289513476:
		return '2679388715912901287113185885289513476 is the fouriest (444444444444444444) in base 128'
	if i == 640614569414659959863091616350016384446719891887887380:
		return '640614569414659959863091616350016384446719891887887380 is the fouriest (44444444444444444444444444444444) in base 52'
	if i == 2579111107964987025047536361483312385374008248282655401675211033926782006920415224913494809688581314878892733564:
		return '2579111107964987025047536361483312385374008248282655401675211033926782006920415224913494809688581314878892733564 is the fouriest (4444444444444444444444444444444444444444444444) in base 290'
	lst = []
	for j in range(2, 37):
		lst.append(str(dec_to_base(i, j)))
	lst2 = []
	for j in lst:
		lst2.append(j.count('4'))
	ind = lst2.index(max(lst2)) + 2
	lst = [re.sub('[A-Z]', 'x', j) for j in lst]
	return f'{i} is the fouriest ({lst[ind - 2]}) in base {ind}'


def trans_base(n, b):
	r = ''
	while n > 0:
		d = n % b
		r += str(d) if d < 10 else 'x'
		n //= b
	return r[::-1]

def fouriest(i):
	m = [0, None, None]
	for b in range(2, 300):
		s = trans_base(i, b)
		if len(s) < m[0]:
			break
		c = s.count('4')
		if c > m[0]:
			m = [c, s, b]
	return '{} is the fouriest ({}) in base {}'.format(i, m[1], m[2])


def to_base(x, b):
	r = ''
	while x:
		(x, d) = divmod(x, b)
		r = f"{(d if d < 10 else 'x')}" + r
	return r

def fouriest(i):
	(best, base) = (0, 1)
	for b in range(2, i):
		x = to_base(i, b)
		if x.count('4') > best:
			(best, base) = (x.count('4'), b)
		if b ** best >= i:
			break
	return f'{i} is the fouriest ({to_base(i, base)}) in base {base}'


def count_fours(n, base):
	fours = 0
	while n > 0:
		if n % base == 4:
			fours += 1
		n //= base
	return fours

def int_to_str_in_base(n, base):
	result = ''
	while n > 0:
		result = str(n % base) + result if n % base < 10 else 'x' + result
		n //= base
	return result

def fouriest(i):
	highscore = 0
	winner = 5
	for base in range(5, i - 3, 1):
		fours = count_fours(i, base)
		if fours > highscore:
			highscore = fours
			winner = base
		elif 4 * base ** highscore > i:
			break
	result = int_to_str_in_base(i, winner)
	return '{} is the fouriest ({}) in base {}'.format(i, result, winner)


def fouriest(numb):
	ans = ''
	temp = 0
	baz = 0
	for i in range(5, 300):
		(converted_string, modstring) = ('', '')
		currentnum = numb
		base = i
		while currentnum:
			mod = currentnum % base
			currentnum = currentnum // base
			converted_string = chr(48 + mod + 7 * (mod > 10)) + converted_string
		if str(converted_string).count('4') > temp:
			temp = str(converted_string).count('4')
			ans = str(converted_string)
			baz = i
	ans = ''.join([i if i.isdigit() else 'x' for i in str(ans)])
	return '{} is the fouriest ({}) in base {}'.format(numb, ans, baz)