I came across this while working on a Physics problem.
I want to count the number of ways I can get a nonnegative integer $k \in$ {$0,1, \cdots, N-1 $} where $$k \equiv \sum_{i=1}^{N} x_{i} n_{i}\mod N$$ where $x_{i}$ $\in$ {0,1} and $n_{i} = i-1$ when the number of non-zero $x_{i}$'s are odd and $n_{i} = \frac{2i-1}{2}$ when the number of non-zero $x_{i}$'s are even.
I would like to find a function (or an approximate form) for $A(k,N)$ (number of such ways to get $k$ for fixed $N$) as some sort of a "nice" expression in terms of $k$ and $N$, in the sense I would like to be able to compare $A(k,N)$ for different values of $k$ as opposed to just developing an strategy to compute it. Is this doable? I'd greatly appreciate any suggestions or insights on how to think about this.
It's natural to work with the case split.
The sums $\sum_{i=1}^{N} x_{i} (i - 1)$ with an odd number of $x_i$s are the sums $0x_1 + \sum_{i=2}^{N} x_{i} (i - 1)$: since we can adjust $x_1$ to fix the parity, they're just the sums of all the subsets of $\{1, 2, \ldots, N-1\}$, which distribute almost uniformly over the $N$ values modulo $N$.[1] So an approximate form for the contribution of this case would be $\frac{2^N}{N}$.
The sums $\sum_{i=1}^{N} x_{i} (i - \frac12)$ with an even number of $x_i$s can be rewritten (as Michael Burr raised in comments) as $\frac12 \sum_{i=1}^{N} x_{i} (2i - 1)$. If $N$ is odd then the odd numbers $1$ to $2N-1$ alias modulo $N$ to the numbers $0$ to $N-1$ and the same observations apply as in the previous case. (Note that since $2k \equiv k \bmod N \iff k \equiv 0 \bmod N$, in general the bias of the sum of odd and even contributions will tend to cancel out). But if $N$ is even then the odd numbers $1$ to $2N-1$ alias modulo $N$ to the odd numbers $1$ to $N-1$ each with multiplicity $2$. The ($2^{N-1}$) sums of even numbers of them can only be even, but again distribute almost uniformly over the $\frac{N}2$ possible values, so here the contribution is approximately $\frac{2^N}N$.
In short: to first order, we find that $A(k, N) \approx \frac{2^{N+1}}{N}$ except for odd $k$ and even $N$, when it's half that.
[1] For more precision, see section 5 of When are subset sums equidistributed modulo m?, Wagon and Wilf, Electronic Journal of Combinatorics 1.1 (1994).