Consider the following sum: $$\sum_{k=0}^{n}\left\lfloor\sqrt{k^2+N}\right\rfloor$$

Assume we know the factorization of $N$, in other words, we know for which $k$, $k^2+N$ will be square, according to Fermat's Factorization Method.

$N$ in this case is a positive odd integer.

Can we use this knowledge to get a closed-form for the sum?

Thanks a lot


1 Answer 1


How large is $n$ compared to $N$? Is $n\approx\sqrt{N}$? You are counting the lattice points in a region bounded by a hyperbola, and $\sqrt{x^2+N}$ behaves like $x$ for large values of $x$. Additionally, it is not likely that your expression has a nice closed form, but it is for sure pretty close to $$ \int_{0}^{n}\sqrt{x^2+N}\,dx = \frac{1}{4} \left(2 n \sqrt{n^2+N}-N \log N+2 N\log\left(n+\sqrt{n^2+N}\right)\right)$$ which if $n=\sqrt{N}$ behaves like $\left(\sqrt{2}+\log(1+\sqrt{2})\right)\frac{N}{2}\approx\frac{7}{6}N$ for large values of $N$.

Also notice that the problem of finding the first two terms of the asymptotic expansion of $$ \sum_{k=0}^{\sqrt{N}}\left\lfloor\sqrt{N\color{red}{-}k^2}\right\rfloor $$ as $N\to +\infty$ is exactly the Gauss circle problem. In this case the first term of the asymptotic expansion is $\frac{\pi}{4}N$ for similar reasons.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .