/* Maximal independent sets in Picat. From http://en.wikipedia.org/wiki/Maximal_independent_set """ In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets. A graph may have many maximal independent sets of widely varying sizes; a largest maximal independent set is called a maximum independent set. """ Also see: http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 Compare with http://www.hakank.org/picat/misp.pi which use another representation and approach. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % import util. % import cp. import sat. main => go. go => nolog, foreach(P in 1..8) println(problem=P), time2(run_problem(P)), nl end, nl. go2 => nolog, problem(8,V), N = V.len, X = new_list(N), X :: 0..1, K #= sum(X), maximal_independent_set(V, X), solve($[ffd,reverse_split,report(printf("K: %d\n", K))],X), println(x=X), println([I : I in 1..N, X[I] = 1]), nl, fail, nl. run_problem(P) => problem(P,V), N = V.len, X = new_list(N), X :: 0..1, K #= sum(X), maximal_independent_set(V, X), solve($[ffd,reverse_split,max(K),report(printf("K: %d\n", K))],X), println(x=X), println([I : I in 1..N, X[I] = 1]), nl. % % X is a maximal independent set of neighbour graph V % maximal_independent_set(V, X) => foreach(I in 1..X.len) (X[I] #= 1) #<=> sum([X[J] #=0 : J in V[I]]) #= V[I].len end. % % Graph from % From http://en.wikipedia.org/wiki/Maximal_independent_set % % 1 ------- 2 % | \ / | % | 3 - 4 | % | | | | % | 5 - 6 | % | / \ | % 7 ------- 8 % % There are 6 maximal independent sets on this graph: % % 1,6 % 1,4,5,8 % 3,8 % 2,5 % 2,3,6,7 % 4,7 % problem(1,V) => V = [ {2,3,7}, % 1 {1,4,8}, % 2 {1,4,5}, % 3 {2,3,6}, % 4 {3,6,7}, % 5 {4,5,8}, % 6 {1,5,8}, % 7 {2,6,7} % 8 ]. % % From http://mathworld.wolfram.com/IndependentSet.html % % Wheel graph n = 8 % % 1 - 2 % / \ / \ % 3- 4 - 5 % | / | \ | % 6 - 7 - 8 % % % n = 8; problem(2,V) => V = [ {2,3,4}, % 1 {1,4,5}, % 2 {1,4,6}, % 3 {1,2,3,4,6,7,8}, % 4 {2,4,8}, % 5 {3,4,6}, % 6 {4,6,8}, % 7 {4,5,7} % 8 ]. % % From http://mathworld.wolfram.com/IndependentSet.html % % Bipartite graph K(3,3) % % There are two maximal independent sets: % {2,4,6} and {1,3,5} % % n = 6; problem(3,V) => V = [ {2,4,6}, % 1 {1,3,5}, % 2 {2,4,6}, % 3 {1,3,5}, % 4 {2,4,6}, % 5 {1,3,5} % 6 ]. % % From http://mathworld.wolfram.com/IndependentSet.html % Petersen graph % % n = 10; problem(4,V) => V = [ {2,3,6}, % 1 {1,4,7}, % 2 {1,5,8}, % 3 {2,5,9}, % 4 {3,4,10}, % 5 {1,9,10}, % 6 {2,8,10}, % 7 {3,7,9}, % 8 {4,6,8}, % 9 {5,6,7} % 10 ]. % http://mathworld.wolfram.com/IndependentSet.html % Frucht graph % maximum independent set (k=5): {1,4,6,9,10} % % constraint k = 5; % n = 12; problem(5,V) => V = [ {2,7,8}, % 1 {1,3,9}, % 2 {2,4,9}, % 3 {3,5,12}, % 4 {4,6,12}, % 5 {5,7,11}, % 6 {1,6,11}, % 7 {1,9,10}, % 8 {2,3,8}, % 9 {8,11,12}, % 10 {6,7,10}, % 11 {4,5,10} % 12 ]. % From Alfred V. Aho, Jeffrey D. Ullman: "Foundations of Computer Science" % http://infolab.stanford.edu/~ullman/focs.html % Chapter 1, "Computer Science: The Mechanization of Abstraction" % http://infolab.stanford.edu/~ullman/focs/ch01.pdf % page 2 % """ % As [an] example, suppose we are faced with the problem of scheduling % final examinations for courses. That is, we must assign course exams % to time slots so that two courses may have their exams scheduled in the % same time slot only if there is no student taking both. % % Eng -- Math 1 -- 2 % \ / \ / % CS 3 % / \ / \ % Econ Phy 4 5 % % Cource-conflict graph for five courses where an edge % between two nodes indicates that at least one student % is taking both cources % """ % There are 3 maximal independent sets: % {1,4,5} {Eng,Econ, Phy} % {2,4,5} {Math,Econ, Phy} % {3} {CS} % % n = 5; problem(6,V) => V = [ {2,3}, % 1, Eng {1,3}, % 2, Math {1,2,4,5}, % 3, CS {3}, % 4, Econ {3} % 5, Phy ]. % % From http://www.hakank.org/minizinc/misp.mzn % (GLPK:s example misp.mod in MiniZinc) % Data from: % """ % M.G.C. Resende, T.A.Feo, S.H.Smith, "Algorithm 787 -- FORTRAN % subroutines for approximate solution of the maximum independent set % problem using GRASP," Trans. on Math. Softw., Vol. 24, No. 4, % December 1998, pp. 386-394. % % The optimal solution is 7 % """ % % Note: There are 29 solutions with k = 7 % % constraint k = 7; % % n = 50; problem(7, V) => V = [ {2,3,5,7,8,12,15,16,19,20,21,22,28,30,34,35,37,41,42,47,50}, % 1 {1,3,5,6,7,8,9,10,13,17,19,20,21,23,25,26,29,31,35,36,44,45,46,50}, % 2 {1,2,5,6,8,9,10,11,14,16,23,24,26,27,28,29,30,31,34,35,36,39,41,42,43,44,50}, % 3 {6,7,9,10,11,13,14,15,17,21,22,23,24,25,27,28,30,31,33,34,35,36,37,38,40,41,42,46,49}, % 4 {1,2,3,6,11,14,21,24,25,28,35,38,39,41,44,49,50}, % 5 {2,3,4,5,8,9,10,13,14,16,17,19,22,23,26,27,30,34,35,38,39,40,41,44,45,47,50}, % 6 {1,2,4,8,9,10,11,13,15,16,18,20,22,23,24,25,33,35,36,38,43,45,46,47}, % 7 {1,2,3,6,7,10,11,13,16,17,18,19,20,21,22,23,24,25,26,33,35,36,39,42,44,48,49}, % 8 {2,3,4,6,7,12,14,17,19,20,23,28,30,31,32,33,34,38,39,42,44,45,46}, % 9 {2,3,4,6,7,8,11,13,15,16,17,20,21,22,23,25,26,27,28,30,31,32,37,38,41,43,44,45,50}, % 10 {3,4,5,7,8,10,12,14,15,18,21,24,25,26,29,32,33,35,36,37,39,40,42,43,45,47,49,50}, % 11 {1,9,11,13,16,17,19,24,25,26,30,31,32,34,36,37,39,41,44,47,48,49}, % 12 {2,4,6,7,8,10,12,15,16,18,19,20,22,23,24,27,28,29,31,33,35,36,37,44,47,49,50}, % 13 {3,4,5,6,9,11,15,16,17,18,19,20,21,26,28,29,30,31,32,34,35,36,38,39,41,44,46,47,48}, % 14 {1,4,7,10,11,13,14,18,21,22,23,25,28,29,30,33,34,36,37,38,39,40,43,44,46,50}, % 15 {1,3,6,7,8,10,12,13,14,17,19,20,25,26,29,35,38,39,40,41,42,44}, % 16 {2,4,6,8,9,10,12,14,16,18,19,21,22,23,25,26,28,29,33,37,44,45,48}, % 17 {7,8,11,13,14,15,17,20,24,27,28,31,32,34,35,36,37,38,45,48,49,50}, % 18 {1,2,6,8,9,12,13,14,16,17,22,24,28,29,36,37,39,41,43,45,48,49}, % 19 {1,2,7,8,9,10,13,14,16,18,21,22,24,25,26,27,29,30,31,33,34,35,38,39,41,42,43,44,45,46,48,49}, % 20 {1,2,4,5,8,10,11,14,15,17,20,22,23,29,31,35,38,42,46,47}, % 21 {1,4,6,7,8,10,13,15,17,19,20,21,23,26,27,28,29,30,39,40,41,42,44,45,46,47,49,50}, % 22 {2,3,4,6,7,8,9,10,13,15,17,21,22,28,31,32,33,34,35,36,39,40,41,42,44,45,48,49,50}, % 23 {3,4,5,7,8,11,12,13,18,19,20,25,27,29,30,31,33,34,38,42,43,44,49,50}, % 24 {2,4,5,7,8,10,11,12,15,16,17,20,24,26,27,29,30,33,34,36,38,40,41,42,44,46,47,48,49}, % 25 {2,3,6,8,10,11,12,14,16,17,20,22,25,28,31,32,33,37,38,39,40,41,42,45,47,48,49}, % 26 {3,4,6,10,13,18,20,22,24,25,29,30,33,34,35,39,40,46,48}, % 27 {1,3,4,5,9,10,13,14,15,17,18,19,22,23,26,29,37,40,42,44,46,47,50}, % 28 {2,3,11,13,14,15,16,17,19,20,21,22,24,25,27,28,35,38,39,41,42,48}, % 29 {1,3,4,6,9,10,12,14,15,20,22,24,25,27,31,32,35,37,38,40,43,45,46,47,48}, % 30 {2,3,4,9,10,12,13,14,18,20,21,23,24,26,30,33,35,38,40,41,42,44,46,47,50}, % 31 {9,10,11,12,14,18,23,26,30,33,35,39,40,46,49,50}, % 32 {4,7,8,9,11,13,15,17,20,23,24,25,26,27,31,32,34,36,37,40,42,43,44,45,50}, % 33 {1,3,4,6,9,12,14,15,18,20,23,24,25,27,33,35,36,37,38,40,43,44,49,50}, % 34 {1,2,3,4,5,6,7,8,11,13,14,16,18,20,21,23,27,29,30,31,32,34,36,38,41,42,43,45,46,47,49,50}, % 35 {2,3,4,7,8,11,12,13,14,15,18,19,23,25,33,34,35,37,39,40,41,42,43,48,50}, % 36 {1,4,10,11,12,13,15,17,18,19,26,28,30,33,34,36,38,41,43,46,47,48,49,50}, % 37 {4,5,6,7,9,10,14,15,16,18,20,21,24,25,26,29,30,31,34,35,37,41,45,46,48,49,50}, % 38 {3,5,6,8,9,11,12,14,15,16,19,20,22,23,26,27,29,32,36,43,46,47,48,49}, % 39 {4,6,11,15,16,22,23,25,26,27,28,30,31,32,33,34,36,43,45,48,50}, % 40 {1,3,4,5,6,10,12,14,16,19,20,22,23,25,26,29,31,35,36,37,38,42,43,44,45,46,48,49}, % 41 {1,3,4,8,9,11,16,20,21,22,23,24,25,26,28,29,31,33,35,36,41,43,44,46,48,49}, % 42 {3,7,10,11,15,19,20,24,30,33,34,35,36,37,39,40,41,42,45,46,48,50}, % 43 {2,3,5,6,8,9,10,12,13,14,15,16,17,20,22,23,24,25,28,31,33,34,41,42,45,48}, % 44 {2,6,7,9,10,11,17,18,19,20,22,23,26,30,33,35,38,40,41,43,44,46,47,48}, % 45 {2,4,7,9,14,15,20,21,22,25,27,28,30,31,32,35,37,38,39,41,42,43,45,49}, % 46 {1,6,7,11,12,13,14,21,22,25,26,28,30,31,35,37,39,45,49,50}, % 47 {8,12,14,17,18,19,20,23,25,26,27,29,30,36,37,38,39,40,41,42,43,44,45,49,50}, % 48 {4,5,8,11,12,13,18,19,20,22,23,24,25,26,32,34,35,37,38,39,41,42,46,47,48,50}, % 49 {1,2,3,5,6,10,11,13,15,18,22,23,24,28,31,32,33,34,35,36,37,38,40,43,47,48,49} % 50 ]. % From % http://www2.research.att.com/~njas/doc/graphs.html % http://www2.research.att.com/~njas/doc/1dc.128.txt.gz % """ % a 128-node graph in which it is known that the size of a maximal independent set % is 16. The Varshamov-Tenegolts code VT0(7) of length 7 forms an independent set % of size 16 (see Ref. [Sl00]), namely % % 1 14 20 21 35 48 55 58 66 79 86 89 100 101 120 123 % % and Magma has confirmed that no larger independent set exists. % """ % % constraint k = 16; % n = 128; problem(8, V) => V = [ {2,3,5,9,17,33,65}, % 1 {1,3,4,5,6,9,10,17,18,33,34,65,66}, % 2 {1,2,4,5,6,7,9,10,11,17,18,19,33,34,35,65,66,67}, % 3 {2,3,6,7,8,10,12,18,20,34,36,66,68}, % 4 {1,2,3,6,7,9,10,11,13,17,19,21,33,35,37,65,67,69}, % 5 {2,3,4,5,7,8,10,11,12,14,18,19,20,22,34,35,36,38,66,67,68,70}, % 6 {3,4,5,6,8,11,12,13,14,15,19,20,23,35,36,39,67,68,71}, % 7 {4,6,7,12,14,15,16,20,24,36,40,68,72}, % 8 {1,2,3,5,10,11,13,17,18,19,21,25,33,37,41,65,69,73}, % 9 {2,3,4,5,6,9,11,12,13,14,18,19,20,21,22,26,34,37,38,42,66,69,70,74}, % 10 {3,5,6,7,9,10,12,13,14,15,19,21,22,23,27,35,37,38,39,43,67,69,70,71,75}, % 11 {4,6,7,8,10,11,14,15,16,20,22,23,24,28,36,38,40,44,68,70,72,76}, % 12 {5,7,9,10,11,14,15,21,23,25,26,27,29,37,39,45,69,71,77}, % 13 {6,7,8,10,11,12,13,15,16,22,23,24,26,27,28,30,38,39,40,46,70,71,72,78}, % 14 {7,8,11,12,13,14,16,23,24,27,29,30,31,39,40,47,71,72,79}, % 15 {8,12,14,15,24,28,30,31,32,40,48,72,80}, % 16 {1,2,3,5,9,18,19,21,25,33,34,35,37,41,49,65,73,81}, % 17 {2,3,4,6,9,10,17,19,20,21,22,25,26,34,35,36,38,41,42,50,66,73,74,82}, % 18 {3,5,6,7,9,10,11,17,18,20,21,22,23,25,26,27,35,37,38,39,41,42,43,51,67,73,74,75,83}, % 19 {4,6,7,8,10,12,18,19,22,23,24,26,28,36,38,39,40,42,44,52,68,74,76,84}, % 20 {5,9,10,11,13,17,18,19,22,23,25,26,27,29,37,41,42,43,45,53,69,73,75,77,85}, % 21 {6,10,11,12,14,18,19,20,21,23,24,26,27,28,30,38,42,43,44,46,54,70,74,75,76,78,86}, % 22 {7,11,12,13,14,15,19,20,21,22,24,27,28,29,30,31,39,43,44,45,46,47,55,71,75,76,79,87}, % 23 {8,12,14,15,16,20,22,23,28,30,31,32,40,44,46,47,48,56,72,76,80,88}, % 24 {9,13,17,18,19,21,26,27,29,41,45,49,50,51,53,57,73,77,89}, % 25 {10,13,14,18,19,20,21,22,25,27,28,29,30,42,45,46,50,51,52,54,58,74,77,78,90}, % 26 {11,13,14,15,19,21,22,23,25,26,28,29,30,31,43,45,46,47,51,53,54,55,59,75,77,78,79,91}, % 27 {12,14,16,20,22,23,24,26,27,30,31,32,44,46,48,52,54,55,56,60,76,78,80,92}, % 28 {13,15,21,23,25,26,27,30,31,45,47,53,57,58,59,61,77,79,93}, % 29 {14,15,16,22,23,24,26,27,28,29,31,32,46,47,48,54,58,59,60,62,78,79,80,94}, % 30 {15,16,23,24,27,28,29,30,32,47,48,55,59,61,62,63,79,80,95}, % 31 {16,24,28,30,31,48,56,60,62,63,64,80,96}, % 32 {1,2,3,5,9,17,34,35,37,41,49,65,66,67,69,73,81,97}, % 33 {2,3,4,6,10,17,18,33,35,36,37,38,41,42,49,50,66,67,68,70,74,81,82,98}, % 34 {3,5,6,7,11,17,18,19,33,34,36,37,38,39,41,42,43,49,50,51,67,69,70,71,75,81,82,83,99}, % 35 {4,6,7,8,12,18,20,34,35,38,39,40,42,44,50,52,68,70,71,72,76,82,84,100}, % 36 {5,9,10,11,13,17,19,21,33,34,35,38,39,41,42,43,45,49,51,53,69,73,74,75,77,81,83,85,101}, % 37 {6,10,11,12,14,18,19,20,22,34,35,36,37,39,40,42,43,44,46,50,51,52,54,70,74,75,76,78,82,83,84,86,102}, % 38 {7,11,13,14,15,19,20,23,35,36,37,38,40,43,44,45,46,47,51,52,55,71,75,77,78,79,83,84,87,103}, % 39 {8,12,14,15,16,20,24,36,38,39,44,46,47,48,52,56,72,76,78,79,80,84,88,104}, % 40 {9,17,18,19,21,25,33,34,35,37,42,43,45,49,50,51,53,57,73,81,82,83,85,89,105}, % 41 {10,18,19,20,21,22,26,34,35,36,37,38,41,43,44,45,46,50,51,52,53,54,58,74,82,83,84,85,86,90,106}, % 42 {11,19,21,22,23,27,35,37,38,39,41,42,44,45,46,47,51,53,54,55,59,75,83,85,86,87,91,107}, % 43 {12,20,22,23,24,28,36,38,39,40,42,43,46,47,48,52,54,55,56,60,76,84,86,87,88,92,108}, % 44 {13,21,23,25,26,27,29,37,39,41,42,43,46,47,53,55,57,58,59,61,77,85,87,89,90,91,93,109}, % 45 {14,22,23,24,26,27,28,30,38,39,40,42,43,44,45,47,48,54,55,56,58,59,60,62,78,86,87,88,90,91,92,94,110}, % 46 {15,23,24,27,29,30,31,39,40,43,44,45,46,48,55,56,59,61,62,63,79,87,88,91,93,94,95,111}, % 47 {16,24,28,30,31,32,40,44,46,47,56,60,62,63,64,80,88,92,94,95,96,112}, % 48 {17,25,33,34,35,37,41,50,51,53,57,81,89,97,98,99,101,105,113}, % 49 {18,25,26,34,35,36,38,41,42,49,51,52,53,54,57,58,82,89,90,98,99,100,102,106,114}, % 50 {19,25,26,27,35,37,38,39,41,42,43,49,50,52,53,54,55,57,58,59,83,89,90,91,99,101,102,103,107,115}, % 51 {20,26,28,36,38,39,40,42,44,50,51,54,55,56,58,60,84,90,92,100,102,103,104,108,116}, % 52 {21,25,27,29,37,41,42,43,45,49,50,51,54,55,57,58,59,61,85,89,91,93,101,105,106,107,109,117}, % 53 {22,26,27,28,30,38,42,43,44,46,50,51,52,53,55,56,58,59,60,62,86,90,91,92,94,102,106,107,108,110,118}, % 54 {23,27,28,31,39,43,44,45,46,47,51,52,53,54,56,59,60,61,62,63,87,91,92,95,103,107,109,110,111,119}, % 55 {24,28,32,40,44,46,47,48,52,54,55,60,62,63,64,88,92,96,104,108,110,111,112,120}, % 56 {25,29,41,45,49,50,51,53,58,59,61,89,93,105,113,114,115,117,121}, % 57 {26,29,30,42,45,46,50,51,52,53,54,57,59,60,61,62,90,93,94,106,114,115,116,118,122}, % 58 {27,29,30,31,43,45,46,47,51,53,54,55,57,58,60,61,62,63,91,93,94,95,107,115,117,118,119,123}, % 59 {28,30,32,44,46,48,52,54,55,56,58,59,62,63,64,92,94,96,108,116,118,119,120,124}, % 60 {29,31,45,47,53,55,57,58,59,62,63,93,95,109,117,121,122,123,125}, % 61 {30,31,32,46,47,48,54,55,56,58,59,60,61,63,64,94,95,96,110,118,122,123,124,126}, % 62 {31,32,47,48,55,56,59,60,61,62,64,95,96,111,119,123,125,126,127}, % 63 {32,48,56,60,62,63,96,112,120,124,126,127,128}, % 64 {1,2,3,5,9,17,33,66,67,69,73,81,97}, % 65 {2,3,4,6,10,18,33,34,65,67,68,69,70,73,74,81,82,97,98}, % 66 {3,5,6,7,11,19,33,34,35,65,66,68,69,70,71,73,74,75,81,82,83,97,98,99}, % 67 {4,6,7,8,12,20,34,36,66,67,70,71,72,74,76,82,84,98,100}, % 68 {5,9,10,11,13,21,33,35,37,65,66,67,70,71,73,74,75,77,81,83,85,97,99,101}, % 69 {6,10,11,12,14,22,34,35,36,38,66,67,68,69,71,72,74,75,76,78,82,83,84,86,98,99,100,102}, % 70 {7,11,13,14,15,23,35,36,39,67,68,69,70,72,75,76,77,78,79,83,84,87,99,100,103}, % 71 {8,12,14,15,16,24,36,40,68,70,71,76,78,79,80,84,88,100,104}, % 72 {9,17,18,19,21,25,33,37,41,65,66,67,69,74,75,77,81,82,83,85,89,97,101,105}, % 73 {10,18,19,20,22,26,34,37,38,42,66,67,68,69,70,73,75,76,77,78,82,83,84,85,86,90,98,101,102,106}, % 74 {11,19,21,22,23,27,35,37,38,39,43,67,69,70,71,73,74,76,77,78,79,83,85,86,87,91,99,101,102,103,107}, % 75 {12,20,22,23,24,28,36,38,40,44,68,70,71,72,74,75,78,79,80,84,86,87,88,92,100,102,104,108}, % 76 {13,21,25,26,27,29,37,39,45,69,71,73,74,75,78,79,85,87,89,90,91,93,101,103,109}, % 77 {14,22,26,27,28,30,38,39,40,46,70,71,72,74,75,76,77,79,80,86,87,88,90,91,92,94,102,103,104,110}, % 78 {15,23,27,29,30,31,39,40,47,71,72,75,76,77,78,80,87,88,91,93,94,95,103,104,111}, % 79 {16,24,28,30,31,32,40,48,72,76,78,79,88,92,94,95,96,104,112}, % 80 {17,33,34,35,37,41,49,65,66,67,69,73,82,83,85,89,97,98,99,101,105,113}, % 81 {18,34,35,36,38,41,42,50,66,67,68,70,73,74,81,83,84,85,86,89,90,98,99,100,102,105,106,114}, % 82 {19,35,37,38,39,41,42,43,51,67,69,70,71,73,74,75,81,82,84,85,86,87,89,90,91,99,101,102,103,105,106,107,115}, % 83 {20,36,38,39,40,42,44,52,68,70,71,72,74,76,82,83,86,87,88,90,92,100,102,103,104,106,108,116}, % 84 {21,37,41,42,43,45,53,69,73,74,75,77,81,82,83,86,87,89,90,91,93,101,105,106,107,109,117}, % 85 {22,38,42,43,44,46,54,70,74,75,76,78,82,83,84,85,87,88,90,91,92,94,102,106,107,108,110,118}, % 86 {23,39,43,44,45,46,47,55,71,75,76,77,78,79,83,84,85,86,88,91,92,93,94,95,103,107,108,109,110,111,119}, % 87 {24,40,44,46,47,48,56,72,76,78,79,80,84,86,87,92,94,95,96,104,108,110,111,112,120}, % 88 {25,41,45,49,50,51,53,57,73,77,81,82,83,85,90,91,93,105,109,113,114,115,117,121}, % 89 {26,42,45,46,50,51,52,54,58,74,77,78,82,83,84,85,86,89,91,92,93,94,106,109,110,114,115,116,118,122}, % 90 {27,43,45,46,47,51,53,54,55,59,75,77,78,79,83,85,86,87,89,90,92,93,94,95,107,109,110,111,115,117,118,119,123}, % 91 {28,44,46,48,52,54,55,56,60,76,78,80,84,86,87,88,90,91,94,95,96,108,110,112,116,118,119,120,124}, % 92 {29,45,47,53,57,58,59,61,77,79,85,87,89,90,91,94,95,109,111,117,121,122,123,125}, % 93 {30,46,47,48,54,58,59,60,62,78,79,80,86,87,88,90,91,92,93,95,96,110,111,112,118,122,123,124,126}, % 94 {31,47,48,55,59,61,62,63,79,80,87,88,91,92,93,94,96,111,112,119,123,125,126,127}, % 95 {32,48,56,60,62,63,64,80,88,92,94,95,112,120,124,126,127,128}, % 96 {33,49,65,66,67,69,73,81,98,99,101,105,113}, % 97 {34,49,50,66,67,68,70,74,81,82,97,99,100,101,102,105,106,113,114}, % 98 {35,49,50,51,67,69,70,71,75,81,82,83,97,98,100,101,102,103,105,106,107,113,114,115}, % 99 {36,50,52,68,70,71,72,76,82,84,98,99,102,103,104,106,108,114,116}, % 100 {37,49,51,53,69,73,74,75,77,81,83,85,97,98,99,102,103,105,106,107,109,113,115,117}, % 101 {38,50,51,52,54,70,74,75,76,78,82,83,84,86,98,99,100,101,103,104,106,107,108,110,114,115,116,118}, % 102 {39,51,52,55,71,75,77,78,79,83,84,87,99,100,101,102,104,107,108,109,110,111,115,116,119}, % 103 {40,52,56,72,76,78,79,80,84,88,100,102,103,108,110,111,112,116,120}, % 104 {41,49,53,57,73,81,82,83,85,89,97,98,99,101,106,107,109,113,114,115,117,121}, % 105 {42,50,53,54,58,74,82,83,84,85,86,90,98,99,100,101,102,105,107,108,109,110,114,115,116,117,118,122}, % 106 {43,51,53,54,55,59,75,83,85,86,87,91,99,101,102,103,105,106,108,109,110,111,115,117,118,119,123}, % 107 {44,52,54,56,60,76,84,86,87,88,92,100,102,103,104,106,107,110,111,112,116,118,119,120,124}, % 108 {45,53,55,61,77,85,87,89,90,91,93,101,103,105,106,107,110,111,117,119,121,122,123,125}, % 109 {46,54,55,56,62,78,86,87,88,90,91,92,94,102,103,104,106,107,108,109,111,112,118,119,120,122,123,124,126}, % 110 {47,55,56,63,79,87,88,91,93,94,95,103,104,107,108,109,110,112,119,120,123,125,126,127}, % 111 {48,56,64,80,88,92,94,95,96,104,108,110,111,120,124,126,127,128}, % 112 {49,57,81,89,97,98,99,101,105,114,115,117,121}, % 113 {50,57,58,82,89,90,98,99,100,102,105,106,113,115,116,117,118,121,122}, % 114 {51,57,58,59,83,89,90,91,99,101,102,103,105,106,107,113,114,116,117,118,119,121,122,123}, % 115 {52,58,60,84,90,92,100,102,103,104,106,108,114,115,118,119,120,122,124}, % 116 {53,57,59,61,85,89,91,93,101,105,106,107,109,113,114,115,118,119,121,122,123,125}, % 117 {54,58,59,60,62,86,90,91,92,94,102,106,107,108,110,114,115,116,117,119,120,122,123,124,126}, % 118 {55,59,60,63,87,91,92,95,103,107,108,109,110,111,115,116,117,118,120,123,124,125,126,127}, % 119 {56,60,64,88,92,96,104,108,110,111,112,116,118,119,124,126,127,128}, % 120 {57,61,89,93,105,109,113,114,115,117,122,123,125}, % 121 {58,61,62,90,93,94,106,109,110,114,115,116,117,118,121,123,124,125,126}, % 122 {59,61,62,63,91,93,94,95,107,109,110,111,115,117,118,119,121,122,124,125,126,127}, % 123 {60,62,64,92,94,96,108,110,112,116,118,119,120,122,123,126,127,128}, % 124 {61,63,93,95,109,111,117,119,121,122,123,126,127}, % 125 {62,63,64,94,95,96,110,111,112,118,119,120,122,123,124,125,127,128}, % 126 {63,64,95,96,111,112,119,120,123,124,125,126,128}, % 127 {64,96,112,120,124,126,127} % 128 ].