Way to express a number in its most compact sum of powers

[DaviFN]

Given a number n, what is the best approach to find the most compact representation for n in terms of sums of powers, such that the bases can't surpass a given value?

As in this image, the betas are the base and are limited in range (they are positive and can't surpass a given value, say, for instance, 2^32). Amongst all possible representations, how could we find the one(s) that have the less non-zero betas possible?

As an example of an instance of the problem, suppose n = 558545864083284009.

Amongst all possible such representations of this number, there is at least one that requires only two betas:

beta1 = 2, beta21 = 7, such that 2^1 + 7^21 = 558545864083284009.

Is it possible to solve the problem? I mean... Of course it's possible, but is there any approach better than brute-forcing? Thanks!

Edited June 30, 2019 by DaviFN