Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say I have a fixed list of numbers:

$2, 3, 1, 2$

and I can reduce every number from $n$ to $0$, for instance: $1,3,1,2$ or $0,3,0,1$ etc.

I am looking for all combinations of this sort, where I receive zero when applying $\oplus$ XOR to it. For example: $$1 \oplus 2 \oplus 1 \oplus 2 = 0$$

Is there a way to compute all possibilities? Just trying out every combination seems very naive.

share|improve this question
Do I understand correctly that you have a list $\langle a_1,a_2,\dots,a_n\rangle$ of non-negative integers, and you want to know the number of solutions to $\bigoplus_{k=1}^ne_ka_k=0$, where each $e_k$ is either $0$ or $1$? –  Brian M. Scott Feb 3 '13 at 4:30
@BrianM.Scott No, it's as you stated, but without $e_k$ and $a_k$ can be in the range between $0$ and $a_k$. $\oplus^n_{k=1} x_k$ with $x_k \in [0,a_k]$. –  Mahoni Feb 3 '13 at 4:32
Okay; that was the point about which I wasn’t certain. (I see now that I didn’t read the example carefully enough, since your $2\to 1$ in the last position covered this.) –  Brian M. Scott Feb 3 '13 at 4:33
@BrianM.Scott Sorry, the example is a bit to sloppy giving a false impression on the first look. –  Mahoni Feb 3 '13 at 4:34
But it’s not congruence mod $2$, if you really mean XOR: $2\oplus4\ne 0$, but $2+4\equiv 0\pmod2$. –  Brian M. Scott Feb 3 '13 at 4:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.