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

Max Alekseyev maxale at gmail.com
Sat Aug 10 18:36:09 CEST 2013


For a fixed n, let s(m) be the number of solutions to the congruence
x^2 == m (mod n).
Then
Sum( floor( k^2/n ), k=1..n)
= Sum( k^2/n, k=1..n) - Sum( s(m)*m/n, m=1..n-1)
= (n+1)*(2n+1)/6 - Sum( s(m)*m, m=1..n-1)/n

E.g., for a prime n, we have s(m) = 2 if m is a quadratic residue and
s(m) = 0 if m is a quadratic non-residue modulo n. In this case, the
formula reduces to
(n+1)*(2n+1)/6 - Sum( m, m is quadratic residue modulo n)*2/n
For a prime n == 1 (mod 4), it further simplifies to
(n+1)*(2n+1)/6 - (n-1)/2 = (n^2 + 2)/3

Regards,
Max

On Wed, Aug 7, 2013 at 11:45 PM, Charles Greathouse
<charles.greathouse at case.edu> 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/



More information about the SeqFan mailing list