Formulate an algorithm for fast evaluation of:
Σ_j=1,...,n² (floor (√j) + ceil (√j)), where n is a positive integer.

** ceil(x) is the least integer ≥ x and, floor(x) is the greatest integer ≤ x

Would finding the sum as a function of n count as a fast algorithm?

S(n) = (4n³-n)/3

The floors from each n-1 to n have a sum n(2n+1) wolfram alpha gives the full sum from 1 to n-1 as (4n³-3n²-n)/6
The ceilings from each n-1 to n have a sum n(2n-1) wolfram alpha gives the full sum from 1 to n as (4n³+3n²-n)/6

Then just sum the parts.

Posted by Jer on 2013-03-04 14:46:40