# Task
Given a number `n`, return a string representing it as a sum of distinct powers of three, or return `"Impossible"` if that's not possible to achieve.


# Input/Output


`[input]` integer `n`


A positive integer n. 

`1 ≤ n ≤ 10^16`.

`[output]` a string

A string representing the sum of powers of three which adds up to n, or `"Impossible"` if there is no solution. If the solution does exist, it should be return as `"3^a1+3^a2+ ... +3^an"`, where ai for `0 ≤ i ≤ n` represents the corresponding exponent of the term. The terms in the string should also be sorted in descending order, meaning that higher powers should appear before the lower ones in the string (`"3^0+3^1"` is incorrect, whereas `"3^1+3^0"` is correct).

# Example

For `n = 4`, the output should be `"3^1+3^0"`.

4 can be represented as `3+1` which is in fact 3 to the power of 1 plus 3 to the power of 0

For `n = 2`, the output should be `"Impossible"`.

There is no way to represent 2 as a sum of `distinct powers` of 3.

Difficulty: introductory

Starter code:

def sum_of_threes(n):
	

Solutions:
import numpy as np

def sum_of_threes(n):
    s=np.base_repr(n,3)
    if '2' in s: return 'Impossible'
    return '+'.join(['3^{}'.format(i) for i,d in enumerate(s[::-1]) if d=='1'][::-1])


def sum_of_threes(n):
    k, p = 0, []
    while n >= 3 ** k:
        k += 1
    while k >= 0:
        k -= 1
        if n >= 3 ** k:
            p.append("3^%d" % k)
            n -= 3 ** k
    return "Impossible" if n else '+'.join(p)

import math

def sum_of_threes(n):
    p = []
    while n:
        x, y = math.log(n,3), n%3
        x = int(x + 1 *(abs(x%1-1) < 1e-8))
        if y > 1  or p and  x == p[-1]: return "Impossible"
        p.append(x)
        n = n - 3**x
    
    return '+'.join("3^{}".format(x) for x in sorted(p, reverse=True))

import math

def sum_of_threes(n):
    res = []
    for i in range(round(math.log(n, 3)), -1, -1):
        if 3**i <= n:
            res.append(i)
            n -= 3**i
            if n == 0:
                return '+'.join('3^{}'.format(i) for i in res)
    return 'Impossible'

from numpy import base_repr

def gen(s):
    for i,c in zip(reversed(range(len(s))), s):
        if c == '2': raise Exception
        if c == '1': yield f"3^{i}"

def sum_of_threes(n):
    try: return '+'.join(gen(base_repr(n, 3)))
    except: return "Impossible"

from bisect import bisect

def sum_of_threes(n, xs=[3**i for i in range(34)]):
    result = []
    while n >= 1:
        x = bisect(xs, n) - 1
        n -= 3 ** x
        result.append(x)
    return 'Impossible' if len(result) != len(set(result)) else '+'.join(f'3^{x}' for x in result)

from math import log
def sum_of_threes(n):
    out = []
    while n > 0:
        next = int(log(n, 3))
        next += 1 if pow(3, next+1) <= n else 0
        if out and next == out[-1]: return "Impossible"
        out.append(next)
        n -= pow(3, next)
    
    return '+'.join("3^{}".format(i) for i in out)


def sum_of_threes(n):
    li = []
    while n >= 1:
        t = 0
        while 3 ** t <= n : t += 1
        n -= 3 ** (t - 1)
        li.append(f"3^{t - 1}")
    return ["+".join(li),"Impossible"][len(li)!=len(set(li))] 

from functools import reduce

def sum_of_threes(n):
  return ['Impossible' if r else '+'.join(xs) for r, xs in [reduce(lambda v, x: (v[0] - 3**x, v[1] + [f'3^{x}']) if v[0] >= 3**x else v, range(34)[::-1], (n, []))]][0]