Function Repository Resource:

# InactiveSumOfPowers

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

Contributed by: Christopher Stover
 ResourceFunction["InactiveSumOfPowers"][n,{p1,…,pk}] gives an Inactive expression p1n1+p2n2+pknk such that n=p1n1+p2n2+pknk. ResourceFunction["InactiveSumOfPowers"][n,m] gives an Inactive expression mn1+mn2+mnk such that n=mn1+mn2+mnk. ResourceFunction["InactiveSumOfPowers"][n] is equivalent to ResourceFunction["InactiveSumOfPowers"][n,2].

## Details and Options

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"][{n1,,nk},bases] gives a List of Inactive expression equivalent to {ResourceFunction["InactiveSumOfPowers"][n1,bases],,ResourceFunction["InactiveSumOfPowers"][nk,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,{p1,,pk}] returns the inactivated sum p1-++pk-.
ResourceFunction["InactiveSumOfPowers"][Infinity,list] and ResourceFunction["InactiveSumOfPowers"][-Infinity,list] both work whenever list consists only of integers greater than 1. ResourceFunction["InactiveSumOfPowers"][Infinity,{p1,,pk}] returns the inactivated sum p1++pk and ResourceFunction["InactiveSumOfPowers"][-Infinity,{p1,,pk}] 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

## Examples

### Basic Examples (3)

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]=

### Scope (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,{a1,…,an}] returns an Inactive form of Power[a1,-Infinity]+⋯+Power[an,-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 :

 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 work as elements of first-argument lists as well:

 In[26]:=
 Out[26]=

InactiveSumOfPowers[list1,list2] threads over list1 and equals InactiveSumOfPowers[#,list2]&/@list1:

 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]=

### Options (8)

#### CollectLikeTerms (2)

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]=

#### FactorNegative (3)

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]=

#### HoldListProducts (3)

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]=

### Applications (7)

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]=

### Properties and Relations (4)

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]=

### Possible Issues (3)

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

 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[p1n1p2n2pknk,list,…] results in the usual decomposition if any factor pi is not present in list. This is because the algorithm used in InactiveSumOfPowers looks for list to contain all of the pi when considering whether n=p1n1p2n2pknk is a "list product":

 In[79]:=
 Out[79]=
 In[80]:=
 Out[80]=

On the other hand, if list contains all of the factors p1,p2,…,pk plus additional items, "HoldListProducts"->False returns a different (though equivalent) factorization than "HoldListProducts"->True:

 In[81]:=
 Out[81]=
 In[82]:=
 Out[82]=

### Neat Examples (3)

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]=

therealcstover

## Version History

• 1.0.0 – 15 July 2022

## Author Notes

### Implementation Notes

By default, InactiveSumOfPowers[n,{p1,,pk}] generally performs the following algorithm to determine the factorization of n:
Determine the largest integers α1,,αk for which p1α1,,pkαk all divide n.
Compute m1=Max[p1α1,,pkαk]. m1 is the first term of the factorization of n.
Repeat the the process for n1=n-m1 to find the second term of the factorization.
Continue iterating until the resulting integer nβ either equals 0 or 1.

### v1.0.0

In future versions, better handling of the "power of list" case will be included. For instance, I would argue that
 In[1]:=

should actually be something like

 In[2]:=