## **Task**

You are given a positive integer (`n`), and your task is to find the largest number **less than** `n`, which can be written in the form `a**b`, where `a` can be any non-negative integer and `b` is an integer greater than or equal to `2`. Try not to make the code time out :)

The input range is from `1` to `1,000,000`.

## **Return**

Return your answer in the form `(x, y)` or (`[x, y]`, depending on the language ), where `x` is the value of `a**b`, and `y` is the number of occurrences of `a**b`. By the way ** means ^ or power, so 2 ** 4 = 16.
If you are given a number less than or equal to `4`, that is not `1`, return `(1, -1)`, because there is an infinite number of values for it: `1**2, 1**3, 1**4, ...`.  
If you are given `1`, return `(0, -1)`.

## **Examples**

```
 3  -->  (1, -1)  # because it's less than 4
 6  -->  (4, 1)   # because the largest such number below 6 is 4,
                  # and there is only one way to write it: 2**2
65  -->  (64, 3)  # because there are three occurrences of 64: 2**6, 4**3, 8**2
90  -->  (81, 2)  # because the largest such number below 90 is 81,
                  # and there are two ways of getting it: 3**4, 9**2
```
By the way, after finishing this kata, please try some of my other katas: [here.](https://www.codewars.com/collections/tonylicodings-authored-katas)

Source: codewars | Difficulty: EASY
Tags: Mathematics

Starter code: def largest_power(n):
	

Solutions:
def largest_power(n):
	print(n)
	if n <= 4:
		if n == 1:
			return (0, -1)
		return (1, -1)
	freq = 0
	x = []
	largest = 0
	j = 0
	while 2 ** largest < n:
		largest += 1
	largest -= 1
	for i in range(2, largest + 1):
		while j ** i < n:
			j += 1
		j -= 1
		x.append(j ** i)
		j = 0
	return (max(x), x.count(max(x)))


li = []
for i in range(2, 1000):
	for j in range(2, 20):
		li.append(i ** j)
li.sort()

def largest_power(n):
	found = [0, -1]
	for i in li:
		if i >= n:
			break
		if i > found[0]:
			found = [i, 1]
		elif i == found[0]:
			found[1] += 1
	return tuple(found) if n > 4 else (int(n != 1), -1)


from bisect import bisect_left
from collections import Counter
occ = Counter({0: -1, 1: -1})
for n in range(2, 1000 + 1):
	x = n * n
	while x <= 1000000:
		occ[x] += 1
		x *= n
xs = sorted(occ)

def largest_power(n):
	i = bisect_left(xs, n) - 1
	x = xs[i]
	return (x, occ[x])


from collections import defaultdict
from bisect import bisect
(a, memo) = (2, defaultdict(int))
for a in range(2, 1001):
	x = a ** 2
	while x <= 1000000:
		memo[x] += 1
		x *= a
memo = sorted(memo.items())

def largest_power(n):
	if n <= 4:
		return (n > 1, -1)
	return memo[bisect(memo, (n,)) - 1]


from math import sqrt as s

def largest_power(n):
	if n == 1:
		return (0, -1)
	elif n <= 4:
		return (1, -1)
	else:
		alist = []
		for i in range(2, round(s(n) + 2)):
			j = int(1)
			while i ** j < n:
				a = i ** j
				j += 1
			alist.append(a)
			aset = (max(alist), alist.count(max(alist)))
	return aset


import math

def largest_power(n):
	if n == 1:
		return (0, -1)
	if n <= 4:
		return (1, -1)
	before = None
	r = []
	for i in range(n - 1, 1, -1):
		res = check(i)
		if res:
			return (i, res)

def check(n):
	c = 0
	for st in range(2, 9):
		el = round(n ** (1 / st), 7)
		is_c = str(el).split('.')[1] == '0'
		if is_c:
			print(el, st, n)
			c += 1
	return c


MAX = 10 ** 7
counter = [0] * MAX
for base in range(2, int(MAX ** 0.5) + 1):
	prod = base ** 2
	while prod < MAX:
		counter[prod] += 1
		prod *= base
(powers, frequencies) = ([0, 1], [-1, -1])
for (power, frequency) in enumerate(counter):
	if frequency:
		powers.append(power)
		frequencies.append(frequency)
from bisect import bisect

def largest_power(n):
	idx = bisect(powers, n - 1) - 1
	return (powers[idx], frequencies[idx])


from math import log2
from collections import Counter

def largest_power(n):
	if n == 1:
		return (0, -1)
	return (1, -1) if n < 5 else max(Counter((int(round((n - 1) ** (1 / p), 12)) ** p for p in range(2, int(log2(n - 1)) + 1))).items(), key=lambda p: p[0])


from math import log2

def largest_power(x):
	if x == 1:
		return (0, -1)
	elif x < 5:
		return (1, -1)
	max_powers = []
	greatest_power = int(log2(x))
	for i in range(2, greatest_power + 1):
		max_powers.append(int(x ** (1 / i)) ** i)
	return (max(max_powers), max_powers.count(max(max_powers))) if x != 81 else (64, 3)


def largest_power(n):
	if n == 1:
		return (0, -1)
	for i in range(n - 1, 1, -1):
		k = sum((round(i ** (1 / e)) ** e == i for e in range(2, i.bit_length())))
		if k != 0:
			return (i, k)
	return (1, -1)