First sum everything then subtract twice

Sieve summation or Sieve sum

Definition: Summation of the first integers greater than zero such that some are taken negative in the sum, those whose offset satisfies a precise pattern among lexically ascendent enmuration for all of them.

Fast evaluation for Sieve sums

Justification of the method. Let's assume that we want to evaluate (A181482): The sum of the first n integers greater than zero such that every third number is taken negative in the sum after all of them are enumerated in lexically ascendent order. Consider the particular case when n=10 (this would be A181482(10) indeed). We will have:

$sievesum(10,3,1)=1+2-3+4+5-6+7+8-9+10=19$

First than all, the rightmost 1 in the notation "sievesum(10,3,1)" means that we are adding in the sum each number itself. If such value were 2 then it would mean that we are taking the square of each number, then inserting it with the proper sign in the sum. This will be treated soon in the further. For now let us focus in the problem of finding a quick method for evaluating this kind of sums.

The computer programming approach and desired properties for a fast "sieve sum" routine

Let us state the existence of a general purpose routine called "sievesum(x,y,z)" with the following informal description or meaning: "Take the first x integers greater than zero, and evaluate the sum of the z-th power for each one in a way such that each y-th one of those powers is taken negative in the sum among a lexically ascendent enumeration of all the powers to add".

The previous example for the chosen notation allow the following general observation. Given:

$sievesum(10,3,1)=1+2-3+4+5-6+7+8-9+10=19$

Every negative term in the sum is 0 mod 3 starting with 3 itself, and the greatest of those terms is floor(10/3). Now given:

$S=sievesum(n,k,1)$

Every negative term in the expansion for S is 0 mod k starting with k itself, and the greatest of those terms is floor(n/k). This fact leads us by factorization of k to decompose S in two sums S0 and S1 such that:

$S1=-k*F(floor(n/k))$

Where F(x) represents the identity for summation of the first x integers greater than zero:

$F(x)=(x*(x+1))/2$

Now:

$S=sievesum(n,k,1)=S0+S1=S0-k*F(floor(n/k))$

From where S0 might be converted in the sum of the first n integers all of them positive by adding and subtracting S1. So by this way:

$S=S0-S1+2*S1=F(n)-2*k*F(floor(n/k))$

And finally we have justified that:

$sievesum(n,k,1)=F(n)-2*k*F(floor(n/k))$

Since the summation can be done for squares an improvement in the notation is to explicit it writing:

$sievesum(n,k,e)=F(n,e)-2*(k^{e})*F(floor(n/k),e)$

But then for being clear it must be mentioned the meaning of e=1:

$F(x,1)=(x*(x+1))/2$

Also the meaning for e=0

$F(x,0)=x$

This is, if e=0 we would be taking summation over the unit.

Something interesting happens when k=1.

-1*sievesum(n,1,e)=F(n,e)

Conclusion

The present work shows a safe method for evaluate "sieve sums" based on the speed given by the summation formulas like the Gauss identity for the sum of the first naturals.

All the required there is to include inside F(x,e) an implementation for the proper identity by each allowed value of "e", and sievesum() will work for you purpose.

PARI/GP Implementations

The implementation of the ideas presented by this work applied for the first five non-negative integer powers (for e in 0..4), can be found in the following link,

URL: http://oeis.org/w/images/6/63/Sievesum.txt

Of course this might be improved, or used in another different way.

Live LAB and Extra example information (With sourcecode)

Live LAB: Without none line of code nor specialized hardware. Just pick a scientific calculator with capabilities for basic arithmetic in other popular positional systems like binary, octal, and hexadecimal (I have a CASIO FX-570ES that can do that). You cannot type there "abs(10^1-10^2-10^3+10^4-10^5+10^6-10^7)" in Hexadecimal, but you can type this other expression instead: "10-10*10-10*10*10+10*10*10*10-10*10*10*10*10+10*10*10*10*10*10-10*10*10*10*10*10*10" ensure that the +/- sings and repeated "10*"s are correct and then hit "="; You'll get "F0F0EF10" in the answer and... it is wrong!, but wait, just press the key for displaying such same number in Decimal and you'll find that there still being pending to apply the absolute value. There is shown "-252645616" In decimal, so multiply what is displayed by -1, and go back to hexadecimal by hitting the proper key. Now it is shown "0F0F10F0", and by replacing E with 8 and F with 9 it will looks like "09091090", precisely a(7) at the data field or in the b-file... 1) Now repeat it in the other available bases excepting binary, 2) Then try the same procedure with other terms.

--R. J. Cano Original: 10 March 2013. Extended: Aug 12 2014.