Getting all solutions to an equation on condition the variables are either 0 or 1

Given a list of 3-bit binary lists

b={{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}};


I would like to have all possible solutions to

s={0,1,0};
Mod[a[2] b[[2]] + a[3] b[[3]] + a[4] b[[4]] + ... + a[8] b[[8]], 2] = s


where each variable a[i] is either 0 or 1.

For instance;

Mod[{1,0,0} + {1,1,0},2]=={0,1,0}


for which a[5]=1 and a[7]=1 and all others 0.

Is this possible with Mathematica?

FWIW this can be solved by brute force: e.g.

b = Tuples[{0, 1}, 3];
t = Tuples[{0, 1}, 8];
sol[s_] := Select[t, Mod[# . b, 2] == s &]


Solutions can be visualized:

Graph[ArrayPlot[sol[#]] -> ArrayPlot[{#}, ImageSize -> 50] & /@ b,
VertexSize -> 0, VertexLabels -> Placed["Name", Center]]


b = IntegerDigits[Range@7, 2, 3];
t = IntegerDigits[Range@127, 2, 7];
ans[s_] := Select[t, Mod[# . b, 2] == s &]
Graph[ArrayPlot[ans[#], ImageSize -> 30] ->
ArrayPlot[{#}, ImageSize -> 30] & /@ b, VertexSize -> 0,VertexLabels -> Placed["Name", Center]]


• Sorry, sol[s] produces {0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 0, 1, 0},...,{1, 1, 1, 1, 1, 0, 1, 0}}. Therefore, this is not it (The number of the unknowns equals 7, not 8.). Hope your answer may be corrected. Good luck! Commented Nov 17, 2023 at 6:36
• Also Dimensions[sol[s]] performs {32, 8}. One sees duplication. Commented Nov 17, 2023 at 6:56
• You are strictly correct. As b[1] ={0,0,0} the duplication you refer to is evident in array plot with first column0s then 1s. The point of my answer was that brute force can solve. If I get time I will constrain the answer to fit the question. Commented Nov 17, 2023 at 7:11
• Sorry, your edited code s = {0, 1, 0}; b = IntegerDigits[Range@7, 2, 3]; t = IntegerDigits[Range@127, 2, 7]; ans[s_] := Select[t, Mod[# . b, 2] == s &] Graph[ArrayPlot[ans[#], ImageSize - › 30] - ArrayPlot[{#), ImageSize -> 30] & /@ b, VertexSize -> 0, VertexLabels - *Placed["Name", Center]] does not work at all: the one generates several syntax errors, e.g. "Syntax::bktmcp: Expression "{#" has no closing "}"." Commented Nov 17, 2023 at 17:18
• The code works. It has always worked. The issue is copy and pasting from iPhone OCR. This link is Mathematica online notebook image: you can edit (as is your penchant) or I will do later as I am going to work now. imgur.com/a/7NOhEUe Commented Nov 17, 2023 at 21:12

An equivalent version to user64494's answer is the following:

    Solve[
Mod[a . b[[2 ;;]], 2] == s && VectorLessEqual[{0, a, 1}] && a ∈ Vectors[7, Integers],
a
]


{{a -> {0, 0, 0, 0, 1, 0, 1}}, {a -> {0, 0, 0, 1, 0, 1, 0}}, {a -> {0, 0, 1, 0, 0, 1, 1}}, {a -> {0, 0, 1, 1, 1, 0, 0}}, {a -> {0, 1, 0, 0, 0, 0, 0}}, {a -> {0, 1, 0, 1, 1, 1, 1}}, {a -> {0, 1, 1, 0, 1, 1, 0}}, {a -> {0, 1, 1, 1, 0, 0, 1}}, {a -> {1, 0, 0, 0, 1, 1, 0}}, {a -> {1, 0, 0, 1, 0, 0, 1}}, {a -> {1, 0, 1, 0, 0, 0, 0}}, {a -> {1, 0, 1, 1, 1, 1, 1}}, {a -> {1, 1, 0, 0, 0, 1, 1}}, {a -> {1, 1, 0, 1, 1, 0, 0}}, {a -> {1, 1, 1, 0, 1, 0, 1}}, {a -> {1, 1, 1, 1, 0, 1, 0}}}

I should point out that here each vector corresponds to your {a[2], a[3], a[4], a[5], a[6], a[7], a[8]}

• For example, are the indices of a -> {0, 0, 0, 0, 1, 0, 1} OK? What is a[3]? Commented Nov 16, 2023 at 19:20
• Excellent, I have Mathematica 11.3 so I will need a definition of VectorLessEqual as well, please. Commented Nov 16, 2023 at 19:31
• Does the following work? Solve[Mod[a . b[[2 ;;]], 2] == s && Max[a] <= 1 && Min[a] >= 0 && a ∈ Vectors[7, Integers], a] Commented Nov 16, 2023 at 19:43
• I get errors: Vectors: --Message text not found --(z) and Solve: Unable to resolve the domain or region membership condition a E Vectors[7,z] Commented Nov 16, 2023 at 20:02
• I don't have 11.3 any more to check. How about Solve[Mod[a . b[[2 ;;]], 2] == s && a ∈ RegionProduct @@ Table[Point[{{0}, {1}}], {7}], a] Commented Nov 17, 2023 at 15:36

This can be done as follows.

b = {{0, 0, 0}, {0, 0, 1}, {0, 1, 0},{0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}};
s = {0, 1, 0};
Reduce[Mod[Sum[a[k]*b[[k]], {k, 2, 8}], 2] == s && a[1] >= 0 &&
a[1] <= 1 && a[2] >= 0 && a[2] <= 1 && a[3] >= 0 && a[3] <= 1 &&
a[4] >= 0 && a[4] <= 1 && a[5] >= 0 && a[5] <= 1 && a[6] >= 0 &&
a[6] <= 1 && a[7] >= 0 && a[7] <= 1 && a[8] >= 0 && a[8] <= 1,
Table[a[k], {k, 2, 8}], Integers]


(a[1] == 0 || a[1] == 1) && ((a[2] == 0 && a[3] == 0 && a[4] == 0 && a[5] == 0 && a[6] == 1 && a[7] == 0 && a[8] == 1) || (a[2] == 0 && a[3] == 0 && a[4] == 0 && a[5] == 1 && a[6] == 0 && a[7] == 1 && a[8] == 0) || (a[2] == 0 && a[3] == 0 && a[4] == 1 && a[5] == 0 && a[6] == 0 && a[7] == 1 && a[8] == 1) || (a[2] == 0 && a[3] == 0 && a[4] == 1 && a[5] == 1 && a[6] == 1 && a[7] == 0 && a[8] == 0) || (a[2] == 0 && a[3] == 1 && a[4] == 0 && a[5] == 0 && a[6] == 0 && a[7] == 0 && a[8] == 0) || (a[2] == 0 && a[3] == 1 && a[4] == 0 && a[5] == 1 && a[6] == 1 && a[7] == 1 && a[8] == 1) || (a[2] == 0 && a[3] == 1 && a[4] == 1 && a[5] == 0 && a[6] == 1 && a[7] == 1 && a[8] == 0) || (a[2] == 0 && a[3] == 1 && a[4] == 1 && a[5] == 1 && a[6] == 0 && a[7] == 0 && a[8] == 1) || (a[2] == 1 && a[3] == 0 && a[4] == 0 && a[5] == 0 && a[6] == 1 && a[7] == 1 && a[8] == 0) || (a[2] == 1 && a[3] == 0 && a[4] == 0 && a[5] == 1 && a[6] == 0 && a[7] == 0 && a[8] == 1) || (a[2] == 1 && a[3] == 0 && a[4] == 1 && a[5] == 0 && a[6] == 0 && a[7] == 0 && a[8] == 0) || (a[2] == 1 && a[3] == 0 && a[4] == 1 && a[5] == 1 && a[6] == 1 && a[7] == 1 && a[8] == 1) || (a[2] == 1 && a[3] == 1 && a[4] == 0 && a[5] == 0 && a[6] == 0 && a[7] == 1 && a[8] == 1) || (a[2] == 1 && a[3] == 1 && a[4] == 0 && a[5] == 1 && a[6] == 1 && a[7] == 0 && a[8] == 0) || (a[2] == 1 && a[3] == 1 && a[4] == 1 && a[5] == 0 && a[6] == 1 && a[7] == 0 && a[8] == 1) || (a[2] == 1 && a[3] == 1 && a[4] == 1 && a[5] == 1 && a[6] == 0 && a[7] == 1 && a[8] == 0))

• Thank you, this works with v11.3 Commented Nov 16, 2023 at 20:31