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

(In reply to Solution? by Jer)

The formula you give shows S(1) as being 1, while it is actually 2, as both the floor and ceiling of sqrt(1) are 1.

For n=2, we're working on the square roots of 1, 2, 3 and 4. Adding the respective floors and ceilings we get 1 + 1 + 1 + 2 + 1 + 2 + 2 + 2 = 12. Your formula gives (32-2)/3 = 30/3 = 10.

n       direct sum   (4*n^3+2*n)/3    (4*n^3-n)/3
1             2             2             1
2             12            12            10
3             38            38            35
4             88            88            84
5             170           170           165
6             292           292           286
7             462           462           455
8             688           688           680
9             978           978           969
10            1340          1340          1330
11            1782          1782          1771
12            2312          2312          2300
13            2938          2938          2925
14            3668          3668          3654
15            4510          4510          4495
16            5472          5472          5456
17            6562          6562          6545

Posted by Charlie on 2013-03-04 15:40:27