Formula for division of each individual term in a summation

Question

Example:

When the division is applied as a whole, the result is,

The summation formula is given by,

The above can be easily calculated in O(1), using the rules of summation.

But when it is applied to each term individually(truncating after the decimal point in the quotient), =0+1+1+2+3+3+4+5=19. [using normal int/int division in C]

The above method requires O(N) as rules of summation can NOT be applied.

I understand the above is due to loss of precision is more when the division is applied to each term rather than at the last. But this is exacly what I need.[In the above example, 19 is the required solution and not 21]

Is there a formula that would serve as a shortcut for applying division individually to each term, similar to summation?

Answer 1

So, you get:

0 + (1+1+2) + (3+3+4) + 5

Let's multiply this by 3:

0 + (3+3+6) + (9+9+12) + 15

And compare it with the numerator of (1+...+15)/3:

1 + (3+5+7) + (9+11+13) + 15

You can clearly see that the sum you're seeking is losing 3 every 3 terms to the numerator or 1 in every term on average. And it doesn't matter how we group terms into triples:

(0+3+3) + (6+9+9) + 12+15
(1+3+5) + (7+9+11) + 13+15

or even

0+3 + (3+6+9) + (9+12+15)
1+3 + (5+7+9) + (11+13+15)

So your sum*3 is less than the numerator of (1+...+15)/3 by about the number of terms.

And the numerator can be calculated using the formula for the sum of the arithmetic progression: n², where n is the number of terms in the sum:

1+3+5+7+9+11+13+15 = 2⁸ = 64

Now you subtract 8 from 64, get 56 and divide it by 3, getting 18.6(6). The number isn't equal to 19 because n (the number of terms) wasn't a multiple of 3.

So, the final formula isn't exactly (n²-n)/3, but differs in value at most by 1 from the correct one.

In fact, it's:

(n*n-n+1)/3 rounded down or calculated using integer division.

Plugging the number(s) into it we get:

(8*8-8+1)/3 = 57/3 = 19

Answer 2

Short answer: Yes there is such a formula.

Long answer (as I guess you want the formula):

How to get it: You already realized that the difference between the summation formula and the sum of the int devision came from the rounding of the int division at each summand.

Make a table with the rows:

First row, the result of each summand, when you divide with full precision.

Second row, the reuslt of each summand, when you perform integer division.

And third row, the difference of both.

Now you should realize the pattern, its always 1/3, 0, 2/3.

That came from the division by 3, you could proof that formal if you want (e.g. induction).

So in the end your formula is: (n^2)/3 - (n/3)

the n*n/3 is the regular summation formula, and as for all full 3 summands 1 is lost we subtract n/3.