## **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)

Difficulty: introductory

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)
    
    #num_of_occurances
    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 <= 1_000_000:
        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 ** .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