This is for some simulations I'm trying to run, and since there are slower parts in my simulation, I want to speed up the processing of the below problem (since it isn't the core part).
What I have is a list of distinct numbers (or set) $S$ consisting of numbers in the range $[0, \approx10^5)$. This list is constant for every single run. I'm given a list of numbers $N$ (elements in this can be big, and are random). For each $n \in N$, I'm trying to calculate $\sum_{x\in S}\binom{n+x}{x}\mod 2$.
Naively, for every $n$, I have to loop through $S$ and sum up $\binom{n+x}{x} \mod 2$ ($\log n$ complexity each) and then get the final answer by modding 2 again.
I'm hoping there's some faster way to calculate this for any list $N$, with a fixed set $S$ per run. Any suggestions or ideas would be great, thank you!
PS: Essentially I need to calculate $\binom{n+x_1}{x_1} + \binom{n+x_2}{x_2} + ... + \binom{n+x_m}{x_m} \mod 2$. Any $x_i, x_j$ are distinct.
This may be helpful:
Since $\dbinom{n+x}{x}= \dfrac{(n+x)!}{n!\,x!}$, to find out the parity of this you can check whether there are the same or more powers of $2$ in $(n+x)!$ than there are in $n!\,x!$.
You can count powers of $2$ in $m!$ by repeatedly halving $m$ and discarding any fractional part. So for example for $53!$, set $a_0=53$ and $a_{i+1} = \lfloor a_i/2\rfloor$ and sum from $a_1$ onwards: $$v_2(53!) = 26+13+6+3+1 = 49$$
(meaning $53! /2^{49}$ is an odd integer).
You can precalculate these multiplicities once for the factorials of each $x_i\in S$ and $n_j\in N$, and of course $v_2(x_i!\,n_j!) = v_2(x_i!) + v_2(n_j!)$. However I don't immediately see a way around calculating individual multiplicities for the factorial of each sum $n_j{+}x_i$ - although this is just a matter of undertaking the above calculation in each case.