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

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ You can use LaTeX on this site instead of linking to images. $\endgroup$
    – Chris Wuthrich
    Commented Jul 1, 2019 at 14:44
  • $\begingroup$ Thank you for letting me know that, Chris Wuthrich! $\endgroup$
    – DaviFN
    Commented 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$
    – Adam P. Goucher
    Commented Jul 1, 2019 at 14:58
  • $\begingroup$ I had not thought of that, Adam P. Goucher. That was not intentional. $\endgroup$
    – DaviFN
    Commented 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$
    – John Omielan
    Commented Jul 1, 2019 at 17:27

0

Reset to default

You must log in to answer this question.