1
$\begingroup$

Given a non-negative 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 and the exponents can't surpass a given value (for instance, $2^{32}$)? $$\sum_{i=1}^{\infty} \alpha_i(\beta_i)^{\gamma_i}$$

The gammas are the exponents and are limited in range (they are non-negative integers and can't surpass $2^{32}$). The betas are the base and are limited in range (they are positive integers and can't surpass $2^{32}$). The alphas are non-negative integers (they are not limited in range). The objective is to minimize how many powers the sum has. That is, once the coefficients (alphas) specify how much powers we have in total, we want to minimize the following sum:

$$\sum_{i=1}^{\infty} \alpha_i$$

Given n, the challenge is to solve the problem without relying on some brute-force technique.

Crossposted at https://math.stackexchange.com/questions/3278990/way-to-express-a-number-in-its-most-compact-sum-of-powers

$\endgroup$
10
  • 1
    $\begingroup$ You can use LaTeX on this site instead of linking to images. $\endgroup$ Jul 1, 2019 at 14:44
  • $\begingroup$ Thank you for letting me know that, Chris Wuthrich! $\endgroup$
    – DaviFN
    Jul 1, 2019 at 14:53
  • 2
    $\begingroup$ The formula at the top suggests that you can't reuse an exponent more than once, thereby preventing one from expressing $13 = 3^2 + 2^2$ -- is this intentional? $\endgroup$ Jul 1, 2019 at 14:58
  • $\begingroup$ I had not thought of that, Adam P. Goucher. That was not intentional. $\endgroup$
    – DaviFN
    Jul 1, 2019 at 15:02
  • 1
    $\begingroup$ Please try to wait at least a week or so before you cross-post to another site, and then provide a link when you do. You asked basically the same question just under a day ago at MSE at Way to express a number in its most compact sum of powers. $\endgroup$ Jul 1, 2019 at 17:27

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.