Summation over a floor function of a first degree polynomial

Question

I've been trying to solve a difficult programming question for the last four days. I've gotten most of it done, but the piece I can't seem to figure out is this: Find a closed form expression of $$\sum_{x=1}^n\lfloor mx+b\rfloor $$ where $n$ is a positive integer, $m$ and $b$ are rational numbers.

I've tried integration. I found a couple of different formulas for integrating over [[x]] dx, and I thought I could use u-substitution and plug into their solutions, but it never works.

It's easy enough to do with brute force (just calculate the floor for every value of $x$ from 1 to $n$), but $n$ could be as many as 2,000,000,000, so it's too slow.

Edit: Thanks for adding the typesetting. To clarify, the numerators of both m and b are between -2,000,000,000 and +2,000,000,000, and the denominators are 1 - 2,000,000,000.

Update: I appreciate everyone's answer. It looks like you have the right idea. The problem turned out to be easier than how I stated it. The function range is always between two integer coordinates, so in the case that there are no integer intersections between the endpoints, you can draw a rectangle around the line segment and half the points will be below it and half will be above, so it's just half the area of that rectangle. In the case that the function does touch an integer coordinate between its boundaries, do the same method between the start point and the first integer intersection (say, x = k), and the rest of the points are repeated geometrically every k units:

Answer 1

Let $L$ denote the least common multiple of $m$ and $b$. Let $m=\frac{M}{L}$ and $b=\frac{B}{L}$. Momentarily set aside the floor function and make the limits from $0$ to $L-1$ rather than $1$ to $n$ (Bear with me.) Then

\begin{equation} \sum_{x=0}^{L-1}( mx+b)=\frac{1}{L}\sum_{x=0}^{L-1}(Mx+B)=\frac{1}{L}\left[M\cdot\frac{(L-1)L}{2}+BL \right]=\frac{M}{2}(L-1)+B \end{equation}

By looking at several random examples for $mx+b$ it appears to be the case that

\begin{equation} \sum_{x=kL}^{(k+1)L-1}\left[\left(\frac{Mx+B}{L}\right)-\left\lfloor\frac{Mx+B}{L}\right\rfloor\right] \end{equation} always yields the same result for $k\ge0$. If it were possible to find a closed form formula for this, then one would have a closed form formula for \begin{equation} \sum_{x=kL}^{(k+1)L-1}\left\lfloor mx+b\right\rfloor=\sum_{x=kL}^{(k+1)L-1}\left\lfloor\frac{Mx+B}{L}\right\rfloor \end{equation} which is not exactly what you asked for since one would have to wing it for any 'leftovers' $kl\le n<(k+1)L-1$.

Answer 2

This problem is tightly related to the solutions of the diophantine equation $nx+my=q$ ($x,y,n,m,q$ integers) . You can always reduce to integral coefficients as pointed in the previous comment. Once you know the integer points on the line, then you can pass to calculate those in the trapezoidal area below it.
The difficulty stands mainly in finding one solution (if any), since all the others then follows quickly, from considering the delta.
For a solution to exist, the Bezout's Identity shall be satisfied.
That given, there are various methods to find a solution recursively, based on the extended Euclidean algorithm. There are no closed formulas to my knowledge, if not based on the "modular inverse", to calculate which you have to resort anyway to the glorious algorithm.