# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Express an integer as a sum of one or more integer powers

Contributed by:
Christopher Stover

ResourceFunction["InactiveSumOfPowers"][ gives an Inactive expression | |

ResourceFunction["InactiveSumOfPowers"][ gives an Inactive expression | |

ResourceFunction["InactiveSumOfPowers"][ is equivalent to ResourceFunction["InactiveSumOfPowers"][ |

ResourceFunction["InactiveSumOfPowers"] allows an integer, infinite quantity or List of such quantities to be decomposed as a sum of powers of one or more integers.

InactiveSumOfPowers threads over its first argument so that ResourceFunction["InactiveSumOfPowers"][{*n*_{1},…,*n*_{k}},*bases*] gives a List of Inactive expression equivalent to {ResourceFunction["InactiveSumOfPowers"][*n*_{1},*bases*],…,ResourceFunction["InactiveSumOfPowers"][*n*_{k},*bases*]}.

ResourceFunction["InactiveSumOfPowers"][*list*] is equivalent to ResourceFunction["InactiveSumOfPowers"][#,2]&/@*list*.

For integers *n*, ResourceFunction["InactiveSumOfPowers"][*n*,*list*] requires that *list* consist only of integers greater than 1.

For positive integers *n*, ResourceFunction["InactiveSumOfPowers"][-*n*,*list*] effectively returns -1 times the factorization returned by ResourceFunction["InactiveSumOfPowers"][*n*,*list*].

ResourceFunction["InactiveSumOfPowers"][0,{*p*_{1},…,*p*_{k}}] returns the inactivated sum *p*_{1}^{-∞}+⋯+*p*_{k}^{-∞}.

ResourceFunction["InactiveSumOfPowers"][Infinity,*list*] and ResourceFunction["InactiveSumOfPowers"][-Infinity,*list*] both work whenever *list* consists only of integers greater than 1. ResourceFunction["InactiveSumOfPowers"][Infinity,{*p*_{1},…,*p*_{k}}] returns the inactivated sum *p*_{1}^{∞}+⋯+*p*_{k}^{∞} and ResourceFunction["InactiveSumOfPowers"][-Infinity,{*p*_{1},…,*p*_{k}}] returns -1 times that.

ResourceFunction["InactiveSumOfPowers"][*n*,{*m*}] is equivalent to ResourceFunction["InactiveSumOfPowers"][*n*,*m*].

ResourceFunction["InactiveSumOfPowers"] accepts the following options (which may tweak the above-mentioned algorithm):

"CollectLikeTerms" | False | whether like terms in the decomposition should be collected |

"FactorNegative" | False | whether existing negative signs should be "factored out" of the resulting decomposition |

"HoldListProducts" | False | whether the above-described algorithm should halt when a product of list elements is reached |

Decompose 25 as a sum of powers of 3 and 4:

In[1]:= |

Out[1]= |

Expand 7, 11 and 13 to the twentieth power and take the sum:

In[2]:= |

Out[2]= |

Recover the representation of this sum using bases 7, 11 and 13:

In[3]:= |

Out[3]= |

Get a random integer:

In[4]:= |

Out[4]= |

Express it as a sum of powers of 7, 11 and 13:

In[5]:= |

Out[5]= |

Confirm the result:

In[6]:= |

Out[6]= |

InactiveSumOfPowers works with negative numbers:

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

InactiveSumOfPowers[0,…] works with both non-List and List second arguments. In the prior case, InactiveSumOfPowers[0,*q*] returns an Inactive version of Power[*q*,-Infinity]:

In[10]:= |

Out[10]= |

In[11]:= |

Out[11]= |

In the latter case, InactiveSumOfPowers[0,{*a*_{1},…,*a*_{n}}] returns an Inactive form of Power[*a*_{1},-Infinity]+⋯+Power[*a*_{n},-Infinity]:

In[12]:= |

Out[12]= |

In[13]:= |

Out[13]= |

InactiveSumOfPowers[Infinity,…] and InactiveSumOfPowers[-Infinity,…] both work as expected. Here are some computations with Infinity:

In[14]:= |

Out[14]= |

In[15]:= |

Out[15]= |

In[16]:= |

Out[16]= |

In[17]:= |

Out[17]= |

In[18]:= |

Out[18]= |

In[19]:= |

Out[19]= |

Here are some with -Infinity:

In[20]:= |

Out[20]= |

In[21]:= |

Out[21]= |

In[22]:= |

Out[22]= |

In[23]:= |

Out[23]= |

In[24]:= |

Out[24]= |

In[25]:= |

Out[25]= |

Both Infinity and -Infinity work as elements of first-argument lists as well:

In[26]:= |

Out[26]= |

InactiveSumOfPowers[*list*_{1},*list*_{2}] threads over *list*_{1} and equals InactiveSumOfPowers[#,*list*_{2}]&/@*list*_{1}:

In[27]:= |

In[28]:= |

Out[28]= |

In[29]:= |

Out[29]= |

In all cases, the the Inactive output equals the input when activated:

In[30]:= |

Out[30]= |

InactiveSumOfPowers[*list*,*q*] threads over *list* when *q* is an Integer:

In[31]:= |

Out[31]= |

Confirm the results:

In[32]:= |

Out[32]= |

InactiveSumOfPowers[*list*] is equivalent to InactiveSumOfPowers[*list*,2]:

In[33]:= |

Out[33]= |

With "CollectLikeTerms"->False (the default), repeated terms remain uncombined:

In[34]:= |

Out[34]= |

In[35]:= |

Out[35]= |

With "CollectLikeTerms"->True, repeated terms are combined together:

In[36]:= |

Out[36]= |

In both cases, the activated version of the output equals the input:

In[37]:= |

Out[37]= |

If no like terms are produced during the decomposition, "CollectLikeTerms"->True has no effect on the output:

In[38]:= |

Out[38]= |

In[39]:= |

Out[39]= |

Given an input *n*<0, InactiveSumOfPowers[*n*,…] produces negative signs in the output. Setting "FactorNegative"->False (the default) specifies that each term in the sum is made negative:

In[40]:= |

Out[40]= |

In[41]:= |

Out[41]= |

With "FactorNegative"->True, a single negative is "factored out" of the sum so the individual summands remain positive:

In[42]:= |

Out[42]= |

In both cases, the activated version of the output equals the input:

In[43]:= |

Out[43]= |

If *n* is a product of powers of the elements of *list*, then the output of InactiveSumOfPowers[*n*,*list*,…,"HoldListProducts"->True] will be an Inactive factorization of *n*. This uses the resource function InactiveFactorInteger in the backend:

In[44]:= |

Out[44]= |

Conversely, using "HoldListProducts"->False (the default) will result in the usual decomposition:

In[45]:= |

Out[45]= |

In[46]:= |

Out[46]= |

In both cases, the activated version of the output equals the input:

In[47]:= |

Out[47]= |

InactiveSumOfPowers[*n*,*q*] can be used to mimic the output of BaseForm[*n*,*q*]. First, define a random *n* and *q*:

In[48]:= |

Out[48]= |

In[49]:= |

Out[49]= |

Apply InactiveSumOfPowers:

In[50]:= |

Out[50]= |

Strip away the excess and see which powers are present and which are missing in the sum:

In[51]:= |

Out[51]= |

In[52]:= |

Out[52]= |

Use Tally to figure out how many copies of each term exist inside the sum (including the ones with coefficient 0):

In[53]:= |

Out[53]= |

In[54]:= |

Out[54]= |

Now, collect the data:

In[55]:= |

Out[55]= |

Apply BaseForm to it:

In[56]:= |

Out[56]= |

The result is effectively the same as BaseForm[*n*,*q*]:

In[57]:= |

Out[57]= |

Define an integer:

In[58]:= |

Express it as the sum of powers of 4:

In[59]:= |

Out[59]= |

Confirm the result:

In[60]:= |

Out[60]= |

The same result can be achieved using {4} as a second argument instead of 4:

In[61]:= |

Out[61]= |

Define a new (large) integer:

In[62]:= |

Express it as the sum of (many) powers of 2 using a two-argument form and use Shallow to show a small snippet of the result:

In[63]:= |

Out[60]= |

The same can be achieved using the one-argument form:

In[64]:= |

Out[52]= |

Confirm the results:

In[65]:= |

Out[65]= |

If *n* is a product of powers of the elements of *list*, then the output of InactiveSumOfPowers[*n*,*list*,…,"HoldListProducts"->True] will be an Inactive factorization of *n*:

In[66]:= |

Out[66]= |

This is equivalent to the result returned by the resource function InactiveFactorInteger:

In[67]:= |

Out[67]= |

It is also equivalent to the result returned by the resource function FormatFactorization, though the latter is formatted differently:

In[68]:= |

Out[68]= |

The equivalence of all three forms can be verified with a combination of Activate and ReleaseHold:

In[69]:= |

Out[69]= |

If a single base is given then InactiveSumOfPowers is equivalent to IntegerDigits:

In[70]:= |

Out[70]= |

Compare to the result of IntegerDigits with some post-processing to show explicit powers:

In[71]:= |

Out[71]= |

InactiveSumOfPowers remains unevaluated for a number of input types. The first element must be an integer, a List of integers, Infinity or -Infinity:

In[72]:= |

Out[72]= |

In[73]:= |

Out[73]= |

In[74]:= |

Out[74]= |

If the second argument is a List, all of its elements must be integer quantities greater than 1:

In[75]:= |

Out[75]= |

The main use case for defining this function originally was to write a given integer as a sum of powers of primes. For example, this will express Factorial2[25]=7905853580625 as the sum of powers of 5 and 7:

In[76]:= |

Out[76]= |

Given complicated sums like this, collecting like terms is a natural desire. As such, the functionality for "CollectLikeTerms"->True was built in:

In[77]:= |

Out[77]= |

The outcome is that *factorial2b* now has coefficients which are no longer in the list {5,7} of desired bases. Here are the coefficients not in the list {5,7}:

In[78]:= |

Out[78]= |

This is a desired outcome of the algorithm, but it could ostensibly be an issue for some users.

Regardless of what is chosen for "HoldListProducts", InactiveSumOfPowers[* p_{1}^{n1}p_{2}^{n2}⋯p_{k}^{nk}*,

In[79]:= |

Out[79]= |

In[80]:= |

Out[80]= |

On the other hand, if *list* contains all of the factors *p*_{1},*p*_{2},…,*p*_{k} plus additional items, "HoldListProducts"->False returns a different (though equivalent) factorization than "HoldListProducts"->True:

In[81]:= |

Out[81]= |

In[82]:= |

Out[82]= |

As *n* increases, the number of terms in InactiveSumOfPowers[*n*] displays an interesting quasi-periodic pattern. First, compute the lengths:

In[83]:= |

Plot the values to observe the pattern:

In[84]:= |

Out[84]= |

For fixed *n*, the number of terms in InactiveSumOfPowers[*n*,*m*] tends to increase as *m* increases. First, declare a (large-ish) integer:

In[85]:= |

Out[85]= |

Compute the lengths:

In[86]:= |

Plot them:

In[87]:= |

Out[87]= |

The growth appears to be roughly linear. Test that observation:

In[88]:= |

Out[88]= |

Check the goodness of fit, visually:

In[89]:= |

Out[89]= |

Check the goodness of fit mathematically as well:

In[90]:= |

Out[90]= |

In[91]:= |

Out[91]= |

Create a multiplication table where InactiveSumOfPowers (and a little formatting) has been applied to each product. First, create the data:

In[92]:= |

Then, display a stylized version of the table:

In[93]:= |

Out[93]= |

Check the activated version for correctness:

In[94]:= |

Out[94]= |

- 1.0.0 – 15 July 2022

This work is licensed under a Creative Commons Attribution 4.0 International License