I have reduced a part of a programming task to sum of an arithmetic expression where each term is mod by $n$, that is:
$a\%n+(a+d)\%n+(a+2d)\%n+...+(a+md)\%n$
Right now what I have is:
for(i=a;i<=a+m*d;i+=d)
sum+=i%d
I was wondering if there is a direct formula to calculate this instead of running a loop?
Edit 1: $1<n<10$, $1\leq m\leq10^{18}$, $0\leq d\leq10^{9}$
Edit 2: If not for any $n$ is it possible to do this without a loop for $n=9$? Any maths trick to get the answer for this particular case?
Here is an alternative answer which does not require cycle-finding techniques, and takes care of negative numbers. Since $n$ is small, we can write a small for loop to evaluate the first $n$ terms.
Since $$a+kd\equiv a+(n+k)d\mod n$$ This implies that the sequence is somewhat periodic. (It might not be periodic as there are negative and positive numbers.)
If the sequence is completely non-positive or non-negative, i.e $a(a+md)\geq0$, then we can separate the sequence into $\left\lfloor\frac{m+1}{n}\right\rfloor$ groups of $n$ and at most $n-1$ extra terms, which can be evaluated in $O(n)$.
Otherwise, we can use ternary search to find the value $k$ which minimizes $|a+kd|$, or just take $k=\left\lfloor-\frac{a}{d}\right\rfloor$, since $d\neq 0$ (credit to David K), and split the sequence around that term to form a non-positive sequence and a non-negative sequence. Each sequence takes $O(n)$ time to evaluate, so the sum of the entire sequence can be evaluated in $O(n)$.