Smallest integer $k$ so that no Sudoku grid has exactly $k$ solutions

Inspired by this question, consider hints on a Sudoku board. A regular puzzle has a unique solution. It is clear that there are puzzles with 2 or 3 solutions, and therefore, I guess, puzzles with say 4, and 6 solutions.

Now, what is the smallest integer $k$ such that there is no set of Sudoku clues resulting in exactly $k$ solutions?

Solution 1:

Like it usually happens with these conjectures, if the solution is not k=7 or k=11, it may be really hard to find. Of course, there exists a solution, for there is a maximum (huge) number of solutions that a blank sudoku allows. A property that may help to construct solutions is that for small values, if we have a sudoku that allows a solutions and another that allows b solutions, we can probably find a sudoku that allows a·b solutions. For example:

This allows k=4 fillings: $$ 2,9,6|3,1,8|5,7,4\\5,8,4|9,7,2|6,1,3\\7,1,3|6,4,5|2,8,9\\6,2,?|?,9,7|3,4,1\\9,3,1|4,2,6|8,5,7\\4,7,?|?,3,1|9,2,6\\1,?,7|2,?,3|4,9,8\\8,?,9|7,?,4|1,3,2\\3,4,2|1,8,9|7,6,5 $$

And this allows k=3 fillings: $$ 2,9,6|3,1,8|5,7,4\\5,?,4|9,7,2|6,?,3\\7,?,3|6,4,5|2,?,?\\6,2,5|8,9,7|3,4,1\\9,3,1|4,2,6|8,5,7\\4,7,8|5,3,1|9,2,6\\1,6,7|2,5,3|4,?,?\\8,5,9|7,6,4|1,3,2\\3,4,2|1,8,9|7,6,5 $$

From this, we can easily see that this: $$ 2,9,6|3,1,8|5,7,4\\5,?,4|9,7,2|6,?,3\\7,?,3|6,4,5|2,?,?\\6,2,?|?,9,7|3,4,1\\9,3,1|4,2,6|8,5,7\\4,7,?|?,3,1|9,2,6\\1,?,7|2,?,3|4,?,?\\8,?,9|7,?,4|1,3,2\\3,4,2|1,8,9|7,6,5 $$

allows k = 4·3 = 12 fillings.

Although it is hard to generalize, probably the number you are looking for is prime, because if it was to be a composite number, its factors (smaller than the number) would have to be a number of fillings for some sudoku, and then this non-rigorous multiplication rule would fail.

Solution 2:

This is just a partial answer, which can perhaps be turned into a community wiki, where examples of partial fillings that allow $n$ complete valid fillings.

This admits $k=2$ solutions: \begin{array}{ccccccccc} . & . & . & . & 5 & 1 & 8 & 7 & 6 \\ . & 7 & . & 6 & . & 9 & . & . & 3 \\ 6 & . & 8 & . & . & 2 & . & 9 & . \\ . & 4 & . & 1 & . & . & . & 8 & . \\ . & . & 1 & . & 3 & . & . & . & 4 \\ 8 & . & . & . & . & 7 & 1 & . & . \\ 2 & . & . & 5 & 6 & . & . & 3 & . \\ . & . & . & . & 1 & . & 9 & . & 8 \\ 3 & . & . & . & . & 4 & . & . & . \\ \end{array}

This allows $k=3$ fillings: \begin{array}{ccccccccc} . & . & . & . & . & 1 & 8 & 7 & 6 \\ . & 7 & . & 6 & . & 9 & . & . & 3 \\ 6 & . & 8 & . & . & 2 & . & 9 & . \\ . & 4 & . & 1 & . & . & . & 8 & . \\ . & . & . & . & 3 & . & . & . & 4 \\ 8 & . & . & 9 & . & 7 & 1 & . & . \\ 2 & . & . & 5 & 6 & . & . & 3 & . \\ . & 6 & . & . & 1 & . & 9 & . & 8 \\ 3 & 8 & 7 & . & . & . & . & . & . \\ \end{array}

If my calculations are correct, this allows $k=5$ complete fillings: \begin{array}{ccccccccc} . & . & . & . & 5 & 1 & 8 & 7 & 6 \\ . & 7 & . & 6 & . & 9 & . & . & 3 \\ 6 & . & 8 & . & . & 2 & . & 9 & . \\ . & 4 & . & 1 & . & . & . & 8 & . \\ . & . & 1 & . & 3 & . & . & . & 4 \\ 8 & . & . & . & . & 7 & 1 & . & . \\ 2 & . & . & 5 & 6 & . & . & 3 & . \\ 5 & . & . & . & 1 & . & . & . & 8 \\ 3 & . & . & . & 9 & . & . & . & . \\ \end{array}

Currently, $k=7$ is still unknown.

This is the mathematica code I use to solve Sudokus. It is just basic recursion, and can most likely be optimized a lot.

(* Returns true iff we can place n at r,c in the filling. *)

IsValidQ[partFil_, n_, {r_, c_}] := Module[{sr, sc},
   (* Check row, col, sub-box for already existing. *)
   Catch[
    If[MemberQ[partFil[[r, All]], n], Throw[False]];
    If[MemberQ[partFil[[All, c]], n], Throw[False]];
    sr = Floor[(r - 1)/3]; sc = Floor[(c - 1)/3];
    If[MemberQ[
      Join @@ partFil[[3 sr + 1 ;; 3 sr + 3, 3 sc + 1 ;; 3 sc + 3]], 
      n], Throw[False]];
    True
    ]
   ];

SolveSudoku[partialFilling_List] := Module[{recSolve, sols = {}},
   recSolve[pFil_List] := Module[{nFil},
     Catch[
      Do[
       If[pFil[[r, c]] == 0,

        (* Try all 9 numbers. *)

        Do[If[IsValidQ[pFil, n, {r, c}],
          recSolve[ReplacePart[pFil, {r, c} -> n]]]
         , {n, 9}];

        (* We tried all 9 numbers here. Now abort. *)

        Throw[False]
        ]
       , {r, 9}, {c, 9}];
      AppendTo[sols, pFil];
      (*Print["NSOLS: ",sols//Length];*)
      True
      ]
     ];

   recSolve[partialFilling];
   sols
   ];

Solution 3:

Here is an example for $k=7$:

\begin{array}{ccccccccc} . & . & . & . & . & . & 7 & . & .\\ 9 & . & 7 & 1 & 2 & 3 & . & 5 & 6\\ 4 & . & 6 & . & 7 & . & . & . & 3\\ 3 & 1 & 2 & 8 & . & 5 & . & 6 & .\\ . & . & . & 3 & . & . & . & 4 & 5\\ 8 & 4 & . & 7 & . & 9 & . & . & .\\ . & . & . & . & 9 & . & 6 & 7 & 8\\ . & . & 8 & . & . & . & 5 & . & .\\ . & . & 4 & . & 8 & . & . & 3 & 1\\ \end{array}

Which resolves to:

\begin{array}{ccccccccc} . & . & . & . & 5 & . & 7 & 8 & 9\\ 9 & 8 & 7 & 1 & 2 & 3 & 4 & 5 & 6\\ 4 & 5 & 6 & 9 & 7 & 8 & 1 & 2 & 3\\ 3 & 1 & 2 & 8 & 4 & 5 & 9 & 6 & 7\\ . & . & 9 & 3 & 1 & 2 & 8 & 4 & 5\\ 8 & 4 & 5 & 7 & 6 & 9 & 3 & 1 & 2\\ . & . & . & . & 9 & . & 6 & 7 & 8\\ . & . & 8 & . & 3 & . & 5 & 9 & 4\\ . & 9 & 4 & . & 8 & . & 2 & 3 & 1\\ \end{array}

Here I extend the prime list of $k$ to the first $142$ primes ($2$ to $821$).

To do so I implemented Knuth's dancing links for Algorithm X, iterated through solves of an empty sudoku, randomly removed between 20 and 53 clues and counted solutions. The first of each prime count was then added to a dictionary. I left it running for about half an hour. Progress had not slowed all that much after the initial burst to around $37$. It discovered another $173$ larger prime solution counts, ranging from $827$ to $17,137$ solutions.

To avoid this post being ridiculously long each is in single line form, and all are in a code block:

  2: 1...5678..8..2345...6..8..331..4.967..7.128.....9....223157469...8.3157..74.89.31
  3: 12...67..78.1234..45.....2.3.2.45..7.673.29...458...1.2.15..6..6...3157.....98.31
  5: ..3.5...9.8......64....9.23.12.....7..73.294.9...6..12231.9.67....2.1594....7.231
  7: ......7..9.7123.564.6.7...33128.5.6....3...4584.7.9.......9.678..8...5....4.8..31
 11: .2...6.8.7.8123456....891233.26..89....3.264...5...3..2.1.....8.7.231.64...8....1
 13: 1.3.5.7...98...4.6.569.81.331.8.5......3.28..8.....3..2315......7..3.5.45.....2..
 17: 1..4.67.99.......6.5..87.2..12....67.693.2.4..4576.3.2.3...4.7...82...9..9.6...3.
 19: ....5.7.98.7..34..4.6......31.....9.9....26.5.4..7931.....6...87..23...45....723.
 23: .2..5..9..7.12..5.456.79.2.31..4...99......456.59....2231...9..7.8.3.5..5.4.9....
 29: 1...5...9..9.....6....8.1233....5....98.126.....89731.2.1.6....9...315.4..4.7.2..
 31: .2.4.689.798.........7.81.........78..9.12.4.64.87....2.15..78..872.1...5.498....
 37: ..3456....9....45..5....123.12.45...9..3....5.......1.2..5...9..8...15..5..9.7.3.
 41: ...45.7.99.812....4..78..2..12.45.9...7312.....59....2........8....31..45..89.2..
 43: ........8897....5.4.6..8...3....5.7....3...45.45.8.3.2.......8797.231.64.64.9.2..
 47: .2..........123.56456.89...3..6.58...7..126....5........1..4.7.79..3........78...
 53: .2.4.6...97.1..4..45...8.23..2..59.......2.45645.7.31....5.4...7.9..1........72..
 59: .......7.97..23456....78.2..........76.3.28...45.693.2...59....6....1....94....3.
 61: ...456.98.87....56...89...3.1.64.....9.3..64...57..3...3.5.......9....645..97...1
 67: .2..5.8......2....45..9..23312.......9..1264..4...9..2..1...9..9..2..5..56..78..1
 71: ..3.....8.8.1234...5...8..3..2...8.696..12.45...8....2..1....8....23.5745749.6.31
 73: .....68.978912.45...68...2.3........86.312945..5...3..2....4........1.945...8..3.
 79: 1.345.......1.34..4..9....3.12.45967.7...284.84..9...22..5...9.9.7.3.............
 83: .23...87..79......45.7.8..3...6......98..2...64598...223..........2.15.4..48.9...
 89: ..345.......1.......6..8......64.8.7...3....564587...223.5.4.6......1..45..9....1
 97: 123.5..8.8.7...4....96...2.....4..6..8...2..........12.315.467.6...31.....4...23.
101: 1...5...896.1.34.7....9...33....58..89..1..........3.22..5..6..6..23157....96823.
103: .2.4.7.68.....345.4....6..331.7..896.........74...8.1..31584...9.....5....4.79.3.
107: 1..4.....79.1..4....6.8.123.1.6......87.....5.4.798....315.......92..5.4.64.7.2..
109: 1..4.679...9..3.......9....31.945.6.768..2.4..456......31..46.9...231..45.4..9...
113: .....67....7..3.5..5.7....3.....5...769...845.4.9...1223...49...9.....7.5746..23.
127: ...459......1.34..4.....1..31.9.5...7..31.....4.678....3.59.87....2..5.4.9..67...
131: .2...7....8.......4...8.12...2.4.......3.2.4..4.89631223.5.4968........45.4.6...1
137: .2.4578.......345.45.....23..2..5........2.4..45..93....1...6899.8.3.5.4.........
139: .234.687.8....3..6..687.1.....64..877.93.2.....5..7..............8..1...56...82..
149: ...45...........5.4...681.3....457...6...2......8...1.....94.8.68723...4....8723.
151: 123..7869..912345.....96.2...27..9....63...............31..4..8..8...5.4.7..6.2..
157: ...4.786...81.3.5.4......2.31..45...8693...4.7.5.96.1....5..69.....3..7........3.
163: .234.6....98.2...6..6...1......4.........2....4....3..2.1.64.78...2.15....49.8.31
167: .2.....8...........5698..2331..4..9....3..74.74..69.12.31...8..6..........4698..1
173: 1.34...796........45..76..3.1..4..67......8...4.769.....1...7.6.96...5.......7.31
179: .2.....8.8691.345745..6.1.3.12..5.6.67......5945..8.1......4.7........9..9.....3.
181: ..34..7......2.4..4.8.7.1.3........7...3.284.84.96.31....5.497....2.15...8.796.31
191: .2.4...9..8.1...5.4........3....5.89...31.64.6459.8...2...64.7.87.2...64..4......
193: ..3..6.....7.2.4...56.9......2....6.....12.....5.78..2231..4.7..7.....8.5.47.92..
197: .....98.78.712..5....76......2.459.........4....8.....2....479.7..23..84..4...2.1
199: ..345...8.97.2..5.4..78..2........87.783.2..5..5..8.....1......78..3.5..5.....23.
211: ...4....66.7.....94......2..1....9...76.1..45845...3....1.9.....6...15...94.8..31
223: 1...5.8.686..2...7....8...3...7......98..274......8...2..57....9.62..57..7..962.1
227: 1...5..69...1.345.4.....12...2.45.......1.....45.9..1.2...7.......23.5.45746...3.
229: .2.....89..9...4...5....123.....56.7...3...4..4...73..231564..897......4.6....23.
233: .2.456.8...........5.7...2.31..45.......12.4.6....9...2.1...97.7.....5.4564...2..
239: ....5.869..8..34.745..9.1.......598.8....2..5...689.....1...6...8.2.1....7...8...
241: ...4...96...12......7...12331.7........312745....983..2.15.....8..2..5.......9...
251: ..34.......61234....96.8.2.3...456.8..8.1.9..9...8....2..86....5.7...8....4......
257: 12.4598.68..12...94.9..6..3..2..5..8.8....945........2...5.....6.8.31.........2..
263: ..........76...45.458....2...284........1284...567..1......4.......3.5845..96.2..
269: ..3.5.69.....2..5.....8.1.331.....86.8......5.4..9.3......7..69...2..57..7486....
271: ...4.6...7.8123..6..6...1...12.4..7....3.....64..............8.9872..5.4564....31
277: 1234..6.....12....4.879...33..8....6.........8..96.....3.5.4.676....15.....6.9.3.
281: .23.58769.6..23..8.......2...28.569.6..3.2.4.84.......2......7...62.1.....4..6.3.
283: 12.45.6...7....45....76......2...98..8....5..6..89..1.....7.....682..794...6...3.
293: 1.34..89..78...4...5...7.233.....7.9..73......45....12.3..6.9....9....64.......3.
307: ....5.8.98.912....4.7..8....1.....9...8..2...6...79.1.2.....97...6.31.8..8.....31
311: .2.4.....6.9.23.58..89..1.3...84...7.673...4......7...2.1..........31.84.8...9...
313: ..3..8.....9...45......9..3..26..789.973..645...9...1........96.8....5..57...62..
317: 12.4.6.......2..5.4........3.254..8.6873....5.4.68......186...9.7......4.6...5...
331: ..3.....8876..........671..3..9.56.77.83.....9....83.2......8766.72..5..5.4...2..
337: .23457.6.9.8.23457..796812....6.5...........56.5.........5....678..31.945.47.62..
347: 12....967....2.......97612.3..8.5.9...9.1...5.........23.....7.7..2.1.....4.9.2.1
349: .23.5.7..97..2.4......79.....264.8....9..26..64..98...2...64..7.9.....64....8..3.
353: ..3..9..7..6....5...9...12....9.5.7.7683....5..56..31.....9.78..872...9..9.7..2..
359: 1.34.....87912.4....69...2.3.....9.....3..64..4....3..2......9..9.2...6.76...923.
367: 12.....98.........4...9..2.31274....9...1.....4..6831..31574..68...3.5........2..
373: .23..6.........4.....8...23.12.45.7.9......4.......31.23.5.47.9.89.....456....2..
379: ..3.5....7.9.....64.6.98.233..9..8...6....9...45..73.......4..96982..5..........1
383: ...4.......6...45.4.8..61...1...9.8..8.....4664...7..22...6.....952..8..8.4...2.1
389: 1.3...7697..1.3.58..86.91....2............8.....9.....2.1..46..967..15.45.47.....
397: 123.......98.......5....12....9...7...63..94...567.3.2.3....7.9..9...5..5.....231
401: .2.....7...6....5.4.......3..25.7....69..2.4.5.7...3..2..68...5.9........8.795231
409: 1.3.5.7............56..9..3.....5...8.....64...5.8.3.2...5.4.7......1564.6.79..31
419: 1........9..12.4..4.....1...126.9..5..531..4964.8..3..2.15.4..7..723.5.45..9.....
421: 12.457.9698.123......6..12......8..9........88..97631.2.1.6.....9.....7.....9..3.
431: 12.......6.7.2.......6.7.2331.9.......6..2..5.457.......159....7.8231...5....6.3.
433: 1.3......7961.....4...7..2..12.49..76...1..49.4..6.............5.9..18.4.6479....
439: 1..458.....6....5....9.61.33.264.........2...64.78..1.2......6...7......89..672..
443: .2...8.79..71.3.58.586.7..33...4.....8..12..5.....63...31.6.............5..8...3.
449: ...4......7...34594.97.6.....2...6.7.....29...4.....1.2..594.6..86....9..9.6.8...
457: ....5.98.9.7...4..4..9..1.....548679.....28....8......23...4....652.....7...652..
461: ....5.9...7.12..5.45...7...3.274.....9.31.74.7...89312.3....8...8.....6.......2..
463: 1.3...6..67.....5.45..7..2.3.......689.31..4..47...3...3........6523..8....7....1
467: 1...........1...7....9..123.12.4...97.5312....46.9..12231.8.5...79...8...........
479: .....6978....2...64..8..12.3.2...78....312..56..78.3...31......9.82..5...........
487: ...45....6...2....4..6...233..9.5..6..6..29.....786.12.31..4..9..523......4.6....
491: 12.4.8......1......58.7612...2.49.6.86..1..4.74.....1.2.1......5.7.......8.5...3.
499: 1...576..6..12.......6..1.3.........796.....5.489...1...1....6..6..3..94.7..6..31
503: ..3...89..9.123....56.9...3..25....8.6.31.....45.........6..98.5....1......9.5.31
509: ......8....7..3.5.4.6.8....3127..69.........8.4..9.3..2....498.8.9...5..5..8.9.3.
521: .234.7....691.34.745796.1.33..5.6..9.7....6......89..2...6..........1....9.......
523: ...4......6.1..4.7..7.69...3.29.5..67....29.594..78.......94...6..2.1..4....86...
541: 12.4598..8..1....9..........1.745....6...27.5....6..1..3.5.4.8...7.315..........1
547: 12.4.867.76912..5.....67123.1......6.8...2.....7.......3...4.6..7..3...4.94...23.
557: 12.4.8.7....12..58....6..2.3.2..5.9......2..5......3...3...4...679231.8.....9.2..
563: 12345........2....4...781...1..4....8...1.....4..8.3...31594.876.....5.45....723.
569: ..3.579.6....2.45...7...12.3.2..5.79..8....4........1....7.....5...3.7.4..4.8.231
571: 123.......7......6..6.7.12..1...........1..4.6..7...122....47...8..31.64.6.9.723.
577: 12.4.6....89......4.69..1..3.2..5...69.3.2......76..1....694...8..........4.7.23.
587: .2....976..6...4.5......1.3.12.4..5.5.7.1..4..49.8531..3.....6.....3.8.....56....
593: ...4.7.86.89....5..57.8.12...2....9.9...12.4....89......1....6989.2.1.......6....
599: .....87..7....3458.......2......6.85...3.26.7.475.931....87459....2..8..8...6....
601: ....59...7...2.........61.33.25..9....73....5...9......31.9.58....2317949.4685..1
607: ..345.....7..23.5.4.6..71.33.2.4.....95.12......569.12..........672............31
613: 1.34....66...2..57....89..3.12.4.7......1........9..1...1..4...8.6.3.5.4.5.9..2..
617: ....56.......23.5.4......2....5..76..693......4.679.......9.6.....231..498.76..3.
619: ...45......9123....5....1...1......76.7.128..5.8.6......1.94.....5.3....9.4..523.
631: 1.3....9..9.1..4..4..89.1...12..9...78..1..4.6.....3.2.3.....6.5682..97..........
641: 1.345....7..1..4.6..6......31.8..9...6.3.....847.........584.97..9......5.4..9.3.
643: 12..5.6.8.6.123.5.....8612.....4..6..7..129....56...122.....7..................31
647: ..3.5.....9...3.....7..6.23.12.49.75..5..2..9....7.31..3....56.....31......56823.
653: ....587.9..9......45.7..12......59.6.9631.84.8.596..1..3................5..6.9...
659: 1....76.9.......7....8...23312......6..3..7........31223.....6.9.....8.4..4.7.231
661: .2.4..6.9.9............9...3.2..8....6931.5..5.8..6.1...1....566.5.3..9......5.31
673: 12.4..7...9..23..8...9.7123.....96...6.......5...7...2.....4....5623..74......2.1
677: 1...59......1....9..9.8.123.....8.7.69......8........2.3.8..7.5..5.3.89498...5.3.
683: ..3..9.....8.2.459..96..1.33.2.....69.....5..5.....3..2.1...8..87..3.6946....8..1
691: .2...9....86.....9....76..3.1...8....75..2..86.8.95.12.3...4..........84894.6.231
701: ...45....79.12.4.....89.123..2.........3...............315..8.7..7231..4.547892..
709: .23.5....9..1.3.574579..1..31....6......1.84..4.76..1....6.4......2.176..........
719: .....9..7......4..4....81......46....8..12..6.4.9..3....17.4.8..9..31.7..74.95..1
727: 1.34569..7891...6...67....3...9.75....5..........6.3.2..16.48.7.78........4......
733: 1.345.6.7....2....45.....2..1..469.57..3..84.84.....1.23....5..5.............5.3.
739: 12.........91.34...5.9....3....4.8.998.3...45.4.7.9....3.89.......2.1..4.9..6....
743: ..3...7.9.6.1.3...4..7..1..31.8......9.3..84....9..3...3...49......3..7457468....
751: ..345.7..7......5.4..76.1..31..4....87.........587.3...3...4..7597...8....4...2..
757: ...4.6.98.8...3....5........1..4.8....8.1.6......7......18...6.5.7231.8.8.4.67231
761: 12.4....9......4..457..9..3...........5.12648....7.31...17.4..65.92...8...4......
769: .23...7.687612.4...5...6.2..125....7.....25.85....73.2.31...8...8......4......231
773: 1...........12.....5....1........7.8......645.....9..223189.576.652.1.84..4..6...
787: ..3.5...88....3.57......1..3.2..9........2...9.8675.1.23...4..668.23..9.........1
797: ...45.798.98.........7981.........6.867.....5....8.3...3.8..579..92......8..7..3.
809: .....87......2....4...7.123.1.84...696....84.84576.....3...4.........584.....7.3.
811: 1....86.9.........4..7.....3..5...8.8..31..45547.893....1....97..5.....4.84..52..
821: ..3....696...23.......96.2...2..7..69....25..54..69....3.98...57..23.8.....6.....

Which resolve to:

  2: 123456789789123456456798123312845967..7312845845967312231574698..8231574574689231
  3: 12.4567..78.12345.45.78912.3129458678673129459458673122315746..698231574574698231
  5: .23.5..89.89.23.56456.89.23312945867867312945945.6.312231594678678231594594.7.231
  7: ....5.789987123456456978123312845967..9312845845769312....9.678..8.3.594.94.8.231
 11: 123..6789798123456...7891233126..897987312645..59783122.1.6.9.8879231564...89.2.1
 13: 12345679879812345645697812331.8.5...9..3.28..8.....3..231584...679231584584...231
 17: 1.34.67.99.7...4.6.5.987123312.4.967769312.4.845769312.3..94.7..782...9..9.67..3.
 19: ....5.7898.7..34..4.67....3312.4.897978312645645879312....6..787..23...45....723.
 23: 123.5..9.87912..5.456.79.2.31..4...998.....456459....2231...9..798.3.5..56479.2..
 29: 123.56..98.9123.56....8.123312645...798312645...8973122.1.6....9..2315.4..4.782.1
 31: 123456897798123...4567981..31.64..78879312.4.64.87....2.15.47899872.1...5.4987...
 37: 123456....9.123456.5....123.12.45...9..31...5..5....1.2..5.4.9..892.15..5..9.7.3.
 41: ...45.78997812....45.789.2..12645.97.97312....45978..2....6...8.8..31..45..89.2..
 43: ........8897.23.5.4.6..8...3....5.7...93.2.45.45.8.3.2......9879782315645648972..
 47: 123456789987123456456789...3..6.58.787.3126.5..58.7....31.64.78798.31.64....78...
 53: .2.456...97.12345.45.798.23..2.459...97.12.456458793122..5.4...7.92.15.45.49.72..
 59: .......78978123456.5..78.23...8.....76.3.28..845769312...59....6...31...594.8..31
 61: .2.456798987...456.5.897123.1.64.....9.3..64...57..31..3.56.....79...5645..97..31
 67: .2..5.8......2.45.45.89.123312...7...9.3126456457893122.1...9..9..2.15..564978231
 71: ..3.....8689123457.57..8..3..2...8.6968.12.45..586...2..1...689896231574574986231
 73: .....68.9789123456.568...233....5...8673129459.5..83..2....4...6.8..1.945...8..3.
 79: 1.345....7..1.34..4..9....3312845967.793.284.84..9...22..5...9.9.7.3.........9...
 83: 123...87.879......4567.8..3.126......98..2...64598...2231......9872.15.45648.9...
 89: ..345.......1.......6..8..3312645897...312645645879..2231584769.....1..45.49....1
 97: 12345..8686712.4....96..12..12.45.6..86.12.....5....12231594678678231.....4...231
101: 1...5.9.896.1.34.7....9.1.33....589689.31.745.....93122..5..68.6..23157....96823.
103: .234.7.68.....345.4....6..331.74.896.......4.74...8.1..31584...9.....584..4.79.3.
107: 12.4.....79.1..4..456987123.126......873...45.45798.122315.....8792..5.456487.2.1
109: 1.34.679...9..3.......9....3129458677683129459456......31..46.9.9.2315.45.4.69...
113: ....567.9..7..3.56.5.7....3.....5.97769...845.459.7.1223.57496..9....5745746..23.
127: ...459......1.34..4..7.61..31.945...7..312.4..4.678....3.594876...231594594867...
131: .2...7....8.......45..8.12.3.274.......3.2.4.745896312231574968........45.4.68.31
137: .2.4578......2345.45.....23..2.45..8.....2.45.45..93.22315746899.823.5.45.4...23.
139: .234.687.8....3..64.687.1.....64..877.93.2...6.5..7........4..8..8..1...5647.82..
149: ...45..7..7.12.45.4..768123....4576.76..12.4....876.1....594687687231594...687231
151: 123457869..9123457...896.2...27.59.6..63........6......31.74698..8.31574.7..682..
157: ...4.786...81.3.5.4......2.312745986869312.4.745896.1....5..69.....3..7........3.
163: .234.6....98.2...64.6...123....4.........2....4....3..2.1.64978...2.1564..49.8231
167: .2.....8...........56987.2331.74..9..6.3..74.745869312.31...8..6.........74698.31
173: 1.34..67967....4..45..76..3.1..4..67.67...8...4.769....31...7.6796...5....46.7.31
179: 123..7.8.869123457457869123312..5.6.678....459456.8.12.....4.7........9..9.....3.
181: ..34..7......234..4.867.1.3....4.6.7...3.284.84.96731....5.497....2.15.4584796231
191: .2.4...9.98.1..45.4........312645789798312645645978...2...64.7.87.2...64.64......
193: .23..6.....7.2.4.6.56.97.2...2....6...8.12.....5.78..2231..46796792315845847692..
197: ...4598.78.7123.5....768.....2.459.........4....8.....2....479.7..23..84..4...2.1
199: ..345.7.8897.2..5.45678..2........87.783.2..5..5.78..2..1...87.78..3.5..5..8.723.
211: 1..4....66.71..4.94.....123.1....96.976.1..45845...31...1.9.....6...159..94.8..31
223: 1...5.8.686..2...7...68...3...7.5....98..2745...9.8..22..57....9.62..57..7.896231
227: 12.45..69...12345.45.96.12..12.45.......1..45.45.9..1.23.574......23.57457468..3.
229: .2..5.789..9...456.5....123.....56.7...3..84..4...73..231564978978...564.6....231
233: .2.456.8...........5.7...2.31..45.......12.4.64..79...2.15.497.7.....5.4564..72..
239: ....5.869..81234574578961.......59868....2..5...689.....1...6.8.8.2.1....7...8...
241: 12.4..896...12.457..798.1233127........312745...6983122.15.....8..2.15.....8.92.1
251: .234.......61234....96.8.2.3.29456.8..8.1.9..9.5.8....2.186....5.72..8....45.....
257: 1234598768..123459459..6123..2..5..8.8...2945........22..5.....6.823159.......2..
263: ...4......76...45.458.9..2...284........1284.84567..12.....4.......3.5845.496.2..
269: .23.5.69.....2..5.....8.12331..4..86.8.....45.4..98312....7..69...2..57..7486.231
271: ...4.6...7.8123..64.6...1..312.4..7.87.3.....64............4.8.987231564564...231
277: 123458679...123...458796..33..8....6...3.....8..96.3...3.584.676..2315.....679.3.
281: .23.58769.6..23..8.......2...284569.6..3.284.84.......2......76..62.1.8...4..6.3.
283: 12.45.67..76...45....76..2...2...98..8....54.6..89..1.....7..6..682..794...6...3.
293: 1.34..897.78...45..5...7.233.....7.9.973......45...312.3..6.97...9....64.......3.
307: 1.3.5.8.98.912....4.7..81...1.....9...8.12...64..79.1.231...97...6.31.8..84....31
311: .2.4.8...6.9.23458..89..123...84...7.673...4......7...2.1.84.......31.84.8...9...
313: ..3..89....9...45......9..3..26..789.973..645...9..312.......96986...57.57..9623.
317: 12.4.6.9.7...2.45.4........31254..8.6873...45.4.68......1864..9.7......4.64..5...
331: ..3...768876.........8671..3..9.56877.83.....9....83.2......8766.72..5..5.4...2..
337: 123457.6.968123457457968123...6.5.........6.56.5.........5....67862315945.47.62..
347: 12....9679..12.......97612.31.8.5.9...9.12..5.....9.1.231....7979.2.1.....4.972.1
349: .23.5.7..97..2.4......79.....264.8....9..264.64..98...2...64.87.9.....64....8..3.
353: ..3..9.67..6....59..9...123...9.567.7683..9459.56..31.....9.78..872..59..9.7..23.
359: 1234....98791234564569..1233.....9..9..3..64.64..9.3..23....59.59.23..6.76...923.
367: 12..5..98....2....4...9..2.31274.86.9...1.....4..6831.2315749868...3.5......8.2..
373: 1234.68..8.....4.....8..1233126459789......4.......31.2315.47.9789.....4564...2.1
379: ..3.56.98789....56456.98.233..9..8..86....9..945..73.2.....4..96982..5....4..9..1
383: ...4..6....6...45.4.8..61...12649.8..8.....4664...7.122...6.....952..86.864...2.1
389: 123...7697961234584586791....2........9...8....59.....2.1..46..967..15.45.47.....
397: 123....9..98....5..5....12.3..9...7...63..94.9.567.312.3....7.9..9...5.45.....231
401: .2..5..7...6....5.45..7...3..25.7....69..25475.7...3..2..68..95.95......684795231
409: 1.3.5.7.........5..56..9..3.....5..78.....645..5.8.3.2...564.7......1564564798231
419: 1..4.....9..12.4..4..7..1..312649..57853126496498..3..2.15.4..78.723.5.45.49.....
421: 123457896986123..7...689123.....8..9..9.....88..97631.2.1.6.98..9.....7.....9..3.
431: 1234.....6.7.2....4.96.7.233129......76..2..5.457.....231594...768231...594876.3.
433: 123......7961.....4...7..2..12.49..76...1..4994..6......1......5.9..18.4.6479....
439: 1..458.....6....5....9.61.33.264.........2...64.78..122......6..67......89..672..
443: .23458.79..71.3.58.586.7..33...4.....8.312..5....863...31.6........3....5..87..3.
449: ...4.9..667...34594.97.6.....2...6.7.6...29...4..6..1.2..594.6..86....94.946.8...
457: ...45.98.9.7...4..4..9..1.....548679.....28....8......23...4...8652.....7...652..
461: .2..5.9...7.12..5.45...7.2.31274.....9.31274.7...89312.3....8...8.....6.......2..
463: 123...6..67.....5.45..7..2.312.....689631..4.547...31..31....6..65231.8..847...31
467: 1.....9..9..1...7....9..123.12.4..59795312....46.9..12231.8.5...79...8........2..
479: .....6978....2.4564..8..1233.2...78....3126.56..78.3.2.31......9.82..5...........
487: ...45....6...2....4..69..233..9.5..6..63.29..549786312.31.74..9.6523......4.6..3.
491: 12.4.8....7.1......58.7612.312.49.6.86..1..4.74.....1.2.1......5.7.......8.5...3.
499: 1...576..6..12.......6..1.3.1.......796.1...5.4897..1...1....6..6..31.94.7..6..31
503: ..3.5689..9.123....56.9...3..25....8.6.31.....45........16..9855.9..1...6..9.5.31
509: ..3...8...87..3.5.4.698...33127.869..95.....8.48.9.3..2.1..498.8.9...5..5.48.9.3.
521: 123457...8691234574579681233.25.6..997....6......89..2...6..........1....9.......
523: ...4.7....6.1.34.74.7869...3.29.5..67.63.29.5945678.......94...6..231..4..4.86...
541: 12.4598..8..1....9......1...1.745....6..127.5....6..1..315.4.8...7.315..........1
547: 123458679769123458...967123.1......6.8...2.....7.....2.3...4.6..7..3...4.94...23.
557: 12.458.7....12..58....6..2.3.2..5.9....3.2..5......3.223...4...679231584....9.23.
563: 12345........2....4...781..31..4....8...1.....4..8.3..2315946876...3.5.45.4.6723.
569: .23.57986....2.457.57...1233.2..5.79..8....4...5....1.23.7.....58..3.7.4..458.231
571: 123.......7.1....6..6.7.12..1...........1..4.6..7...1223...47...8.231.64.6.9.723.
577: 12.4.6...789......4.69.71..3.28.5...69.3.2...5487693122..694...8........9.4.7823.
587: .23.5.976..6...4.5.5....1.3312.4..58587.1..49649.8531..3....56..65.3.89....56..3.
593: ..3457986.8912..5..57.8.12...2....9.9.8.12.4....89......1....698962.1.......6....
599: .....87..7....3458.....712....746985...312647647589312...87459....23.8..8..96.2..
601: ..3.59...7...23..9..9..61.33.25..9...973....5...9.....231.9.586...231794974685..1
607: ..345.....7..23.5.456..7123312748...695312...7..569312.3........6723...........31
613: 1.34....66...2..57...6891.3.12.4.7......1........9..1...1..4...8.6.3.5.4.5.9..2.1
617: ....56.......23.5.4...87.2....54.76976931.....4.679......89.6.....231..498.76..3.
619: 1..45......9123....5....1...1..4...76.7.128..5.8.6..12..1.94.....5.31...9.4..5231
631: 1.3....9.89.1..4..4..89.1..312..9...785312649649...312.3.....6.5682..97..7.......
641: 1.3456...7.81..4.64.6..8...31.8..9..96.3.....847.......31584.97..9......5.4..9.3.
643: 123.5.678.6.123459...786123.12.4..67.7..129....56...122.....7..................31
647: ..3.5.....9...3.5...7..6.23.12.49.75..5..2..9....75312.3....56.....31......56823.
653: ...4587.9..9......45.79612......5976.9631.8458.596..1..3................5..6.9...
659: 1....76.9.......7....8...233127....66..3..7........31223....9679.....854..4.7.231
661: .2.45.6.9.9......5.5...9...3125.8.6..6931.5..5.8..6.1..31....566.5.3..9......5.31
673: 1234..7...9.123..8...9.7123.....96...6...2...5...7...2.....4....56231.74......2.1
677: 1...59..7...1....9..9.8.123.....8.7.69......8........2.3.89.7.5..5.3.89498...523.
683: ..3..9.6..68.2.459..96..1.33.2...9.69.....5..5.....3..2.1...8.5875.3.6946.4..8..1
691: .2...9....86.....9.5..76..3.1...8....75..2..8648.95.12.3...4....6.....84894567231
701: 12.45....79.12.4.....897123..2.........3..............231564897987231..4654789231
709: 123.57..69..1.3.574579.61..31....67....31.84..4.76..1....6.4......2.176..........
719: ...4.9..7...1.34..4....81......46....8..12.46.4.9873....17.4.8..9..31.74.74.95..1
727: 1234569787891..465..67....3..29.75....5...7....7.6.3.2..16.48.7.78........4.7....
733: 12345.6.7....2..5.45.....2.3128469757.53..84.84.5...1.23....5..5.............5.3.
739: 123........91.34...5.9....3.1..4.8.998.31..45.4.789....3.89.......231..4.9..6....
743: 1.34..7.9.6.1.34..4..7..1..31.84..9..9.3..84..4.9..3...31.749......31.745746892..
751: ..345.7..7......5.45.76.1..31..4..7887........4587.3...3...4..7597...8....4..72..
757: ...4.6.98.8...3....5..89....1..4.8....8.1.6......78.....1894.6.567231.8.894567231
761: 12.4....9......4..457..9..3.1..4......5.12648.4..7.31...17.4..65.92...84..4......
769: 123...7868761234...5...6123.125....7.....25.85.8..73.2.31...8...8...1..4......231
773: 1...........12.....5....1........798......645.....9312231894576765231984..4..6231
787: ..3.5...88....3.57......1..3.2..9......3.2..9948675.1.23...4..668.23..9.........1
797: ...45.798798....5....79812.......86.867...9.5....8.3...3.8..579.792...8..8..7.23.
809: ...4.87......2.4.84...7.123.1.84...696....84.84576..1..3...4.........584..4..7.3.
811: 1..4.86.9......4..4..7..1..31.5...8.8..31..45547.893....18..597..5...8.4.84..52..
821: .23..8.696...23.5.....96.2.3.2..7..69....25..54..69...23.98.6757..23.8.....67....