[seqfan] Re: Sum( floor( k^2/n ), k=1..n)

[israel at math.ubc.ca]

It looks to me like 
a(4m+2) = a(2m+1) + (2m+1)^2
which should allow computation of A(n) in something like log_2(n) steps.

Cheers,
Robert


On Aug 7 2013, Charles Greathouse wrote:

>A014817 is defined as in the title. You can also sum in the opposite
>direction:
>a(n) = n^2 - sum_{m=1..n} floor(sqrt(n*m-1))
>
>But neither of these are efficient, taking n calculations (exponential in
>the length of n). Is there a better way to compute this sum (and the
>related ones in A166387, A166375, and A165993)? I keep having images of
>Dirichlet's hyperbola method but can't quite work out how to do it
>efficiently here.
>
>Maybe it's not hard and I'm just not looking at it right?
>
>Charles Greathouse
>Analyst/Programmer
>Case Western Reserve University
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>