# FindInstance: remarkable timings

(Mathematica 11.1, windows 10)

I have a set of equations, for which I need only one integer solution.

equations=Mod[w7 Mod[w1+w2,2]+w8 Mod[w3+w4,2]+w9 Mod[w5+w6,2],2]==0&&
Mod[w7 Mod[w1,2]+w8 Mod[w3,2]+w9 Mod[w5,2],2]==1&&
Mod[w7 Mod[w2,2]+w8 Mod[w4,2]+w9 Mod[w6,2],2]==1;


FindInstance gives me within 2 seconds 5 solutions:

FindInstance[equations, {w1,w2,w3, w4, w5, w6, w7, w8, w9}, Integers, 5] // Timing

(* {1.73438,{{w1->429,w2->9,w3->33,w4->53,w5->31,w6->-88,w7->50,w8->-67,w9->-8},
{w1->394,w2->-48,w3->71,w4->46,w5->74,w6->3,w7->-12,w8->51,w9->-71},
{w1->-335,w2->-30,w3->94,w4->18,w5->-12,w6->-19,w7->-27,w8->14,w9->-23},
{w1->-381,w2->16,w3->-90,w4->-77,w5->-88,w6->25,w7->15,w8->1,w9->74},
{w1->367,w2->-54,w3->96,w4->3,w5->15,w6->38,w7->6,w8->13,w9->-57}}} *)


Two solutions are found within a second.

But when I ask for only 1 solution, it takes almost 10 minutes:

FindInstance[equations, {w1,w2,w3, w4, w5, w6, w7, w8, w9}, Integers] // Timing

(* {570.891,{{w1->0,w2->0,w3->0,w4->0,w5->1,w6->1,w7->0,w8->0,w9->1}}} *)


So this is the rather strange situation that finding 5 solutions is more than 300 times faster than finding one solution. Can someone explain why this happens? The last solution, when we looked for one solution, seems to be the simplest one, not found when we asked for more solutions, so different algorithms must be used in the two situations.

Personally, I prefer a solution found in less than a second above a 'nice' solution found in 10 minutes.

Can't explain why, but if you first Simplify your equations, you get the same single result within parts of a second

fsequ = FullSimplify[
equations, {w1, w2, w3, w4, w5, w6, w7, w8, w9} \[Element] Integers]

(*    Mod[(w1 + w2) w7 + (w3 + w4) w8 + (w5 + w6) w9, 2] == 0 &&
Mod[w1 w7 + w3 w8 + w5 w9, 2] == 1 &&
Mod[w2 w7 + w4 w8 + w6 w9, 2] == 1    *)

FindInstance[fsequ, {w1, w2, w3, w4, w5, w6, w7, w8, w9},
Integers] // Timing

(*    {0.172, {{w1 -> 0, w2 -> 0, w3 -> 0, w4 -> 0, w5 -> 1, w6 -> 1,
w7 -> 0, w8 -> 0, w9 -> 1}}}    *)

• Nice observation, thanks. – Fred Simons Jul 4 '17 at 6:16