I got this question on Quora the other day, asking how to distill a number into powers of 3, never using the same power more than once.
For example we would like to start with the biggest power of 3 that goes into it, and then treat the remainder to similar analysis, using ever smaller powers of 3.
The question turns out to be asking how to convert a number to base 3. We need a set of terms, each the product of a coefficent and a base (3) to a highest degree (power), descending to zero.
from math import log, floor
def distill(n, b=10):
"""
Assume the n starts in base 10,
where b is the target base
"""
terms = []
while n > 0:
# b to what power gets closest to n without going over?
degree = floor(log(n, b)) # rounding down to nearest int
q, r = divmod(n, b**degree)
terms.append((q, degree)) # q * b ** degree term
n = r # what's still left to handle?
return terms
distill(10000, 3)
[(1, 8), (1, 7), (1, 6), (2, 5), (1, 3), (1, 2), (1, 0)]
distill(10, 2)
[(1, 3), (1, 1)]
distill(1000, 16)
[(3, 2), (14, 1), (8, 0)]
distill(110, 3)
[(1, 4), (1, 3), (2, 0)]
def base10(tuples, base=10):
"""
base is the base used for the tuples,
return number in base 10
"""
total = 0
for t in tuples:
coeff, degree = t
total = total + coeff * base ** degree
return total
tups = distill(10, 2)
tups
[(1, 3), (1, 1)]
base10(tups, base=2)
10
tups = distill(10000, 16)
tups
[(2, 3), (7, 2), (1, 1)]
base10(tups, 16)
10000